信息学训练营NOIP模拟题(3)-信号覆盖

摘要

    本文试题为往期清北学堂信息学训练营内部模拟测试题，仅供大家学习,如需测试数据请留言。

代码：

AC CODE

#include<cstdio>

#include<cstring>

const int MN=24,MOD=998244353;

int a[MN+5],f[2][(1<<MN)+5],v[MN+5],ps[MN+5];

void rw(int&a,int b){a+=b;if(a>=MOD)a-=MOD;}

int main()

{

freopen('heap.in','r',stdin);

freopen('heap.out','w',stdout);

int n,i,j,k,p,q,s,ans=0;

scanf('%d',&n);

for(i=1;i<=n;++i)scanf('%d',&a[i]);

for(f[p=0][q=i=1]=1;i<n;++i,p^=1,q^=1)

{

memset(f[q],0,sizeof(int)*(1<<i+1));

for(j=1;j<1<<i;++j)if(f[p][j])

{

for(s=k=0;k<i;++v[s],++k)if(j&(1<<k))ps[++s]=k;

for(k=1;k<s&&k<a[i+1];++k)

{

int t=(1<<ps[k+1]+1)-1;

rw(f[q][((j^(j&t))<<1)+(j&t)],1LL*f[p][j]*v[k]%MOD);

}

if(k<a[i+1])rw(f[q][j|(1<<i)],1LL*f[p][j]*v[s]%MOD);

memset(v,0,sizeof(int)*(s+1));

}

}

for(i=1;i<1<<n;++i)rw(ans,f[p][i]);

printf('%d',ans);

}

题解：