Noip2021 T2 series

  Portal ：NOIP2021 T2 The sequence

The main idea of the topic

  Given integer $n,m,k$, And a length of $m+1$ A positive integer array of $v_0,v_1,\dots ,v_m$.

  For a length of $n$, Subscript from $1$ Start with no more than $m$ A sequence of nonnegative integers $\{a_i\}$, We define its weight as $v_{a_1}\times v_{a_2}\times \cdots \times v_{a_n}$.

  When such a sequence $\{a_i\}$ Satisfy integer $S=2^{a_1}+2^{a_2}+\cdots +2^{a_n}$ In the binary representation of $1$ No more than $k$ when , We think $\{a_i\}$ Is a legal sequence .

  Calculate all legal sequences $\{a_i\}$ The weight sum of $998244353$ Results of die taking .

analysis

  I still vaguely remember the most violent violence in the examination room … Did you get a point qwq

#include<bits/stdc++.h>
using namespace std;
#define in read()
#define MOD 998244353
#define MAXN 202

inline int read(){
    
	int x = 0; char c = getchar();
	while(c < '0' or c > '9') c = getchar();
	while('0' <= c and c <= '9'){
    
		x = x * 10 + c - '0'; c = getchar();
	}
	return x;
}

int k = 0;
int v[MAXN] = {
     0 };
int n = 0; int m = 0;

inline int lowbit(int x){
    
	return x & -x;
}

int ans = 0;
int a[MAXN] = {
     0 };
void work(){
    
	int S = 0;
	for(int i = 1; i <= n; i++) S += pow(2, a[i]);
	int cnt1 = 0;
	while(S){
    
		S -= lowbit(S); cnt1++;
		if(cnt1 > k) return;
	}
	int temp = 1;
	for(int i = 1; i <= n; i++)
		temp = (1ll * temp * v[a[i]]) % MOD;
	ans = (1ll * ans + temp) % MOD;
}

void dfs(int now){
    
	if(now > n){
     work(); return; }
	for(int i = 0; i <= m; i++){
    
		a[now] = i;
		dfs(now + 1);
		a[now] = 0;
	}
}

int main(){
    
	n =  in; m = in; k = in;
	for(int i = 0; i <= m; i++) v[i] = in;
	dfs(1);
	cout << ans << endl;
	return 0;
}

  Okay , Now let's look at the normal solution .

  Look at this data range , $n,m$ They are all relatively small , So it should not be counting , Then consider $dp$. set up $f_{i,j,k,l}$ Indicates the current processing of $i$ position , It has been used $j$ Number , front $i$ There are $k$ individual “$1$”, And in the $i$ For rounding $l$ Time .

  Then based on this information, we enumerate the current $i$ Place $x$ individual “$1$”. We can know the number $i+1$ Is it $0$ still $1$. say concretely , We are $i$ Bit carry $l$ Time , that $i+1$ Bit is carried $\frac{l}{2}$ Time . And we let go again $x$ individual $1$, So the first $i+1$ Bits are carried in total $\lfloor \frac{l+x}{2}\rfloor$ Time . Then we can start from ：

$$f_{i,j,k,l}$$

  Transferred to the ：

$$f_{i+1,j+x,k+(\lfloor \frac{l+x}{2}\rfloor \wedge 1),\lfloor \frac{l+x}{2}\rfloor }$$

  That's how it's transferred ：

$$f_{i,j,k,l}\to f_{i+1,j+x,k+(\lfloor \frac{l+x}{2}\rfloor \wedge 1),\lfloor \frac{l+x}{2}\rfloor }$$

  Obviously, this cannot be added directly , There are also some coefficients ahead . The first obvious coefficient is $v_i^x$ This is where I am $i$ Bit plus $x$ individual $i$ Contribution to the answer , Then there is another coefficient, which is the number of schemes , That is to say, there are still $n-j$ Select from the number $x$ A for $i$ The number of solutions is $\left(\begin{array}{c}n-j\\ x\end{array}\right)$. So the transfer equation should be ：

$$f_{i+1,j+x,k+(\lfloor \frac{l+x}{2}\rfloor \wedge 1),\lfloor \frac{l}{2}\rfloor +x}=\sum f_{i,j,k,l}\times v_i^x\times \left(\begin{array}{c}n-j\\ x\end{array}\right)$$

  Then we can preprocess the combination number and be happy $dp$ La . The answer is ：

$$ans=\sum _{i=0}^n\sum _{j=0}^k[j+popcnt(i)\le k]f_{m,n,j,i}$$

  End of the flower ！！！

Code

#include<bits/stdc++.h>
using namespace std;
#define in read()
#define MAXN 50
#define MAXM 505
#define MOD 998244353

inline int read(){
    
	int x = 0; char c = getchar();
	while(c < '0' or c > '9') c = getchar();
	while('0' <= c and c <= '9'){
    
		x = x * 10 + c - '0'; c = getchar();
	}
	return x;
}

int K = 0;
int n = 0; int m = 0;
int v[MAXM][MAXN] = {
     0 };                     // v[i][j] = v_i^j
int c[MAXN][MAXN] = {
     0 };
int f[MAXM][MAXN][MAXN][MAXN] = {
     0 };

int popcnt(int x){
    
	int ans = 0;
	while(x) ans += (x & 1), x >>= 1;
	return ans; 
} 

int main(){
    
	n = in; m = in; K = in; int ans = 0;
	for(int i = 0; i <= m; i++){
    
		v[i][0] = 1; v[i][1] = in;
		for(int j = 2; j <= n; j++)
			v[i][j] = 1ll * v[i][j - 1] * v[i][1] % MOD;
	}
	c[0][0] = 1;
	for(int i = 1; i <= n; i++){
    
		c[i][0] = 1;
		for(int j = 1; j <= i; j++)
			c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % MOD;
	}
	f[0][0][0][0] = 1;
	for(int i = 0; i <= m; i++)
		for(int j = 0; j <= n; j++)
			for(int k = 0; k <= K; k++)
				for(int l = 0; l <= n >> 1; l++)
					for(int x = 0; x <= n - j; x++)
						f[i + 1][j + x][k + (l + x & 1)][l + x >> 1] = (f[i + 1][j + x][k + (l + x & 1)][l + x >> 1] + 1ll * f[i][j][k][l] * v[i][x] % MOD * c[n - j][x] % MOD) % MOD;
     for(int j = 0; j <= K; j++)
	 	for(int i = 0; i <= n >> 1; i++)
	 		if(j + popcnt(i) <= K) ans = (ans + f[m + 1][n][j][i]) % MOD;
    cout << ans << '\n';
	return 0;
}