2023.1.29 模拟赛记录

2023冬

期望分数：

实际分数：

Summary

T1：代码有实现上的小问题，错将 $flag$ 变量的意义搞反，并且没有给 $flag$ 附初值。
T2：AC，但状态设计得稍显冗余
T3：看到无向图上随机游走问题，先入为主的认为一定是高斯消元解决，并且没有积累过这种拆平方期望的套路，导致没有想出来。

T1 GotoAndPlay

Description

我们用一张连通图来表示整个西湖的范围，每棵容小松鼠逗留的树都用
这张图上的一个点来表示。小松鼠能够通过只跳一次互相到达的两棵树用
图上的一条无向边来连接。　
　吃撑了的小松鼠有些神志不清，每次她连跳两条边之后才会在到达的那
个点上休息。她想知道，是否存在一种连续的跳法，使得她有机会在所有
的树上都休息至少一次。
　对于这种跳法，你可以任选起点，允许重复经过边，允许重复经过点。
　但是超萌小松鼠是一只有梦想的小松鼠，她有时能够突破自己的极限，
使一些原本无法互相到达的两个点能够通过一次跳跃互相到达。

$1 \leq n \leq 1e5$

Solution

稍微手玩一下+想一下，很容易发现若图中有奇环，则一定是 "YES"，那么问题变为二分图判定。

染色，每次询问看两个端点是否同色冲突即可。

Code

