CF1561D Up the Strip (整除分块 dp 因子)

CF1561D Up the Strip (整除分块 dp 因子)

Codeforces Round #740 (Div. 2, based on VK Cup 2021 - Final (Engine))

D1. Up the Strip (simplified version)

D2. Up the Strip

题意：

思路：

for(int l=2,r;l<=i;l=r+1){ r=i/(i/l); dp[i]=(dp[i]+(r-l+1)*dp[i/l]%mod)%mod;}

for(int j=2;j*i<=n;j++){//(i*j)/j=i，所以i*j可以转移到i int r=min(n,(ll)i*j+j-1);//右边界 dp[i]=(dp[i]+sum[i*j]-sum[r+1]+mod)%mod;//后缀和}

代码：

const int maxn=2e5+10; ll n,dp[maxn],mod,sum[maxn]; int main(){ n=read,mod=read; dp[1]=1;dp[2]=2; sum[1]=1,sum[2]=3; rep(i,3,n){ dp[i]=(dp[i]+sum[i-1])%mod; for(int l=2,r;l<=i;l=r+1){ r=i/(i/l); dp[i]=(dp[i]+(r-l+1)*dp[i/l]%mod)%mod; //cout<

const int maxn=4e6+10; ll n,dp[maxn],mod,sum[maxn]; int main(){ n=read,mod=read; dp[n]=sum[n]=1; per(i,n-1,1){ dp[i]=sum[i+1]; //sum[i]=(sum[i+1]+dp[i])%mod; for(int j=2;j*i<=n;j++){ int r=min(n,(ll)i*j+j-1); dp[i]=(dp[i]+sum[i*j]-sum[r+1]+mod)%mod; } sum[i]=(sum[i+1]+dp[i])%mod; } write(dp[1]); return 0;}

好有道理~

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。