題目鏈接
\(Description\)
q次詢問，每次給定r,n，求\(F_r(n)\)。
\[ f_0(n)=\sum_{u\times v=n}[(u,v)=1]\\ f_{r+1}(n)=\sum_{u\times v=n}\frac{f_r(u)+f_r(v)}{2}\]
\(Solution\)
首先將\(f_r\)的式子化為
\[ f_{r+1}(n)=\sum_{d|n}f_r(d)\]
即\(f_{r+1}(n)\)為\(f_r(n)\)與\(g(n)=1\)的狄利克雷卷積。
因為n的所有質(zhì)因子之間對\(f_0(n)\)的貢獻(xiàn)是獨立的，所以顯然\(f_0(n)\)為積性函數(shù)（為什么我還是不懂。。），那么\(f_r(n)\)也為積性函數(shù)。
于是可以對每個質(zhì)因子單獨計算，這樣狄利克雷卷積就可以化成求和
\[ f_{r+1}(p^k)=\sum_{i=0}^kf_r(p^i) \]
（\(p^k\)的所有因子即\(p^i,i=0,1,\ldots,k\)）
同時可以發(fā)現(xiàn)\(f_0(p^k)=[k\neq 0]+1\)，即\(f_0(p^k)\)的值與因子p無關(guān)，只與次數(shù)有關(guān)。
那么DP，用\(dp[i][j]\)表示\(f_i(p^j)\)，則\(dp[i][j]=\sum_{k=0}^jdp[i-1][k]\)。
詢問時對\(n\)分解質(zhì)因數(shù)即可。
#include<cmath>
#include<cstdio>
#include<cctype>
#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
const int N=1e6+3,M=21,mod=1e9+7,MAXIN=1<<18;int r,n,f[N+3][21],Primes[100000],cnt;
char IN[MAXIN],*SS=IN,*TT=IN;
bool Not_Prime[N+3];inline int read()
{int now=0,f=1;register char c=gc();for(;!isdigit(c);c=gc()) if(c=='-') f=-1;for(;isdigit(c);now=now*10+c-'0',c=gc());return now*f;
}
#define Mod(a) (a>=mod)?a-=mod:0
void Init()
{
// Not_Prime[1]=1;for(int i=2;i<N;++i){if(!Not_Prime[i]) Primes[++cnt]=i;for(int j=1;j<=cnt&&Primes[j]*i<N;++j){Not_Prime[i*Primes[j]]=1;if(!(i%Primes[j])) break;}}f[0][0]=1;//f_r(p^0)=1for(int i=1;i<M;++i) f[0][i]=2;for(int sum=0,i=1;i<N;++i,sum=0)for(int j=0;j<M;++j){sum+=f[i-1][j], Mod(sum);f[i][j]+=sum, Mod(f[i][j]);}
}
int Solve(int r,int n)
{int ans=1,m=sqrt(n+0.5);for(int i=1;i<=cnt&&Primes[i]<=m;++i){if(n%Primes[i]) continue;int t=0;while(!(n%Primes[i])) n/=Primes[i],++t;ans=1LL*ans*f[r][t]%mod;}if(n>1) ans=1LL*ans*f[r][1]%mod;//本身是個質(zhì)數(shù) return ans;
}int main()
{
//#ifndef ONLINE_JUDGE
// freopen("757.in","r",stdin);
//#endifInit();int t=read(),r,n;while(t--)r=read(),n=read(),printf("%d\n",Solve(r,n));return 0;
}
轉(zhuǎn)載于:https://www.cnblogs.com/SovietPower/p/8324134.html
總結(jié)
以上是生活随笔為你收集整理的Codeforces757E.Bash Plays With Functions(积性函数 DP)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
