F - Density of subarrays
屲，平衡复杂度题
首先考虑如何求一个序列的密度
从最左端开始，找到需序列\(A[1...n]\)的最小段\(A[1...a_1]\)，使其包含\(1\sim c\)的所有颜色，然后又以\(a_1+1\)为起点，找下一个最短的包含\(1\sim c\)的所有颜色的段，最后找到的这样的段的个数就是这个序列的密度
由此也可得，一个长度为\(n\)的序列，密度最大为\(\frac nc\)
所以，就有一个显然的状压\(dp\)：设\(f[i][j][S]\)表示前\(i\)个中，已有了\(j\)个包含\(1\sim c\)的所有颜色的段，目前最后一个段包含颜色的状态为\(S\)的序列的个数，则有：
复杂度就是\(O(\frac{n^2}c\times2^c)\)
然后这个复杂度在\(c\)更大时就\(G\)了，所以考虑不用状压的另一种\(dp\)
注：下文中\(A[i]\)仅仅代表\(i\)在序列中的存在形式，若在值上\(A[j]=A[i]\)，那么在下文中\(A[j]\)也不等同\(A[i]\)
设\(f[i][j]\)表示以\(A[i]\)结尾的序列中，恰有\(j\)个包含\(1\sim c\)的所有颜色的序列的数量，考虑如何转移
设\(g[i][j]\)表示\(A[i,j]\)中，包含\(A[j]\)，且包含\(A[j]\)后恰好包含\(1\sim c\)的所有颜色的序列的数量，那么有
又设\(h[i][j]\)表示\(A[i,j]\)中，包含\(A[j]\)且不包含\(1\sim c\)的所有颜色的序列的数量
那么最后的答案就为：
最后的那个\(i>0\)表示\([i+1,n]\)里不选任何序列来接到\(f[i][j]\)后面，显然，当\(i=0\)时，\(f[i][j]\)就已经是空的了，所以若\(i=0\)时也不选，那么空的序列就会被计入答案，这是不合法的
那么\(g[i][j]\)和\(h[i][j]\)，可以枚举\(j\)，然后\(i\)从后往前枚举计算
若目前\([i,j]\)里不存在序列包含\(1\sim c\)的所有颜色，那么此时\(g[i][j]=0,h[i][j]=2^{j-i}\)
因为\(A[j]\)是必须选的
若包含\(1\sim c\)的所有颜色，那么\(g[i][j]=\prod_{1\leq k\leq c\&\&k\neq A[j]}(2^{cnt_k}-1)\)，\(h[i][j]=2^{j-i}-2^{cnt_{A[j]}-1}\times\prod_{1\leq k\leq c\&\&k\neq A[j]}(2^{cnt_k}-1)\)
其中，\(cnt_k\)表示颜色\(k\)在\([i,j]\)中出现了\(cnt_k\)次
复杂度为\(O(\frac{N^3}c)\)
然后结合这两种做法，就可以过了
#include<bits/stdc++.h>
using namespace std;
const int N=3005,MOD=998244353;
int n,c,a[N],ans[N];
void add(int &a,int b){
a+=b;
if(a>=MOD) a-=MOD;
}
void work1(){
vector<vector<vector<int>>> f(2,vector<vector<int>>(n/c+1,vector<int>(1<<c,0)));
f[0][0][0]=1; int id=0,mx=(1<<c)-1;
for(int i=1;i<=n;++i,id^=1){
for(int j=0;j<=i/c;++j) for(int s=0;s<=mx;++s) f[id^1][j][s]=f[id][j][s];
for(int j=0;j<=(i-1)/c;++j)
for(int s=0;s<mx;++s){
if(!f[id][j][s]) continue;
int nows=s|(1<<a[i]-1),nowj=j;
if(nows==mx) nows=0,++nowj;
add(f[id^1][nowj][nows],f[id][j][s]);
}
}
for(int i=0;i<=n/c;++i) for(int s=0;s<=mx;++s) add(ans[i],f[id][i][s]);
add(ans[0],MOD-1);//-empty
}
int cnt[N],sur,p2[N],inv[N],use;
void ad(int x){
if(!cnt[x]) ++cnt[x],--sur;
else{
use=1ll*use*inv[cnt[x]]%MOD;
++cnt[x];
use=1ll*use*(p2[cnt[x]]-1<0?p2[cnt[x]]-1+MOD:p2[cnt[x]]-1)%MOD;
}
}
void Init(){
for(int i=1;i<=c;++i) cnt[i]=0;
sur=c,use=1;
}
int power(int x,int y){
if(x<0) x+=MOD;
int ans=1;
for(;y;y>>=1,x=1ll*x*x%MOD) if(y&1) ans=1ll*ans*x%MOD;
return ans;
}
void work2(){
vector<vector<int>> g(n+5,vector<int>(n+5,0)),h(n+5,vector<int>(n+5,0)),f(n+5,vector<int>(n+5,0));
vector<int> sum(n+5,0);
p2[0]=use=1;
for(int i=1;i<=n;++i) p2[i]=2ll*p2[i-1]%MOD;
for(int i=1;i<=n;++i) inv[i]=power(p2[i]-1,MOD-2);
for(int j=1;j<=n;++j,Init())
for(int i=j;i;--i){
ad(a[i]);
if(sur) h[i][j]=p2[j-i];
else{
int v=1ll*use*inv[cnt[a[j]]]%MOD;
g[i][j]=v,h[i][j]=((1ll*p2[j-i]-1ll*v*p2[cnt[a[j]]-1]%MOD)%MOD+MOD)%MOD;
}
}
f[0][0]=1;
for(int i=0;i<n;++i)
for(int j=0;j<=i/c;++j)
if(f[i][j])
for(int k=i+1;k<=n;++k) f[k][j+1]=(1ll*f[k][j+1]+1ll*f[i][j]*g[i+1][k]%MOD)%MOD;
for(int i=0;i<=n;++i) for(int j=i;j<=n;++j) add(sum[i],h[i][j]);
for(int i=0;i<=n;++i)
for(int j=0;j<=i/c;++j){
if(i) add(ans[j],f[i][j]);//[i+1,n]=empty
add(ans[j],1ll*f[i][j]*sum[i+1]%MOD);
}
}
int main(){
scanf("%d%d",&n,&c);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
if(c<=10) work1();
else work2();
for(int i=0;i<=n;++i) printf("%d ",ans[i]);
return 0;
}