洛谷P9149 串串题题解

题意：

给定长度分别为 $n,m$ 的整数序列 $A,B$ 和常数 $W,d$，序列从 $1$ 开始标号，保证 $A_i,B_i \in [1,W]$。

容易发现，我们有 $\binom{W}{d}$ 种方案选择 $[1,W]$ 中的 $d$ 个互不相同的整数。

对于每一种选择的方案，我们删去 $A$ 中出现的对应的 $d$ 种整数，令此时序列 $B$ 在序列 $A$ 中的出现次数为这次选择方案的权值。

你需要求所有的选择方案的权值和，对 ${10}^9+7$ 取模。

若对题意有疑问，请阅读样例及样例解释。

注：$\binom{a}{b}$ 表示组合数，含义为在 $a$ 个物品中无序地选择出 $b$ 个物品的方案数。

请注意：我们并不会删除序列 $\mathbf{B}$ 中出现的对应整数。

输入格式：

本题有多组数据。

第一行，一个正整数 $T$，表示数据组数。对于每组数据：

第一行，四个正整数 $n, m, W, d$，保证 $d \le W$。

第二行，$n$ 个正整数 $A_1, A_2, \ldots, A_n$，表示序列 $A$。

第三行，$m$ 个正整数 $B_1, B_2, \ldots, B_m$，表示序列 $B$。

输出格式：

对于每组数据，输出一个整数表示答案对 ${10}^9+7$ 取模的结果。

数据范围：

对于 $100\%$ 的数据，$1 \le n,m,W \le {10}^6$，$1 \le d, A_i, B_j \le W$，$1 \le T \le 5$。

考虑计算每个可能位置在所有方案下匹配上 $B$ 的次数和。

假设 $A$ 数组内 $[l,r]$ 位置的数字在删数之后变成了一个 $B$ （$l$ 和 $r$ 位置上的数没有被删）

容易发现，妨碍形成一个匹配的元素一定会被删除，或者说 $[l,r]$ 中出现的不在 $B$ 的元素一定会被删掉。

考虑枚举 $l$ 的值。一个 $l$ 是合法的当且仅当在删除所有不在 $B$ 内的元素后，$[l,r]$ 剩下的元素恰好为 $B$ 。

因此我们可以先把所有不在 $B$ 内的元素删掉，然后跑一遍 kmp 得到合法的 $l$ （顺便能计算出 $r$ ）

接着统计在 $[l,r]$ 区间里出现了多少种不在 $B$ 内的元素，不妨记为 $a$ ，并记 $B$ 内出现的元素有 $b$ 种

由于出现在 $B$ 的元素一定不能删，在 $[l,r]$ 里且未出现在 $B$ 的一定要删，其他的可删可不删，那么贡献即为

$\Delta = \binom{W-a-b}{d-a}$

也就是我们要在剩下的 $W-a-b$ 个数里面选 $d-a$ 个数删（不管怎么删 $[l,r]$ 都能出现一个匹配）

容易发现，随着 $l$ 的增长，$r$ 也是单调的。每次 $l$ 增大后我们维护 $r$ 的值，并统计 $[l,r]$ 内每个元素的出现次数

时间复杂度 $\mathcal{O}(W + \sum n_i)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int mod = 1e9 + 7;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
void add(int &x,int y) { (x += y) >= mod ? x -= mod : 0; }
#define N ((int)(1e6 + 15))

const int o = 1e6;
int fac[N],inv[N];
int qpow(int a, int b)
{
    int r = 1;
    while(b) {
        if(b & 1) r = r * a % mod;
        b >>= 1; a = a * a % mod;
    }
    return r;
}
int C(int n, int m)
{
    if(n < 0 || m < 0 || n - m < 0) return 0;
    return fac[n] * inv[m] % mod * inv[n - m] % mod;
}
int n,m,W,D,a[N],b[N],c[N],d[N],x[N],y[N],L[N],R[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    fac[0] = inv[0] = 1;
    for(int i = 1; i <= o; i++) fac[i] = fac[i - 1] * i % mod;
    inv[o] = qpow(fac[o], mod - 2);
    for(int i = o - 1; i; i--) inv[i] = inv[i + 1] * (i + 1) % mod;
    int Q; for(cin >> Q; Q--; )
    {
        cin >> n >> m >> W >> D; int t = 0, val = 0, res = 0;
        for(int i = 1; i <= n; i++) cin >> a[i];
        for(int i = 1; i <= m; i++) { cin >> b[i]; val += !x[b[i]]; x[b[i]] = true; }
        for(int i = 1; i <= n; i++) { c[i] = d[i] = L[i] = R[i] = 0; }
        for(int i = 1; i <= n; i++) if(x[a[i]]) { c[++t] = a[i], d[t] = i; }
        L[1] = 0; a[n + 1] = b[m + 1] = 0;
        for(int i = 2; i <= m; i++)
        {
            int p = L[i - 1];
            for(; p && b[p + 1] != b[i]; p = L[p]);
            if(b[p + 1] == b[i]) L[i] = p + 1; else L[i] = 0;
        }
        for(int i = 1; i <= t; i++)
        {
            int p = R[i - 1];
            for(; p && b[p + 1] != c[i]; p = L[p]);
            if(b[p + 1] == c[i]) R[i] = p + 1; else R[i] = 0;
        }
        int l = 1, r = 0, ans = 0;
        for(int i = 1; i <= t; i++) if(R[i] == m)
        {
            int y0 = d[i], x0 = d[i - m + 1];
            for(; r < y0; ) {
                ++r; if(!x[a[r]] && y[a[r]] == 0) ++ans;
                if(!x[a[r]]) ++y[a[r]];
            }
            for(; l < x0; ++l) {
                if(!x[a[l]]) --y[a[l]];
                if(!x[a[l]] && y[a[l]] == 0) --ans;
            }
            add(res, C(W - val - ans, D - ans));
        }
        for(int i = 1; i <= m; i++) x[b[i]] = 0;
        for(int i = 1; i <= n; i++) y[a[i]] = 0;
        cout << res << '\n';
    }
    return 0;
}