//The Code Is From Dawn
#include<bits/stdc++.h>
using namespace std;
inline int read() {
    int x = 0;
    char c = getchar();
    bool f = 0;
    while(!isdigit(c)) f |= (c == '-'), c = getchar();
    while(isdigit(c)) x = (x * 10) + (c ^ 48), c = getchar();
    return f ? -x : x;
}
const int maxn = 1e6 + 5, maxm = 2 * 1e6 + 5;
int n, m, Q, flag;
struct node {
    int v, nex;
}edge[maxm << 1];
int head[maxn], len;
int Col[maxn];
inline void make_map(int u, int v) {
    len++;
    edge[len].nex = head[u];
    edge[len].v = v;
    head[u] = len;
}
inline bool Search(int x, int col) {
    Col[x] = col;
    bool fl = 1;
    for(register int i = head[x]; i; i = edge[i].nex) {
        int y = edge[i].v;
        if(Col[y] != -1) {
            if(Col[y] ^ Col[x]) continue;
            else return 0;
        }
        fl &= Search(y, col ^ 1);
    }
    return fl;
}
int main() {
//  freopen("GotoAndPlay.in", "r", stdin);
//  freopen("GotoAndPlay.out", "w", stdout);
    n = read(), m = read();
    flag = 1;
    for(register int i = 1; i <= m; ++i) {
        int u = read(), v = read();
        make_map(u, v), make_map(v, u);
    }
    fill(Col + 1, Col + n + 1, -1);
    for(register int i = 1; i <= n; ++i)
        if(Col[i] == -1) flag &= Search(i, 0);
    Q = read(); 
    while(Q--) {
        int u = read(), v = read();
        if(!flag) { printf("Yes\n"); continue; }
        if(Col[u] == Col[v]) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

T2 StopAllSounds

Description

超萌游戏机之所以拥有这个名字，是因为它的屏幕是一个n  2的矩形。
小松鼠接过游戏机，开始了她的第一个游戏：俄罗斯方块。
　考虑到小松鼠的智商，游戏机里的方块只有下面四种，方块按顺序下落，
　可以在任意时刻（甚至是下落前）对其进行不限次数的旋转操作。
　由于四种方块最小宽度都为2，因此下落的时候在水平方向上是不能够移
动的。我们称当前方块下落的过程完成了，当且仅当其再往下移动一个单
位就会与之前覆盖的方块有部分相重叠。小松鼠想要知道，在这个n  2的
游戏界面中，一共会出现多少种游戏状态。游戏状态指单次方块下落的过
程完成后，不要求游戏结束（即不要求第1行非空），且界面中出现的必须
是完整的方块。
　两种游戏状态被认为是相同的，当且仅当游戏界面中的每一个格子两种
状态下被覆盖的方块类型都相同（或都不被覆盖）。
　再次考虑到小松鼠的智商，答案模 $10^9 + 7$ 输出。

$1 \leq n \leq 1e6$

Solution

比较显然的状压 DP 题，一种比较好的状压方式是考虑当前“表面”的缺口。

分别记：表面没有缺口，表面左侧有一个缺口，表面右侧有一个缺口，表面左侧有两个缺口，表面右侧有两个缺口

分讨转移即可。

Code

//The Code Is From Dawn
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
    int x = 0;
    char c = getchar();
    bool f = 0;
    while(!isdigit(c)) f |= (c == '-'), c = getchar();
    while(isdigit(c)) x = (x * 10) + (c ^ 48), c = getchar();
    return f ? -x : x;
}
const int maxn = 1e6 + 5, mod = 1e9 + 7;
int n;
int f[maxn][2][2][2][2], Answer;
inline void Add(int &x, int y) { x = (x + y) % mod; }
signed main() {
    freopen("StopAllSounds.in", "r", stdin);
    freopen("StopAllSounds.out", "w", stdout);
    n = read();
    f[0][1][1][1][1] = 1; 
    for(register int i = 1; i <= n; ++i) {
        for(register int a = 0; a < 2; ++a) {
            Add(f[i][0][0][0][1], f[i - 1][0][1][a][1]);
            Add(f[i][0][0][1][0], f[i - 1][1][0][1][a]);
        }
        Add(f[i][0][0][1][1], f[i - 1][1][1][0][1]);
        Add(f[i][0][0][1][1], f[i - 1][1][1][1][0]);
        Add(f[i][0][0][1][1], f[i - 1][1][1][1][1]);
        if(i == 1) continue;
        for(register int a = 0; a < 2; ++a)
            for(register int b = 0; b < 2; ++b) { 
                Add(f[i][1][1][1][1], f[i - 2][1][0][a][b]);
                Add(f[i][1][1][1][1], f[i - 2][0][1][a][b]);
                Add(f[i][1][1][1][1], f[i - 2][1][1][a][b]);
            }
            for(register int a = 0; a < 2; ++a) {
                Add(f[i][0][1][1][1], f[i - 2][1][0][1][a]);
                Add(f[i][0][1][1][1], f[i - 2][0][0][a][1]);
            }
            for(register int a = 0; a < 2; ++a) {
                Add(f[i][1][0][1][1], f[i - 2][0][1][a][1]);
                Add(f[i][1][0][1][1], f[i - 2][0][0][1][a]);
            }
            if(i >= 4) {
                Add(f[i][1][1][1][1], f[i - 3][0][0][1][0]);
                Add(f[i][1][1][1][1], f[i - 3][0][0][0][1]);
                Add(f[i][1][1][1][1], f[i - 3][0][0][1][1]);
            }
            Add(f[i][1][1][1][0], f[i - 2][0][1][1][1]);
            for(register int a = 0; a < 2; ++a)
                Add(f[i][1][1][1][0], f[i - 2][0][0][1][a]);
            for(register int a = 0; a < 2; ++a) {
                Add(f[i][0][1][1][1], f[i - 2][0][0][1][a]);
                Add(f[i][0][1][1][1], f[i - 2][0][1][a][1]);
            }
            Add(f[i][0][1][0][1], f[i - 2][0][0][1][0]);
            Add(f[i][0][1][0][1], f[i - 2][0][0][0][1]);
            Add(f[i][0][1][0][1], f[i - 2][0][0][1][1]);
    }
    for(register int i = 1; i <= n; ++i) {
        for(register int a = 0; a < 2; ++a) {
            Add(Answer, f[i][1][0][1][a]);
            Add(Answer, f[i][0][1][a][1]);
        }
        Add(Answer, f[i][1][1][0][1]), Add(Answer, f[i][1][1][1][0]), Add(Answer, f[i][1][1][1][1]);
    }
    printf("%lld\n", Answer + 1);
    return 0;
}

T3 UpdateAfterEvent

Description

给定一张 $n$ 个点的无向图，每个点上有 $a_i$ 只松鼠，每个时刻，每只松鼠会等概率移动到相邻的点，概率为 $\frac{1}{Deg[i]}$ ，若最终状态下，某个点上松鼠的数量为 $x$，则这个点的价值为 $\frac{x * (x - 1)}{2}$，问经过 $T$ 的时间后，所有点的价值之和的期望。

数据分为两个Sub

Sub1 : $1 \leq n \leq 100, 1 \leq T \leq 10^9$
Sub2 : $1 \leq n \leq 1000, T = 1$

Solution

考虑这个价值是个平方的柿子，而平方的式子是不能用线性性拆开的，我们考虑改变计算价值的形式。

考虑到 $\frac{x * (x - 1)}{2} = 1 + 2 + \ldots + (x - 1)$

我们以每只松鼠为视角，给每只松鼠一个标号，假定松鼠的行动是按标号先后顺序行动的。

那么我们可以将所求改变为 每只松鼠到达终点后造成的贡献的和的期望。

每只松鼠到达终点后造成的贡献就是这个点现在有的松鼠数量。

这个期望是可以用线性性拆开的。

我们考虑 Sub1，考虑求出 $P(i, j)$ 表示第 $i$ 个点的松鼠终点走到 $j$ 的概率。

这个东西显然可以拿度数的倒数矩阵，做 $T$ 次方的矩阵快速幂得到。

那么计算答案，考虑枚举两个松鼠的起点 $i$ 与 $j$，终点 $k$，那么答案为 $P(i,k) \times Val[i] \times P(j, k) \times Val[j]$。

特殊的，当 $i = j$ 时，需要将 $Val[i] \times Val[j]$ 改成 $\binom{2}{Val[i]}$

复杂度 $O(n^3 \log n)$

考虑Sub2

由于 $T=1$，不再需要矩阵快速幂。

而上面那个计算答案的方式，显然可以将 $i,j$ 分开，用前缀和优化掉一维，这个优化同样适用于Sub1，但不解决瓶颈

复杂度 $O(n^2)$

Code

//The Code Is From Dawn
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
    int x = 0;
    char c = getchar();
    bool f = 0;
    while(!isdigit(c)) f |= (c == '-'), c = getchar();
    while(isdigit(c)) x = (x * 10) + (c ^ 48), c = getchar();
    return f ? -x : x;
}
const int maxn = 1005, maxm = 105, mod = 1e9 + 7;
int n, T;
int Val[maxn], mapp[maxn][maxn], Du[maxn], Inv[maxn], Answer;
struct Matrix {
    int num[maxm][maxm];
    inline void Clear() { memset(num, 0, sizeof(num)); }
    inline int &operator () (int x, int y) { return num[x][y]; }
    inline void Init() {
        Clear();
        for(register int i = 1; i <= n; ++i) num[i][i] = 1;
    }
}Base, f;
inline Matrix operator *(Matrix A, Matrix B) {
    Matrix C; C.Clear();
    for(register int i = 1; i <= n; ++i)
        for(register int j = 1; j <= n; ++j)
            for(register int k = 1; k <= n; ++k)
                C(i,j) = (C(i,j) + A(i, k) * B(k, j) % mod) % mod;
    return C;
}
inline Matrix Matrix_Ksm(Matrix A, int B) {
    Matrix res; res.Init();
    while(B) {
        if(B & 1) res = res * A;
        A = A * A, B >>= 1;
    }
    return res;
}
inline int Ksm(int A, int B) {
    int res = 1;
    while(B) {
        if(B & 1) res = res * A % mod;
        A = A * A % mod, B >>= 1;
    }
    return res;
}
inline void Ready() {
    for(register int i = 1; i <= n; ++i) Inv[i] = Ksm(i, mod - 2);
}
signed main() {
    freopen("UpdateAfterEvent.in", "r", stdin);
    freopen("UpdateAfterEvent.out", "w", stdout);
    n = read(), T = read();
    Ready();
    for(register int i = 1; i <= n; ++i) Val[i] = read();
    for(register int i = 1; i <= n; ++i)
        for(register int j = 1; j <= n; ++j) {
            mapp[i][j] = read();
            if(mapp[i][j]) Du[i]++;
    }
    if(T == 1) {
        for(register int i = 1; i <= n; ++i) {
            int Sum = 0;
            for(register int j = 1; j <= n; ++j) {
                if(!mapp[i][j]) continue;
                int Cnt = Val[j] * Inv[Du[j]] % mod;
                Answer = (Answer + Sum * Cnt % mod) % mod;
                Sum = (Sum + Cnt) % mod;
            }
        }
        for(register int i = 1; i <= n; ++i) {
            int Cnt = Val[i] * (Val[i] - 1) / 2 % mod;
            Answer = (Answer + Inv[Du[i]] * Cnt % mod) % mod;
        }
        printf("%lld\n", Answer); 
        return 0;
    }
    else {
        Base.Clear();
        for(register int i = 1; i <= n; ++i)
            for(register int j = 1; j <= n; ++j) 
                if(mapp[i][j]) Base(i, j) = Inv[Du[i]];
        Base = Matrix_Ksm(Base, T);
        for(register int i = 1; i <= n; ++i)
            for(register int j = i + 1; j <= n; ++j)
                for(register int k = 1; k <= n; ++k) {
                    int A = Base(i, k) * Val[i] % mod, B = Base(j, k) * Val[j] % mod;
                    Answer = (Answer + A * B % mod) % mod;
                }
        for(register int i = 1; i <= n; ++i)
            for(register int j = 1; j <= n; ++j) {
                int A = Base(i, j) * Base(i, j) % mod;
                int B = Val[i] * (Val[i] - 1) / 2 % mod;
                Answer = (Answer + A * B % mod) % mod;
            }
        printf("%lld\n", Answer);
    }
    return 0;
}

Summary

非常巧妙的期望转换方式，面对平方的期望贡献，不只能用完全平方拆开，还可以考虑分步重写贡献。