题解：AT_abc433_f [ABC433F] 1122 Subsequence 2

· · 题解

\text{\Large{Solution}}

ABC 后朋友告诉我的范德蒙德卷积。

令 p_i 表示 1\sim i 中 a_i 的个数，q_i 表示 i\sim n 中 a_i 的个数。

枚举前半段的结尾 i 和前半段的长度 j，则答案为

ans&=\sum_{i=1}^n \sum_{j=1}^{p_i}\binom{p_i-1}{j-1}\binom{q_{i+1}}{j}\\ &=\sum_{i=1}^n \sum_{j=1}^{p_i}\binom{p_i-1}{j-1}\binom{q_{i+1}}{q_{i+1}-j}\\ &=\sum_{i=1}^n \binom{p_i+q_{i+1}-1}{q_{i+1}-1} \end{aligned}

预处理阶乘即可。

\text{\Large{Code}} 
#include <bits/stdc++.h>
#define int long long
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef pair <int, pii> piii;
const double PI = acos (-1);
const double eps = 1e-10;
const int N = 2e6 + 10, M = 2e5 + 10;
//const int mod = 1e9 + 7;
const int mod = 998244353;

int l[10], r[10];
int cntl[N], cntr[N], fac[N], ne[N][10];
int qmi(int a, int b, int p)
{
    int t = 1;
    while (b)
    {
        if (b & 1) t = t * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return t;
}

signed main()
{
    cin.tie (0);
    cout.tie (0);
    ios::sync_with_stdio (false);
    string s;
    cin >> s;
    int n = s.size ();
    s = " " + s;
    fac[0] = 1;
    for (int i = 1; i <= 2 * n; i++) fac[i] = fac[i - 1] * i % mod;
    for (int i = 1; i <= n; i++)
    {
        int x = s[i] - '0';
        cntl[i] = cntl[l[x]] + 1;
        l[x] = i;
    }
    for (int i = n; i >= 1; i--)
    {
        int x = s[i] - '0';
        cntr[i] = cntr[r[x]] + 1;
        for (int j = 0; j <= 9; j++) ne[i][j] = r[j];
        r[x] = i;
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        int x = s[i] - '0';
        if (x == 9) continue;
        ans = (ans + fac[cntl[i] + cntr[ne[i][x + 1]] - 1] * qmi (fac[cntr[ne[i][x + 1]] - 1], mod - 2, mod) % mod * qmi (fac[cntl[i]], mod - 2, mod) % mod) % mod;
    }
    cout << ans << "\n";
    return 0;
}