P11030 『DABOI Round 1』Blessings Repeated

· · 题解

或许更好的阅读体验。

题意：

给定一个正整数 k 和两个字符串 S,T。

设字符串 s 为 k 个字符串 S 首尾相接得到的字符串。

求 s 中有多少个子序列为 T。

0 < k \le 10^{18}, 0 < |S| \le 5 \times 10^3, 0 < |T| \le 10

思路：

考虑 T 在 s 中作为子序列出现的形式，可以看作是将 T 切成若干段，放到这 k 个 S 中分别出现。

此时注意到 T 的长度很小，于是考虑暴力 O(2^{|T|}) 去爆搜所有 T 的切割方案，设当前爆搜的是 [l_1 = 1, r_1], \cdots, [l_m, r_m= |T|]；此时令 f_{l, r} 表示 T[l : r] 在 S 中作为子序列出现的次数，最后再算上把这切开的 m 个段放入 k 个 S 中的方案数，那么此时这个分段的贡献是：

\binom{k}{m} \prod_{i = 1}^m f_{l_i, r_i}

求 f_{l, r} 是简单的，直接 dp 即可。

时间复杂度为 O(|T| 2^{|T|} + |T|^3 |S|)。

显然可以对分段方式进行 dp，做到 poly，但是这题没必要了。

link

完整代码：

#include<bits/stdc++.h>
#define ls(k) k << 1
#define rs(k) k << 1 | 1
#define lowbit(x) x & (-x)
#define fi first
#define se second
#define popcnt(x) __builtin_popcount(x)
#define open(s1, s2) freopen(s1, "r", stdin), freopen(s2, "w", stdout);
using namespace std;
typedef __int128 __;
typedef long double lb;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
bool Begin;
const int N = 5e3 + 10, M = 11, mod = 998244353;
inline ll read() {
    ll x = 0, dp = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-')
            dp = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * dp;
}
inline void write(ll x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
ll k;
int n, m, ans;
int dp[M], C[M];
int f[M][M];
char s[N], t[N];
inline int qpow(int a, int b){
    int ans = 1;
    while(b){
        if(b & 1)
          ans = 1ll * ans * a % mod;
        a = 1ll * a * a % mod;
        b >>= 1;
    }
    return ans;
}
vector<pair<int, int>> V;
inline int solve(){
    int sum = 1;
    for(auto t : V)
        sum = 1ll * f[t.fi][t.se] * sum % mod;
    return 1ll * sum * C[(int)V.size()] % mod;
}
inline void dfs(int pos, int lst){
    if(pos == m + 1){
        ans = (ans + solve()) % mod;
        return ;
    }
    if(pos == m){
        V.push_back({lst, m});
        dfs(pos + 1, m + 1);
        V.pop_back();
    }
    else{
        V.push_back({lst, pos});
        dfs(pos + 1, pos + 1);
        V.pop_back();
        dfs(pos + 1, lst);
    }
}
int main() {
    k = read();
    scanf("%s", s + 1);
    scanf("%s", t + 1);
    n = strlen(s + 1), m = strlen(t + 1);
    C[0] = 1, C[1] = k % mod;
    for(int i = 2; i <= m; ++i){
        C[i] = 1ll * (k % mod - i + 1 + mod) % mod * qpow(i, mod - 2) % mod * C[i - 1] % mod;
//      cerr << C[i] << ' ';
    }
//  cerr << '\n';
    for(int l = 1; l <= m; ++l){
        for(int r = l; r <= m; ++r){
            memset(dp, 0, sizeof(dp));
            dp[0] = 1;
            for(int i = 1; i <= n; ++i)
              for(int j = r; j >= l; --j)
                if(t[j] == s[i])
                  dp[j - l + 1] = (dp[j - l + 1] + dp[j - l]) % mod;
            f[l][r] = dp[r - l + 1];
        }
    }
    dfs(1, 1);
    write(ans);
    return 0;
}