由题意可得出递推式(f[i ,j]=sum_{ein s} f[i-1,frac{j}{e}]),初值(f[0,0]=1),答案为(f[n,x]),具体意义不表。
分析可知(f[1,e(ein s)]=1),(f[i,ab]=sum_{ain s,bin s}f[i-1,a]f[1,b]);
设模数(m)(指数)的一个原根为(g),构造(e'=log_g(e)in s', ein s),改写递推式(f[1,e'in s']=1),(f[i,a'+b']=sum_{a',bin s'}f[i-1,a']f[1,b']) 。就能套卷积做了*(^e^)*。
做法的正确性:因为(g^i(0le i<m-1))能取遍([1,m-1])所有数,故(ein s)都有存在唯一在([0,m-1))里的离散对数。
于是此题就是离散快速傅利叶的模板了。
最后谈谈(g)的求法很暴力,枚举原根(g),然后小大枚举阶(阶的个数是(o(sqrt m))级的)来判断是否过早地产生循环,如下
int getg(int m) { vector<int> r; for(int i=2; i*i<=m-1; ++i) if((m-1)%i==0) { r.push_back(i); if(i*i!=m-1) r.push_back((m-1)/i); } sort(r.begin(),r.end()); for(int i=2; ; ++i) { bool flag=1; for(auto rr: r) if(fpow(i,rr,m)==1) {flag=0; break;} if(flag) return i; } }
就酱,实现留坑。
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/604724.html