menu ZigZagK的博客
account_circle

正在努力加载中QAQ

[原根+循环矩阵快速幂]liu_runda NOIP模拟题【随】题解
apps HHHOJ
local_offer 查看标签
comment 0 条评论

解题报告

先来介绍一波原根:如果 $\forall i\not=j,g^i\not\equiv g^j\ (mod\ P)$ ,那么 $g$ 是 $P$ 的一个原根,如果 $P$ 是素数那么一定有原根。

原根有什么用呢?如果有了原根,那么我们就可以做到模意义下取对数,也就是说我们我可以把模意义下乘法变成模意义下加法,这是很重要的一个作用。

怎么求原根?爆枚!一般原根都不会很大,所以直接爆枚,判断的时候可以这样:对于 $P-1$ 的所有素因子 $p$ ,如果均满足 $a^{P-1\over p_i}\not=1$ 那么说明 $a$ 是 $P$ 的一个原根。证明我不会……


这道题很明显可以矩乘优化DP,但是复杂度是 $O(P^3log_2m)$ ,直接炸飞。这时候就需要用到原根的套路,用原根把转移矩阵中的乘法换成加法,那么就会发生一件很奇妙的事情:转移矩阵是循环的,也就是说只需要知道第一列就可以推知整个矩阵,这时候矩乘可以做到 $O(P^2)$ ,就可以过了。

会发现矩乘是个循环卷积的形式,甚至可以用循环卷积FFT做到更优秀的复杂度,不过我不会……

示例程序

#include<cstdio>
using namespace std;
typedef long long LL;
const int maxp=1000,MOD=1e9+7;

int n,m,P,g,pw[maxp+5],Lg[maxp+5],p[maxp+5],D[maxp+5];bool pri[maxp+5];
int S[maxp+5],T[maxp+5],c[maxp+5],ans;

inline void Make(){
    for (int i=2;i<=maxp;i++){
        if (!pri[i]) p[++p[0]]=i;
        for (int j=1,t;j<=p[0]&&(t=i*p[j])<=maxp;j++)
            if (i%p[j]) pri[t]=true; else {pri[t]=true;break;}
    }for (int i=1;i<=p[0];i++) if (!((P-1)%p[i])) D[++D[0]]=(P-1)/p[i];
}
inline int Pow(int w,int b,int MOD) {int s=1;for (;b;b>>=1,w=(LL)w*w%MOD) if (b&1) s=(LL)s*w%MOD;return s;}
inline bool check(int g) {for (int i=1;i<=D[0];i++) if (Pow(g,D[i],P)==1) return false;return true;}
inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
inline void Mul(int *a,int *b,int P){
    for (int i=0;i<P;i++)
        {c[i]=0;for (int j=0;j<P;j++) AMOD(c[i],(LL)a[j]*b[(i-j+P)%P]%MOD);}
    for (int i=0;i<P;i++) a[i]=c[i];
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d%d",&n,&m,&P);Make();for (g=2;g<=MOD-1;g++) if (check(g)) break;
    for (int i=0,w=1;i<P-1;i++,w=w*g%P) pw[i]=w,Lg[w]=i;
    for (int i=1,x;i<=n;i++) scanf("%d",&x),T[Lg[x]]++;
    S[0]=1;for (int b=m;b;b>>=1,Mul(T,T,P-1)) if (b&1) Mul(S,T,P-1);
    for (int i=0;i<P-1;i++) AMOD(ans,(LL)S[i]*pw[i]%MOD);
    ans=(LL)ans*Pow(Pow(n,m,MOD),MOD-2,MOD)%MOD;printf("%d\n",ans);return 0;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!
名称不能为空
email
邮箱不能为空,请填写正确格式
link
网址请用http://或https://开头
message
评论不能为空
资瓷Markdown和LaTeX数学公式
sentiment_very_satisfied
keyboard_arrow_up