2024牛客多校 4 （概率，带权并查集，构造）
J - Zero
题面：给出整数 \(n\) 和 \(k\) ， 一个 0 1 ? 字符串 \(s\) 。
? 有概率是 0 或是 1，且概率相等，一段区间 \([l, r]\) 的贡献这样计算：
-
这一段区间不包含 0
-
贡献为长度的 \(k\) 次方
求这个字符串 \(s\) 的期望贡献是多少？
solution：
首先应该考虑如何统计贡献，如果遍历区间，到达了复杂度 \(O(n^2)\) 复杂度。
于是自然想到统计每一位的贡献，开始想到统计第 \(i\) 位出现的所有区间的贡献，但尝试过之后发现难以实现，重点来了，计算第 \(i\) 位结尾所得的贡献。
\(dp[i]\) 表示第 \(i\) 位结尾所得的贡献 ，于是列式计算：
若子串为 ????
则 \(f[3]\) 表示为 \({\frac{1}{2}}^1 * 1^k + {\frac{1}{2}}^2 * 2^k + {\frac{1}{2}}^3 * 3^k\)
$f[4] = $ \({\frac{1}{2}}^1 * 1^k + {\frac{1}{2}}^2 * 2^k + {\frac{1}{2}}^3 * 3^k + {\frac{1}{2}}^4 * 4^k\)
自然想到如何从 \(f[3]\) 变化到 \(f[4]\) ，这个时候联想一下数组推移的样子，首先多了一项长度为 1 的，其次前面每一项都长度加 1 ，用 \(f[4]\) 减去 \(f[3]\) 可得一个简单的式子：
\[(x + 1)^k - x^k = \sum_{i = 0}^{k - 1} C_{k}^{i} * x^i \]所以发现需要计算 \(k\) 次方的答案需要用到 0 - (k - 1) 的结果，于是升级定义
定义 \(dp[i][j]\) 表示第 \(i\) 位结尾，\(k = j\) 时的贡献
细节为底层特殊情况应该需要特殊判断去赋值，然后递推公式就是：
\[dp[i][j]=\left\{\begin{aligned}dp[i-1][j] + 1 + \sum_{i = 0}^{k - 1} C_{k}^{i} * dp[i - 1][i], s[i] = 1\\ \frac 12 *(dp[i-1][j] + 1 + \sum_{i = 0}^{k - 1} C_{k}^{i} * dp[i - 1][i]), s[i] = ?\\\end{aligned}\right. \]参考代码如下：
// Created by qyy on 2024/9/13.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<int, int>
#define endl "\n"
const long long inf = 0x3f3f3f3f3f3f3f3f;
const int N = 2e5 + 10;
const long long mod = 998244353;
int n, k;
ll dp[N][32];
string s;
ll fast_pow(ll a, ll n){
ll ans = a % mod;
while(n){
if(n & 1){
ans = (ans * a) % mod;
}
a = (a * a) % mod;
n >>= 1;
}
return ans;
}
ll inv(ll x){
return fast_pow(x, mod - 2);
}
ll C[50][50];
ll cal(int beg, int ed){
if(beg > ed){
return 0;
}
int len = ed - beg + 1;
for(int i = 0; i <= len; i++){
for(int j = 0; j <= 30; j++){
dp[i][j] = 0;
}
if(i != 0){
dp[i][0] = 1;
}
}
ll ans = 0;
if(s[beg] == '?'){
dp[1][0] = inv(2);
}else{
dp[1][0] = 1;
}
for(int j = 1; j <= k; j++){
dp[1][j] = dp[1][j - 1];
}
for(int j = 0; j <= k; j++){
for(int i = 2; i <= len; i++){
int pos = beg + i - 1;
ll res = 1;
for(int x = 0; x < j; x++){
ll tmp = C[j][x] * dp[i - 1][x];
res = (res + tmp) % mod;
}
res = (res + dp[i - 1][j]) % mod;
if(s[pos] == '?'){
dp[i][j] = (res * inv(2)) % mod;
}else{
dp[i][j] = res;
}
}
}
for(int i = 1; i <= len; i++){
ans = (ans + dp[i][k]) % mod;
}
return ans;
}
void solve() {
cin >> n >> k;
cin >> s;
for(int i = 1; i <= 40; i++){
C[i][0] = C[i][i] = 1;
for(int j = 1; j < i; j++){
C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
}
}
s.push_back('0');
int len = s.size();
int beg = 0, ed = 0;
ll ans = 0;
for(int i = 0; i < len; i++){
if(s[i] == '0'){
ed = i - 1;
ans = (ans + cal(beg, ed)) % mod;
beg = i + 1;
}
}
cout << ans % mod << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t = 1;
//cin >> t;
while (t--) {
solve();
}
return 0;
}