洛谷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;
}