方宏进近况,中国十大名牌床垫,对头小冤家
由题意可得出递推式\(f[i ,j]=\sum_{e\in s} f[i-1,\frac{j}{e}]\)，初值\(f[0,0]=1\)，答案为\(f[n,x]\)，具体意义不表。
分析可知\(f[1,e(e\in s)]=1\)，\(f[i,ab]=\sum_{a\in s,b\in s}f[i-1,a]f[1,b]\)；
设模数\(m\)（指数）的一个原根为\(g\)，构造\(e'=\log_g(e)\in s', e\in s\)，改写递推式\(f[1,e'\in s']=1\),\(f[i,a'+b']=\sum_{a',b\in s'}f[i-1,a']f[1,b']\) 。就能套卷积做了*(^e^)*。
做法的正确性：因为\(g^i(0\le i<m-1)\)能取遍\([1,m-1]\)所有数，故\(e\in 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;
}
}
就酱，实现留坑。
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论