首先可以发现，有值的p最大是n/c

对于密度为p，每个数至少出现c次，且其实是每出现c个数，就分成一段，这样贪心就得到了p

n/c

考虑对c进行讨论

c比较大的时候：

dp[i][j]，i开头到末尾的子序列中，密度为j的数量。

枚举最后出现的数的出现位置k，f[i][k]表示[i,k]区间取子序列，使得k位置的数是最后一个出现的数（且出现一次）

dp数组的转移？

加一堆剪枝：见代码；

 

对于c较小的时候

考虑直接状压最后一段出现的数，而不是进行枚举k

dp[i][j][s]表示，前i个，分了j段，最后一段出现的数字集合是s

这样，当s|(1<<(a[i+1]-1])是全集的时候，直接转移到dp[i+1][j+1][0]

这样，当c很小的时候，1<<c就小于n了，暴力二就跑的比暴力一快了

#include
     
      #define reg register int#define il inline#define fi first#define se second#define mk(a,b) make_pair(a,b)#define numb (ch^'0')#define pb push_back#define solid const auto &#define enter cout<
      
       using namespace std;typedef long long ll;template
       
        il void rd(T &x){    char ch;x=0;bool fl=false;while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);(fl==true)&&(x=-x);}template
        
         il void output(T x){
   if(x/10)output(x/10);putchar(x%10+'0');}template
         
          il void ot(T x){
   if(x<0) putchar('-'),x=-x;output(x);putchar(' ');}template
          
           il void prt(T a[],int st,int nd){ for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}namespace Modulo{const int mod=998244353;int ad(int x,int y){ return (x+y)>=mod?x+y-mod:x+y;}void inc(int &x,int y){x=ad(x,y);}int mul(int x,int y){ return (ll)x*y%mod;}void inc2(int &x,int y){x=mul(x,y);}int qm(int x,int y=mod-2){ int ret=1;while(y){ if(y&1) ret=mul(x,ret);x=mul(x,x);y>>=1;}return ret;}template
           
            il int ad(const int a,const int b,const Args &...args) { return ad(ad(a,b),args...);}template
            
             il int mul(const int a,const int b,const Args &...args) { return mul(mul(a,b),args...);}}using namespace Modulo;namespace Miracle{const int N=3003;int n,c;int a[N];namespace sol1{int f[N][N];int dp[N][303],s[N][303];int cnt[N];int mi[N];int iv[N];// int ans[N];void main(){ mi[0]=1; for(reg i=1;i<=n;++i) mi[i]=mul(mi[i-1],2); for(reg i=0;i<=n;++i) iv[i]=qm(mi[i]-1); for(reg i=1;i<=n;++i){ memset(cnt,0,sizeof cnt); int val=1,exi=0; for(reg j=i;j<=n;++j){ if(a[j]==a[i]){ if(!cnt[a[i]]) ++exi,++cnt[a[i]]; else{ ++cnt[a[i]]; val=ad(val,val); } }else{ if(!cnt[a[j]]) ++exi,++cnt[a[j]]; else{ val=mul(val,iv[cnt[a[j]]]); ++cnt[a[j]]; val=mul(val,mi[cnt[a[j]]]-1); } } if(a[i]!=a[j]&&exi==c){ f[i][j]=mul(val,iv[cnt[a[j]]]); } } } dp[n+1][0]=1; s[n+1][0]=1; for(reg i=n;i>=1;--i){ int sum=0; for(reg j=1;j<=(n-i+1)/c;++j){ for(reg k=i+c-1;k<=n&&s[k+1][j-1];++k){ inc(dp[i][j],mul(f[i][k],s[k+1][j-1])); } inc(sum,dp[i][j]); s[i][j]=ad(s[i+1][j],dp[i][j]); } dp[i][0]=ad(mi[n-i],mod-sum); s[i][0]=ad(s[i+1][0],dp[i][0]); } --s[1][0]; for(reg i=0;i<=n/c;++i){ ot(s[1][i]); } for(reg i=n/c+1;i<=n;++i){ printf("0 "); }}}namespace sol2{int dp[2][N][1<<10];void main(){ int tmp=0; dp[0][0][0]=1; int lim=(1<
            
           
          
         
        
       
      
     

发现性质，根据c暴力讨论

加一堆剪枝。