题目描述：
给出一个大小为 \(N\) 的可重集 \(A=\lbrace\ A_1,A_2,\dots,A_N\ \rbrace\)。
你可以执行若干次如下操作（也可以不执行）。
- 将两个 \(x\) 合并成一个 \(x+1\)。
输出最终可能的集合个数对 \(998244353\) 取模的结果。
数据范围：
\(1\le N\le 2\times 10^5\)
\(1\le Q\le 2\times 10^5\)
思路：
实话实说，我觉得这个题其实没有那么好做。
首先一开始我就犯了一个审题错误：我误以为是必须两个相邻的才能合并
然后我们回归正题。思考这个题目中的这个问题该怎么处理。
我们发现，似乎当前这轮的个数只与上一轮的有关系，所以我们考虑令 \(dp_{i,j}\) 表示当前枚举到了 \(i\) 这个数，并且有 \(j\) 个 \(i\) 存在的序列的个数
然后转移也是简单的 \(dp_{i,j+a_i}=\sum\limits_{k=2\times j}^{lst}dp_{i-1,k}\) 其中 \(lst\) 表示上一轮最多有多少的 \(i-1\)
然后我们对这个式子进行一个变形，使其变得好看一点 \(dp_{i,j'}=\sum\limits_{k=2\times (j-a_i)}^{lst}dp_{i-1,k}\)
这样我们就可以使用后缀和优化这个式子了。
最后需要注意的是，因为最后的 \(mx\) 最终最多拥有 \(\log_2 n\) 的个数，所以需要增加 \(\log_2 n\) 次循环。
然后我们分析一下复杂度：
首先空间复杂度可以通过滚动数组优化到 \(O(N)\)
时间复杂度比较奇怪，他应该是类似于 \(n\times \left( 1+\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\cdots \right)\le 2\times n\)
所以时间复杂度 \(O(2n)\) 左右。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=2e6+5;
const int mod=998244353;
const int inf=0x3f3f3f3f;
int n;
int a[maxn];
int bul[maxn],sum[maxn],dp[maxn];
signed main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i],bul[a[i]]++;
int mn=n,mx=0;
for(int i=1;i<=n;i++)mn=min(mn,a[i]),mx=max(mx,a[i]);
int lst=bul[mn];
for(int i=lst;i>=0;i--)sum[i]=1;
for(int i=mn+1;i<=mx+20;i++){
lst=bul[i]+lst/2;
for(int j=0;j<bul[i];j++)dp[j]=0;
for(int j=bul[i];j<=lst;j++)dp[j]=sum[(j-bul[i])*2];
sum[lst]=dp[lst];
for(int j=lst-1;j>=0;j--)sum[j]=(sum[j+1]+dp[j])%mod;
}
cout<<sum[0]<<endl;
return 0;
}