Codeforces Round #740 (Div. 2, based on VK Cup 2021 - Final (Engine))
D1. Up the Strip (simplified version)
D2. Up the Strip
题意：
给出一个数n，每次有两种操作，设x为当前数字
选择1 < = y < = x − 1 , x = x − y
选择2 < = z < = x , x = x /2（向下取整）
问从n nn变为1 11的方案数。
e a s y v e r s i o n 中n < = 2 e 5
h a r d v e r s i o n 中n < = 4 e 6
思路：
假设d p [ i ]表示从i变到1的方案数，那么d p [ i ] = ∑ j = 1 i − 1 d p [ j ] + ∑ k = 2 i d p [ i k ]
前一项表示通过减法到达j，后一项表示通过除法到达k。
这样的复杂度是O ( n 2 )的，考虑能够怎么优化。
∑ j = 1 i − 1 d p [ j ]可以用前缀和优化，每次加上s u m i − 1 就行。
后面一项，由于每次都是向下取整，真正的除数只有i个，可以用整除分块来做，每次维护因子能够影响到的区间。时间复杂度O ( n n )
学习链接
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; }
这个复杂度过d 2显然不大行，考虑进一步的优化。
看看是否能从后继状态转移过来，比如当枚举到x时，除数为2，那么2 x , 2 x + 1就可以通过除2到达x。
进一步的扩展，对于x的每个除数y，都能够通过[ z y , z y + y − 1 ]中的数除y到达x。
可以枚举倍数，并且维护后缀和。时间复杂度O ( n l o g n )
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;//后缀和 }
代码：
D 1 D1D1
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<<l<<" "<<r<<" "<<dp[i]<<endl; } sum[i]=(sum[i-1]+dp[i])%mod; } /*rep(i,1,n){ cout<<i<<" "<<dp[i]<<endl; }*/ printf("%lld\n",dp[n]); return 0; }
D2
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; }
参考
昨晚比赛结束了看群里的讨论，两个题本质是d p dpdp的转移方式
好有道理~
