记录编号	596677	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2021]数列	最终得分	100
用户昵称	小金	是否通过	通过
代码语言	C++	运行时间	0.666 s
提交时间	2024-11-04 15:51:44	内存使用	8.32 MiB

#include<bits/stdc++.h>
using namespace std;
const long long mod=998244353;
long long ans,v[105],dp[105][35][35][16],pv[105][35];
long long C[35][35];
int n,m,k;
void chu(int n) 
{
	for(int i=0;i<=n;i++) 
    {
       C[i][0]=1; 
    }
	for(int i=1;i<=n;i++)
	{
	    for(int j=1;j<=i;j++)
        {
            C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
        } 
    }	
}
int q(int n) 
{
	int res=0;
	while(n)
    {
        res+=n&1;
        n>>=1;
    } 
	return res;
}
int main() 
{
	freopen("2021sequence.in","r",stdin);
	freopen("2021sequence.out","w",stdout);
	chu(30);
	scanf("%d%d%d",&n,&m,&k);
	for(int i=0;i<=m;i++) 
    {
		scanf("%lld",&v[i]);
		pv[i][0]=1;
		for(int j=1;j<=n;j++)
        {
            pv[i][j]=pv[i][j-1]*v[i]%mod;
        } 
	}
	dp[0][0][0][0]=1;
	for(int i=0;i<=m;i++)
	{
	    for(int j=0;j<=n;j++)
	    {
	        for(int x=0;x<=k;x++)
	        {
	            for(int p=0;p<=n>>1;p++)//x最大为n 
	            {
	                for(int t=0;t<=n-j;t++)
                    {
                        dp[i+1][j+t][x+(t+p&1)][t+p>>1]=(dp[i+1][j+t][x+(t+p&1)][t+p>>1]+dp[i][j][x][p]*pv[i][t]%mod*C[n-j][t]%mod)%mod;
                    } 
                }		
            }	
        }		
    }	
	for(int x=0;x<=k;x++)
	{
	    for(int p=0;p<=n>>1;p++)
	    {
	        if(x+q(p)<=k) ans=(ans+dp[m+1][n][x][p])%mod;
        }
    }	
	printf("%lld",ans);
	return 0;
}