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

计数，~~div lj ak~~AC自动机 + 树上差分，结论 + 树状数组，区间dp

# A. 矩阵游戏

一眼想到我永远喜欢月，然而并没有什么卵用。

不难发现行列是独立的，所以分开考虑。

我们称操作一行或一列被操作奇数次为有效操作。

那么当有 $i$ 行有效， $j$ 列有效的方案数为：

$\dbinom ni\dbinom mj$

此时 $i, j$ 应满足 $0 \leq i, j \leq k, i, j \equiv 2 \bmod k$ .

但是会算重，什么情况下有重复呢？

结论：只有在 $n, m$ 均为偶数时，不同的操作方案才会导致出现相同的矩阵。

证明…就算了。

算重的部分同样是：

$\dbinom ni \dbinom mj$

当 $i, j$ 满足: $(i,j <= k, i, j \equiv 2 \bmod k, n-i, m - j \leq k)$ .

最后面这个条件什么意思呢？其实就是把所有的操作反过来依旧合法的限制。

用上面的总方案数减掉这个就行了。

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

using namespace std;

namespace IO{
    inline int read(){
        int x = 0, f = 1;
        char ch = getchar();
        while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x * f;
    }

    template <typename T> inline void write(T x){
        if(x < 0) putchar('-'), x = -x;
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const int N = 2e5 + 10;
const int mod = 1e9 + 7;
int T, n, m, k;
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;
    while(b){
        if(b & 1) res = mul(res, a);
        a = mul(a, a), b >>= 1;
    }
    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 void solve(){
    cin >> n >> m >> k;
    int res = 0, s1 = 0, s2 = 0;
    for(int i = k & 1; i <= min(n, k); i += 2) s1 = add(s1 + C(n, i));
    for(int i = k & 1; i <= min(m, k); i += 2) s2 = add(s2 + C(m, i));
    res = mul(s1, s2);
    if((n & 1) || (m & 1)) cout << res << '\n';
    else{
        s1 = 0, s2 = 0;
        for(int i = k & 1; i <= min(n, k); i += 2)
            if(n - i <= k) s1 = add(s1 + C(n, i));
        for(int i = k & 1; i <= min(m, k); i += 2)
            if(m - i <= k) s2 = add(s2 + C(m, i));
        cout << sub(res - mul(qpow(2, mod - 2), mul(s1, s2))) << '\n';
    }
}

signed main(){
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    cin >> T;
    init(2e5);
    while(T--) solve();
    return 0;
}

# B. Divljak

简单 AC 自动机套树上差分。

简单说一下吧，先建 AC 自动机。

对于每个询问串，把它在 $fail$ 树上的点全都存下来，这些点单点加 1，再把两两 $lca$ 单点减 1。

查询的时候查子树和就行了。

树状数组维护，复杂度一个 $\log$ 。

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

using namespace std;

const int N = 2e6 + 10;
int n, m;
char s[N];

int ch[N][26], tot = 1, id[N];

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

int fail[N];
vector <int> G[N];

inline void build(){
    queue <int> q;
    for(int i = 0; i < 26; ++i) ch[0][i] = 1;
    q.push(1), fail[1] = 0;
    while(!q.empty()){
        int x = q.front(); q.pop();
        for(int i = 0; i < 26; ++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 = 2; i <= tot; ++i) G[fail[i]].pb(i);
}

int siz[N], son[N], dep[N];

inline void dfs1(int x){
    dep[x] = dep[fail[x]] + 1, siz[x] = 1;
    for(auto y : G[x]){
        dfs1(y), siz[x] += siz[y];
        if(siz[y] > siz[son[x]]) son[x] = y;
    }
}

int top[N], dfn[N], tim;

inline void dfs2(int x, int topfa){
    top[x] = topfa, dfn[x] = ++tim;
    if(son[x]) dfs2(son[x], topfa);
    for(auto y : G[x])
        if(y != son[x]) dfs2(y, y);
}

inline int lca(int x, int y){
    while(top[x] != top[y]){
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        x = fail[top[x]];
    }
    return dep[x] < dep[y] ? x : y;
}

int c[N];

inline void add(int x, int y){
    for(; x <= tot; x += x & (-x)) c[x] += y;
}

inline int ask(int x){
    int res = 0;
    for(; x; x -= x & (-x)) res += c[x];
    return res;
}

inline int ask(int l, int r) {return ask(r) - ask(l - 1);}

inline bool cmp(int a, int b) {return dfn[a] < dfn[b];}

inline void upd(char *s){
    int len = strlen(s), u = 1;
    vector <int> vec;
    for(int i = 0; i < len; ++i) u = ch[u][s[i] - 'a'], vec.pb(u);
    sort(vec.begin(), vec.end(), cmp);
    for(auto x : vec){
        add(dfn[x], 1);
        // cout << x <<  " " << dfn[x] << " " << id[1] << " " << ask(dfn[id[1]] - 1) << endl;
    }
    for(int i = 0; i < (int)vec.size() - 1; ++i)
        add(dfn[lca(vec[i], vec[i + 1])], -1);
    // cout << "tmp " << ask(dfn[id[1]] - 1) << endl;
}

inline int qry(int x){
    return ask(dfn[x], dfn[x] + siz[x] - 1);
}

signed main(){
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    ios :: sync_with_stdio(false);
    cin >> n;
    for(int i = 1; i <= n; ++i) cin >> s, insert(s, i);
    build(), dfs1(1), dfs2(1, 1);
    // for(int i = 1; i <= tot; ++i) cout << fail[i] << " ";
    // cout << endl;
    // for(int i = 1; i <= tot; ++i) cout << dfn[i] << " ";
    // cout << endl;
    cin >> m;
    while(m--){
        int op, x; cin >> op;
        if(op == 1) cin >> s, upd(s);
        if(op == 2) cin >> x, cout << qry(id[x]) << '\n';
    }
    return 0;
}

# C. 交换

就是那道 JOISC 的题。

结论就是累加上每个点向左向右交换次数较少的那个。

简单说一下证明：就是考虑把最小的移到最左侧或最右侧，肯定选代价较小的，移动之后不影响其他数的顺序，就变成了一个子问题。

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

using namespace std;

namespace IO{
    inline int read(){
        int x = 0, f = 1;
        char ch = getchar();
        while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x * f;
    }

    template <typename T> inline void write(T x){
        if(x < 0) putchar('-'), x = -x;
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const int N = 3e5 + 10;
int n;
int a[N], b[N];

int c[N];

inline void add(int x, int y){
    for(; x <= n; x += x & (-x)) c[x] += y;
}

inline int qry(int x){
    int res = 0;
    for(; x; x -= x & (-x)) res += c[x];
    return res;
}

signed main(){
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    n = read();
    for(int i = 1; i <= n; ++i) a[i] = read();
    for(int i = 1; i <= n; ++i)
        b[i] = i - 1 - qry(a[i]), add(a[i], 1);
    memset(c, 0, sizeof(c));
    for(int i = n; i >= 1; --i)
        b[i] = min(b[i], n - i - qry(a[i])), add(a[i], 1);
    int ans = 0;
    for(int i = 1; i <= n; ++i) ans += b[i];
    write(ans), puts("");
    return 0;
}

# D. 零二（Zero Two）

比较离谱的题。

假设是个排列，设 $A_p = B_q = n$ 。

那么有 $\{A_1 \sim A_q\} = \{B_1 \sim B_q\}$ ，后半部分也相等。

设 $f_{l, r, x}$ 表示当前考虑 $l \sim r$ 的区间，最大值为 $x$ 时的序列个数。

令 $a_{pos} = x$ ，转移时枚举最后一个入堆的点（也就是入完之后一直弹堆，弹到 $x$ 被弹出来），左右可以分成两部分递归下去：

$f_{l, r, x} = \sum_{i = pos}^rf_{l, i, x - 1}f_{i + 1, r, x - 1}$

可能有点怪，也可以理解为枚举 $x$ 在 $B$ 中出现的位置，然后左右分开考虑，但是这样有瑕疵，最好还是能理解上面的东西。

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

using namespace std;

const int N = 110;
const int mod = 998244353;
typedef pair<int, int> P;
int n;
int a[N], f[N][N][N];
P b[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 solve(int l, int r, int x){
    if(x == 0 || l >= r) return 1;
    if(~f[l][r][x]) return f[l][r][x];
    int pos = -1;
    for(int i = l; i <= r; ++i)
        if(a[i] == x) {pos = i; break;}
    if(pos == -1) return f[l][r][x] = solve(l, r, x - 1);
    int res = 0;
    for(int i = pos; i <= r; ++i)
        if(a[i] <= x) res = add(res + mul(solve(l, i, x - 1), solve(i + 1, r, x - 1)));
    return f[l][r][x] = res;
}

signed main(){
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    ios :: sync_with_stdio(false);
    cin >> n;
    for(int i = 1; i <= n; ++i)
        cin >> a[i], b[i] = {a[i], i};
    sort(b + 1, b + 1 + n);
    for(int i = 1; i <= n; ++i)
        a[i] = lower_bound(b + 1, b + 1 + n, P(a[i], i)) - b;
    memset(f, -1, sizeof(f));
    cout << solve(1, n, n) << '\n';
    return 0;
}

# A. 矩阵游戏

# B. Divljak

# C. 交换

# D. 零二（Zero Two）

20230215

2023 春季联赛游记