20230215 - 模拟赛 | Final Fantasy = xixike = 人间忽晚，山河已秋

博弈论 + 计数，AC自动机 + dp，格路计数

# A. 取石子

看了几个小时才想到怎么博弈。

我们把 $x_i\ \bmod\ (a+b)$ 的余数分类讨论，设余数为 $r$ 。

假设 $a < b$ .

$0 \leq r \leq a - 1$
$a \leq r \leq b - 1$
$b \leq r \leq 2a - 1$
$2a \leq r \leq a + b - 1$

下面来分析一下：

情况 1 对胜负没用，忽略掉，不过最后计数的时候要乘上 $2^{c_1}$ 。
出现情况 2，那么 $\text{Alice}$ 必胜，因为这步可以留到最后走。
出现情况 3，那么相当于交换先后手。
出现情况 4：
- 出现次数大于 1：那么 $\text{Alice}$ 必胜，可以手模一下。
- 只出现 1 次， $\text{Alice}$ 先手则先手胜， $\text{Bob}$ 先手则交换先手顺序。

如果 $2a < b$ 的话把 3，4合并起来就行了（好像）

然后把四种情况记到桶里。

$O(1)$ 计算或者 $O(n)$ $\text{dp}$ 都行。

#include <bits/stdc++.h>
#define pb push_back
// #define int long long

using namespace std;

const int N = 1e5 + 10;
const int mod = 1e9 + 7;
int n, a, b;
int s[N], c[N], tot, tmp;

inline int add(int x) {return x >= mod ? x - mod : x;}
inline int sub(int x) {return x < 0 ? x + mod : x;}
inline int mul(int x, int y) {return 1ll * x * y % mod;}

inline int qpow(int a, int b, int v){
    if(b < 0) return v;
    int res = 1;
    for(; b; b >>= 1, a = mul(a, a))
        if(b & 1) res = mul(res, a);
    return res;
}

int t[4], win[4];
// 0: alice胜  1: Bob胜  2: 先手  3: 后手
int d[N], k, flag;

signed main(){
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    ios :: sync_with_stdio(false);
    cin >> n >> a >> b;
    if(a > b) swap(a, b), flag = 1;
    for(int i = 1; i <= n; ++i) cin >> s[i];
    for(int i = 1; i <= n; ++i){
        int r = s[i] % (a + b);
        if(r < a) t[0]++;
        if(a <= r && r < b) t[1]++;
        if(b < 2 * a){
            if(b <= r && r < 2 * a) t[2]++;
            if(2 * a <= r && r <= a + b - 1) t[3]++;
        }else{
            if(b <= r && r <= a + b - 1) t[3]++;
        }
    }
    win[2] = add(qpow(2, t[2] - 1, 0) + mul(t[3], qpow(2, t[2] - 1, 1)));
    win[2] = mul(win[2], qpow(2, t[0], 1));
    win[3] = mul(qpow(2, t[2] - 1, 1), qpow(2, t[0], 1));
    win[0] = sub(qpow(2, n, 0) - add(win[2] + win[3]));
    if(flag) swap(win[0], win[1]);
    for(int i = 0; i < 4; ++i) cout << win[i] << " ";
    cout << '\n';
    return 0;

}

# B. 字符串

妙题。

我们对 $s_1 \sim s_n$ 的正反串分别建两个 AC 自动机，设为 $A,B$ 。

记一个 $\text{dp}$ ，设 $f_{i, S, p, q}$ 表示填了 $i$ 个字符，包含了状态为 $S$ 的串，当前在 $A$ 的 $p$ 点， $B$ 的 $q$ 点时的方案数。

转移时枚举下一个填 $0/1$ ，对称的位置是固定的，让 $p, q$ 跳到相应的 $x, y$ 点，状态或上 $x,y$ 包含的子串。

转移方程：

$f_{i + 1, s | endA_x | endB_y, x, y} += f_{i, s, p, q}$

这时还有一个小问题，就是有一些串越过中间的位置。

我们预处理出一个数组 $g_{i, j}$ 表示现在在 $A$ 中的 $i$ 点， $B$ 中 $j$ 点时，两边拼接能够包含的 $n$ 个模式串的 01 状态。

统计答案时枚举状态，再枚举所有符合这个状态的 $p, q$ ，把 $S$ 跟 $g_{p, q}$ 或起来看一下是否合法即可。

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define int long long

using namespace std;

const int N = 610;
const int mod = 998244353;
int n, m;
char s[10][N];
int b[N], len[10];

inline void add(int &x, int y) {x = x + y >= mod ? x + y - mod : x + y;}

struct ACAN{
    int ch[N][2], tot, num[N], fail[N];
    vector <int> G[N];

    inline void insert(char *s, int id){
        int len = strlen(s + 1), u = 0;
        for(int i = 1; i <= len; ++i){
            int c = s[i] - '0';
            if(!ch[u][c]) ch[u][c] = ++tot;
            u = ch[u][c];
        }
        num[u] |= (1 << id);
    }

    inline void build(){
        queue <int> q;
        for(int i = 0; i < 2; ++i)
            if(ch[0][i]) q.push(ch[0][i]);
        while(!q.empty()){
            int x = q.front(); q.pop();
            for(int i = 0; i < 2; ++i){
                if(ch[x][i]) fail[ch[x][i]] = ch[fail[x]][i], q.push(ch[x][i]);
                else ch[x][i] = ch[fail[x]][i];
            }
        }
        for(int i = 1; i <= tot; ++i) G[fail[i]].pb(i), num[i] |= num[fail[i]];
    }
}A, B;

