2022杭电多校第三场 Two Permutations (dp, 哈希)

1012 Two Permutations

题目链接

题意：

给定两个$1-n$的全排列数组$P,Q$。一个空排列$R$,每次可以从两个排列的首位数字选一个插到$R$的后面，然后该数字从排列中删除，最后可以$R$是一个长度为$2n$的数组。问：给定最终的$R$，有多少种方案可以构成。

思路：

考虑一个排列$P$的放置方案。显然，$1-n$中每个数字会出现两次，我们记录每个数字$p[i]$出现在$R$数组中的位置为$pos[p[i]][0],pos[p[i]][1]$。考虑动态规划：$dp[i][j]$表示数字$P[i]$匹配$p[i]$在$R$中第$j$次出现的位置的方案数。然后我们可以枚举$p[i+1]$出现的位置，那么在这两个位置中间就是由$Q$中连续的一段子串所放置，那么我们可以预处理哈希然后$O(1)$判断$Q$中连续的一段是否完全匹配$R$的一段子串。

code:

typedef unsigned long long ULL;
typedef long long LL;
typedef pair<int, int> pii;
template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
} 
const int N = 3e5 + 10, M = N * 2, mod1 = 998244353, mod2 = 1e9 + 7;
inline LL ksm(LL a, LL b, int mod){
    LL ans = 1; 
    for(; b; b >>= 1, a = a * a % mod) if(b & 1) ans = ans * a % mod;
    return ans;
}
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, -1, 1};

//----------------------------------------------------------------------------------------//
ULL fb[N], fc[N << 1], p[N << 1];
int n, a[N], b[N], c[N << 1];
int dp[N][2], pos[N][2];

inline ULL get(ULL f[], int l, int r) {
    return f[r] - f[l - 1] * p[r - l + 1];
}
inline bool check(int lb, int rb, int lc, int rc) {
    if(lb > rb) return 1;
    if(lb < 1 || rb > n || lc < 1 || rc > n + n) return 0;
    return get(fb, lb, rb) == get(fc, lc, rc);
}
inline void up(int &x, int y) {
    x = x + y >= mod1 ? x + y - mod1 : x + y;
}
void solve() {
    read(n);
    for(int i = 1; i <= n; i++) read(a[i]);
    for(int i = 1; i <= n; i++) read(b[i]);
    for(int i = 1; i <= n + n; i++) read(c[i]);

    for(int i = 1; i <= n; i++) for(int j = 0; j < 2; j++) dp[i][j] = 0;
    for(int i = 1; i <= n; i++) pos[i][0] = pos[i][1] = 0;

    for(int i = 1; i <= n; i++) fb[i] = fb[i - 1] * 233 + b[i];
    for(int i = 1; i <= n << 1; i++) fc[i] = fc[i - 1] * 233 + c[i];
    for(int i = 1; i <= n << 1; i++) {
        if(!pos[c[i]][0]) pos[c[i]][0] = i;
        else pos[c[i]][1] = i;
    }
    int Q = 1;
    for(; Q <= n; Q++) if(!pos[Q][0] || !pos[Q][1]) break;
    if(Q != n + 1) {
        puts("0");
        return;
    }
    for(int j = 0; j < 2; j++) {
        int x = pos[a[1]][j];
        if(check(1, x - 1, 1, x - 1)) dp[1][j] = 1;
    }
    for(int i = 1; i < n; i++) {
        for(int j = 0; j < 2; j++) {
            if(dp[i][j]) {
                int x = pos[a[i]][j];
                for(int k = 0; k < 2; k++) {
                    int y = pos[a[i + 1]][k];
                    if(y <= x) continue;
                    if(check(x - i + 1, y - i - 1, x + 1, y - 1)) 
                        up(dp[i + 1][k], dp[i][j]);
                }
            }
        }
    }
    int ans = 0;
    for(int j = 0; j < 2; j++) 
        if(dp[n][j]) {
            int x = pos[a[n]][j];
            if(check(x - n + 1, n, x + 1, n + n )) up(ans, dp[n][j]);
        }
    printf("%d\n", ans);
}   
signed main() {
#ifdef JANGYI
    freopen("input.in", "r", stdin);
    freopen("out.out", "w", stdout);
    auto now = clock();
#endif
    // ios::sync_with_stdio(false);
    // cin.tie(0);
    p[0] = 1;
    for(int i = 1; i < N << 1; i++) p[i] = p[i - 1] * 233;
    int T = 1;
    read(T);
    while(T--) {
        solve();
    }    

#ifdef JANGYI
    cout << "================================" << endl;
    cout << "Program run for " << (clock() - now) / (double)CLOCKS_PER_SEC * 1000 << " ms." << endl;
#endif
    return 0;
}   
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102