[luogu8340]山河重整

记$S$中的元素依次为$a_{1}

结论：$S$合法当且仅当$\begin{cases}\sum_{i=1}^{k}a_{i}\ge n&(1)\\\forall i\in [1,k],\sum_{j=1}^{i-1}a_{j}+1\ge a_{i}&(2)\end{cases}$

必要性：若$(1)$不满足则无法得到$n$，若$(2)$不满足则无法得到$\sum_{i=1}^{j-1}a_{j}+1$

充分性：对于$x\in [1,n]$，从后往前枚举$i$并在$x\ge a_{i}$时将$x$减去$a_{i}$，归纳$x\le \sum_{j=1}^{i}a_{j}$即可

推论：$S$合法当且仅当$\forall x\in [1,n],S$中$\le x$的元素和$\ne x-1$

必要性：若$S$中存在$x$的后继$a_{i}$则$\sum_{j=1}^{i-1}a_{j}+1=x

充分性：若$(1)$不满足则取$x=\sum_{i=1}^{k}a_{i}+1$，若$(2)$不满足则取$x=\sum_{j=1}^{i-1}a_{j}+1$

枚举最小的$x$（不满足条件），记对应的方案数为$f_{x}$，则转移即
$$
f_{x}=\{[1,x]子集和为x-1的方案数\}-\sum_{x'=1}^{x-1}\{(x',x]子集和为x-x'的方案数\}f_{x'}
$$
另外，答案为$2^{n}-\sum_{x=1}^{n}2^{n-x}f_{x}$

关于前者，变形得$\sum_{i=1}^{k}a_{i}=\sum_{i=1}^{k}(a_{i}-a_{i-1})(k-i+1)$，且两者一一对应

记$g_{s}$为$\sum_{i=1}^{k}i\cdot x_{i}=s$的解数（其中$x_{i}\ge 0$且非0的$x_{i}$构成前缀），则方案数也即$g_{x}$

注意到$k\le \sqrt{2s}$，倒序枚举$k$并对$g$做完全背包（对每个$k$均设初值$g_{0}=1$），时间复杂度为$o(n\sqrt{n})$

关于后者，可以看作每次设初值为$g_{x'+kx'}=f_{x'}$时的结果，并根据$x'\le \lfloor\frac{x}{2}\rfloor$分治即可

总复杂度为$o(n\sqrt{n})$，可以通过

 1 #include
 2 using namespace std;
 3 #define N 500005
 4 #define ll long long
 5 int n,mod,ans,pw[N],g[N],f[N];
 6 void add(int &x,int y){
 7     x+=y;if (x>=mod)x-=mod;
 8 } 
 9 void solve(int n){
10     if (n==1)return;
11     solve(n>>1);
12     memset(g,0,sizeof(g));
13     for(int i=(int)sqrt(n<<1);i;i--){
14         for(int j=1,s=i+1;(j<=(n>>1))&&(s<=n);j++,s+=i+1)add(g[s],f[j]);
15         for(int j=n;j>=0;j--)g[j]=(j0 : g[j-i]);
16         for(int j=i;j<=n;j++)add(g[j],g[j-i]);
17     }
18     for(int i=(n>>1)+1;i<=n;i++)f[i]=(f[i]-g[i]+mod)%mod;
19 }
20 int main(){
21     scanf("%d%d",&n,&mod);
22     pw[0]=1;
23     for(int i=1;i<=n;i++)pw[i]=(pw[i-1]<<1)%mod;
24     for(int i=(int)sqrt(n<<1);i;i--){
25         g[0]=1;
26         for(int j=n;j>=0;j--)g[j]=(j0 : g[j-i]);
27         for(int j=i;j<=n;j++)add(g[j],g[j-i]);
28     }
29     for(int i=1;i<=n;i++)f[i]=(i==1 ? 1 : g[i-1]);
30     ans=pw[n],solve(n);
31     for(int i=1;i<=n;i++)ans=(ans-(ll)pw[n-i]*f[i]%mod+mod)%mod;
32     printf("%d\n",ans);
33     return 0;
34 }