int g[N][N];

inline int jump1(int p, int l, int r){
    int x = 0;
    for(int i = l; i <= r; ++i) x = A.ch[x][s[p][i] - '0'];
    return x;
}

inline int jump2(int p, int l, int r){
    int x = 0;
    for(int i = r; i >= l; --i) x = B.ch[x][s[p][i] - '0'];
    return x;
}

inline void dfs2(int x, int y){
    g[x][y] |= g[x][B.fail[y]] | g[A.fail[x]][y];
    for(auto v : B.G[y]) dfs2(x, v);
}

inline void dfs1(int x, int y){
    dfs2(x, y);
    for(auto v : A.G[x]) dfs1(v, y);
}

typedef pair<int, int> P;
int f[2][64][N][N];
vector <P> vec[2][64];

signed main(){
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    ios :: sync_with_stdio(false);
    cin >> m >> n;
    for(int i = 0; i < m; ++i){
        cin >> (s[i] + 1), len[i] = strlen(s[i] + 1);
        A.insert(s[i], i), reverse(s[i] + 1, s[i] + 1 + len[i]);
        B.insert(s[i], i), reverse(s[i] + 1, s[i] + 1 + len[i]);
    }
    A.build(), B.build();
    for(int i = 0; i < m; ++i)
        for(int j = 1; j < len[i]; ++j)
            g[jump1(i, 1, j)][jump2(i, j + 1, len[i])] |= (1 << i);
    dfs1(0, 0);

    f[0][0][0][0] = 1;
    vec[0][0].pb(P(0, 0));
    for(int i = 0, l = 0; i < n; ++i, l ^= 1)
        for(int s = 0; s < (1 << m); ++s){
            for(auto p : vec[l][s]){
                for(int c = 0; c < 2; ++c){
                    P q = P(A.ch[p.fi][c], B.ch[p.se][c ^ 1]);
                    int t = s | A.num[q.fi] | B.num[q.se];
                    if(!f[l ^ 1][t][q.fi][q.se]) vec[l ^ 1][t].pb(q);
                    add(f[l ^ 1][t][q.fi][q.se], f[l][s][p.fi][p.se]);
                }
                f[l][s][p.fi][p.se] = 0;
            }
            vec[l][s].clear();
        }
    int ans = 0;
    for(int s = 0; s < (1 << m); ++s)
        for(auto p : vec[n & 1][s])
            if((s | g[p.fi][p.se]) == (1 << m) - 1) add(ans, f[n & 1][s][p.fi][p.se]);
    cout << ans << '\n';
    return 0;
}

# C. 树

挺复杂的格路计数。

经过大量模拟不难发现不包含 $k$ 连树相当于根到每个叶子上左儿子个数小于 $k$ 。

考虑按先序遍历建出这棵树，每次有两种操作：

当前点加一个左孩子；
退到上一个只有左孩子的点，加一个右孩子。

转化成括号匹配，相当于一个长度为 $2n - 2$ 的序列，保证左括号 - 右括号数量小于 $m$ 。

当然还要保证括号序列合法，即前缀和大于等于 0。

如果只有前缀和大于等于 0 的条件，就是经典的卡特兰数的容斥：

总路径 - 不合法路径。大概就是把第一次碰到 -1 后面的路径全部翻折，最后到达 $(2n-2, -2)$ （不会的自行百度）

不合法方案数就是从 $(0, 0)$ 走到 $(2n-2,-2)$ 的路径数。

然后现在有两个限制条件，我们的方案数就是：

$总 - [-1] - [m - 1]$

（ $[-1], [m-1]$ 表示经过 $-1, m-1$ 的方案数）

但是明显有重复的，所以就再套个容斥：

$总 - [-1] - [m - 1] + [-1, m - 1] + [m - 1, -1] - [-1, m - 1, -1] -\cdots$

然后就没了。

#include <bits/stdc++.h>
#define pb push_back

using namespace std;

const int N = 2e7 + 10;
const int mod = 998244353;
int n, m;
int fac[N], ifac[N];

inline int add(int x) {return x >= mod ? x - mod : x;}
inline int sub(int x) {return x < 0 ? x + mod : x;}
inline int mul(int x, int y) {return 1ll * x * y % mod;}

inline int qpow(int a, int b){
    int res = 1;
    for(; b; b >>= 1, a = mul(a, a))
        if(b & 1) res = mul(res, a);
    return res;
}

inline void init(int n){
    fac[0] = 1;
    for(int i = 1; i <= n; ++i) fac[i] = mul(fac[i - 1], i);
    ifac[n] = qpow(fac[n], mod - 2);
    for(int i = n - 1; i >= 0; --i) ifac[i] = mul(ifac[i + 1], i + 1);
}

inline int C(int n, int m){
    return mul(fac[n], mul(ifac[m], ifac[n - m]));
}

inline int f(int x){
    if(x > n || x < -n) return 0;
    return C(n, (n + x) / 2);
}

signed main(){
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    ios :: sync_with_stdio(false);
    cin >> n >> m, init(2e7);
    n = 2 * n - 2;
    int ans = f(0);
    for(int k = 2; (k - 2) * m <= n; k += 2){
        ans = sub(ans - add(f(k * m - 2) + f(-(k - 2) * m - 2)));
        ans = add(ans + add(f(k * m) + f(-k * m)));
    }
    cout << ans << '\n';
    return 0;
}

# A. 取石子

# B. 字符串

# C. 树

20230214

20230217