首先容易得到 \(O(n^2)\) 的解法,容易观察得出任意时刻范围都应是 \([1,\sum]\) 否则直接寄了。
考察 \(i\) 使得 \([1,i]\) 都能凑出但 \(i+1\) 不行。则有 \(\sum\limits_{a_x\leqslant i}a_x=i\),令 \(f_i\) 表示其方案数。
可以考虑总方案减去不可行的方案,而不可行的方案可以依据更小的 \(f\) 求出。
考察这种最多只能加 \(\sqrt n\) 的背包,其实就是对每个 \(i\in [1,\sqrt n]\) 对 \(\sum [a_x\geqslant i]\) 做完全背包。
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+10;
#define inf 1e9
inline int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
int n,mod,dp[maxn],ans,pw[maxn],f[maxn];
inline void add(int &x,int y){x=(x+y>=mod?x+y-mod:x+y);}
inline void solve(int n){
if(n<=1)return;solve(n/2);
for(int i=0;i<=n;i++)f[i]=0;
int lim=sqrt(2*n);
for(int i=lim;i>=1;i--){
for(int j=n;j>i;j--)f[j]=f[j-i];
for(int j=i;j>=1;j--)f[j]=0;
for(int j=0;j+(j+2)*i<=n;j++)add(f[j+(j+2)*i],dp[j]);
for(int j=i;j<=n;j++)add(f[j],f[j-i]);
}for(int i=n/2+1;i<=n;i++)add(dp[i],mod-f[i]);
}
int main(){
n=read(),mod=read();
dp[0]=pw[0]=1;
for(int i=1;i<=n;i++)
pw[i]=(pw[i-1]+pw[i-1])%mod;
int lim=sqrt(2*n);
for(int i=lim;i>=1;i--){
for(int j=n;j>i;j--)dp[j]=dp[j-i];
for(int j=i;j>=1;j--)dp[j]=0;
for(int j=i;j<=n;j++)add(dp[j],dp[j-i]);
}solve(n);
for(int i=0;i<n;i++)
ans=(ans+1ll*dp[i]*pw[n-i-1])%mod;
ans=(pw[n]-ans+mod)%mod;
printf("%d\n",ans);
return 0;
}
深深地感到自己的弱小。
标签:山河,int,题解,sum,--,AHOI2022,dp,getchar From: https://www.cnblogs.com/syzf2222/p/16868563.html