Preface & emo

I didn't preprocess the combination number to cause \ (100 - > 85 \).

A thousand year old NOIP2021 T2.

Official data and results were not available at the time of writing this explanation. If you fall into disrepute because of this \ (15pts \), you really don't know how to face your future OI career.

Problem solving ideas

I'll follow the thinking process in my examination room.

Consider DP. (the counting class is either a combined number or a DP)

We define a four-dimensional state \ (f_{i,j,k,q} \) to indicate that the number of \ (I \) has been filled in and \ (v_{1...j} \) has been considered. At this time, there are \ (k \) \ (1 \) under the \ (S \) binary, and \ (q \) assigned \ (a_i \) takes \ (j \), and the sum of weights when \ (q\geq 1 \).

We found that this state is not well transferred because we cannot transfer \ (k \) through \ (q \). The question is, how to calculate \ (k \)?

For example, we now take \ (x \) \ (2^y \), so if \ (2^i \ operatorname {\ &} x > 0 \) is equivalent to a \ (1 \) contribution on the \ (y+i \) bit of \ (S \) under binary, so the contribution to \ (k \) is \ (\ operatorname{popcnt}(x) \)\ (\ operatorname{popcnt}(x) \) indicates the number of digits of \ (x \) in binary \ (1 \). In other words, if we only consider the number of \ (1 \) under \ (S \) binary, taking \ (x \) \ (2^i \) is equivalent to taking \ (\ lfloor \frac{x}{2^{j-i}}\rfloor \) \ (2^j \). In other words, the last few digits may have an impact on the front. We can change the status to this:

The four-dimensional state \ (f_{i,j,k,q} \) indicates that the number of \ (i \) has been filled and \ (v_{1...j} \) has been considered. At this time, there are \ (k \) \ (1 \) under the binary of \ (S \). If the number after \ (j \) is not considered, it is equivalent to taking \ (q \) \ (j \), and at least one of them takes \ (j \).

This is a good transfer. We have the transfer equation:

How to understand this equation\ (x \) indicates how many numbers have taken \ (j \), \ (p \) is the last number taken by itself. Because we want to go back to the previous state, our \ (K \) will change. We have reduced the number of \ (x \) and will not affect \ (1 \) on the lower order, so \ (k'=k-\operatorname{popcnt}(q)+\operatorname{popcnt}(q-x) \). And \ (tmp \) is the equivalent number of \ (p \).

We can easily find that the complexity of this code is about \ (O(n^5m^2) \). But I'm not satisfied. In fact, only \ (50pts \) can run seriously.

Considering optimization, we redefine the state as follows:

The four-dimensional state \ (f {i, j, k, q} \) indicates that the number of \ (i \) has been filled in and \ (V {1... j} \) has been considered. At this time, there are \ (k \) \ (1 \) under the binary of \ (S \). If the number after \ (j \) is not considered, it is equivalent to taking \ (q \ (j \) and taking \ (j \) without any.

In this way, we can stop enumerating \ (p \). The equation is as follows:

There are only two values for \ (tmp \). In this way, our complexity becomes \ (O(2n^4m) \).

Seems to pass?

That's what I thought in the examination room.

In fact, without preprocessing \ (\ operatorname{popcnt} \) and combination number, three TLE points will be.

It's just a matter of preprocessing. I hate you for thousands of years....

code

#include<bits/stdc++.h>
using namespace std;

const int MAXN=33,MAXM=100+10,MOD=998244353;

int n,m,k;
long long f[MAXN][MAXM][MAXN][MAXN];
bool vis[MAXN][MAXM][MAXN][MAXN];
long long pop[MAXM],jc[MAXM],v[MAXM],c[MAXN][MAXN];

long long qpow(long long x,int y) {
	long long ret=1;
	while(y) {
		if(y&1) {
			ret=ret*x%MOD;
		}
		y>>=1;
		x=x*x%MOD;
	}
	return ret;
}
long long inv(int x) {
	return qpow(x,MOD-2);
}

long long C(int n,int m) {
	return jc[n]*inv(jc[m])%MOD*inv(jc[n-m])%MOD;
}

long long dp(int i,int j,int k,int q) {
	if(k<0||i<0||j<0||q<0) {
		return 0ll;
	}
	if(vis[i][j][k][q]) {
		return f[i][j][k][q];
	}
	if(i==0) {
		if(q==0&&k==0) {
			return 1ll;
		}
		return 0ll;
	}
	if(j==0) {
		return 0ll;
	}
	if(q>i) {
		return 0ll;
	}
	long long ans[MAXN]={},sum=0;
	for(int x=0;x<=q;x++) {
		for(int t=(q-x)*2;t<(q-x+1)*2&&t<=i-x;t++) {
			ans[x]=(ans[x]+dp(i-x,j-1,k-pop[q]+pop[q-x],t))%MOD;
		}
	}
	for(int x=0;x<=q;x++) {
		ans[x]=ans[x]*c[i][x]%MOD;
		sum=(sum+ans[x]*qpow(v[j],x)%MOD)%MOD;
	}
	vis[i][j][k][q]=1;
	return f[i][j][k][q]=sum;
}

int pop_c(int x) {
	int ret=0;
	while(x) {
		if(x&1) {
			ret++;
		}
		x>>=1;
	}
	return ret;
}

int main() {
	
	cin>>n>>m>>k;
	m++;
	for(int i=1;i<=m;i++) {
		scanf("%lld",&v[i]);
	}
	jc[0]=1;
	for(int i=1;i<=n;i++) {
		pop[i]=pop_c(i);
		jc[i]=jc[i-1]*i%MOD;
	}
	for(int i=1;i<=n;i++) {
		for(int x=0;x<=i;x++) {
			c[i][x]=C(i,x);
		}
	}
	
	long long ans=0;
	for(int t=0;t<=k;t++) {
		for(int i=0;i<=n;i++) {
			ans=(ans+dp(n,m,t,i))%MOD;
		}
	}
	
	cout<<ans<<endl;
	
}

summary

This problem solution is finished! It took me 1.5h to see here. Don't you like it qwq.

Let's continue to cheer for the provincial election. There is still a chance to reverse the world!