做题记录整理dp12 P7961 [NOIP2021] 数列（2022/9/26）

P7961 [NOIP2021] 数列
当时在考场上对于拿部分分这个感念不是很清晰，所以当时连暴力分都没拿。。。

事实上这题在看了题解之后还是有很多地方没搞明白，比如最后统计答案，为什么从0开始

不过可以学习到组合数的预处理

等之后再把重新这题做一遍（当然，考场上肯定做不出来）

#include<bits/stdc++.h>
#define for1(i,a,b) for(int i = a;i<=b;i++)
#define ll long long
#define mp(a,b) make_pair(a,b)
using namespace std;
ll ans, a[105], dp[105][35][35][16], pf[105][35];
int n,m,K;
ll c[35][35];
const ll md= 998244353;
void yu() 
{
	for1(i,0,30)c[i][0]=1;
	for1(i,1,30)
		for1(j,1,i)
		    c[i][j]=(c[i-1][j]+c[i-1][j-1])%md;
}

int cl(int x)
{
	int cnt=0;
	while(x)
	{
	    cnt+=x&1;
	    x>>=1;
	}
	return cnt;
}

int main()
{
	yu();
	scanf("%d%d%d",&n,&m,&K);
	for1(i,0,m)
	{
		scanf("%lld",&a[i]);
		pf[i][0]=1;
		for1(j,1,n) pf[i][j]=pf[i][j-1]*a[i]%md;
	}
	dp[0][0][0][0]=1;
	for1(i,0,m)//前i位 
		for1(j,0,n)//确定了j个 
			for1(k,0,K)//有k个1 
				for1(p,0,j>>1)//下一位的进位 
					for1(t,0,n-j)//这一a中有t个i 
					    dp[i+1][j+t][k+(t+p&1)][t+p>>1]=
						(dp[i+1][j+t][k+(t+p&1)][t+p>>1]+dp[i][j][k][p]*pf[i][t]%md*c[n-j][t]%md)%md;
	for1(k,0,K)
    	for1(p,0,n>>1)
			if(k+cl(p)<=K) 
			    ans=(ans+dp[m+1][n][k][p])%md;
	printf("%lld",ans);
	return 0;
}