NC231397. [NOIP2021]数列（sequence）
描述
当这样的序列 满足整数
的二进制表示中
的个数不超过
时，我们认为
是一个合法序列。
计算所有合法序列 的权值和对
取模的结果。
输入描述
输入的一行是三个整数
。
第二行
个整数，分别是
。
输出描述
仅一行一个整数，表示所有合法序列的权值和对
取模的结果。
示例1
输入:
5 1 1 2 1
输出:
40
说明:
由于C++(g++ 7.5.0) 解法, 执行用时: 109ms, 内存消耗: 14364K, 提交时间: 2023-07-31 20:28:44
#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
ll ans, v[105], dp[105][35][35][16], pv[105][35];
ll C[35][35];
inline void init(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;
}
inline int popcnt(int n) {
int res = 0;
while (n) res += n & 1, n >>= 1;
return res;
}
int main() {
init(30);
int n, m, K;
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 k = 0; k <= K; k++)
for (int p = 0; p <= n >> 1; p++)
for (int t = 0; t <= n - j; t++) 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] * pv[i][t] % mod
* C[n - j][t] % mod) % mod;
for (int k = 0; k <= K; k++)
for (int p = 0; p <= n >> 1; p++)
if (k + popcnt(p) <= K) ans = (ans + dp[m + 1][n][k][p]) % mod;
printf("%lld", ans);
return 0;
}
C++(clang++ 11.0.1) 解法, 执行用时: 120ms, 内存消耗: 35232K, 提交时间: 2023-08-03 15:05:11
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=40,M=110,mod=998244353;
int n,m,K;
ll f[M][N][N][N],v[M],pv[M][N],c[N][N];
void init() {
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;
}
inline int popcount(int x) {
int res = 0;
while (x) res += x & 1, x >>= 1;
return res;
}
int main() {
cin>>n>>m>>K;
init();
for(int i=0;i<=m;i++) {
cin>>v[i];pv[i][0]=1;
for(int j=1;j<=n;j++) pv[i][j]=pv[i][j-1]*v[i]%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 p=0;p<=n>>1;p++)
for(int t=0;t<=n-j;t++)
f[i + 1][j + t][k + (t + p & 1)][t + p >> 1] = (f[i + 1][j + t][k + (t + p & 1)][t + p >> 1] + f[i][j][k][p] * pv[i][t] % mod * c[n - j][t] % mod) % mod;
}
ll ans=0;
for (int k = 0; k <= K; k++)
for (int p = 0; p <= n >> 1; p++)
if (k + popcount(p) <= K) ans = (ans + f[m + 1][n][k][p]) % mod;
cout<<ans<<endl;
return 0;
}