7.10暑期模拟赛

2022暑

---

期望得分

T1	T2	T3	Sum
100	0	100	200

实际得分：

T1	T2	T3	Sum
0	0	60	60

惨（woshiSB

T1 Comic

算法：树型DP，组合计数

树上计数，考虑DP

感觉从后往前填比较好填，所以把儿子倒过来

很显然每个儿子互相独立，考虑怎么合并到根上

首先填儿子 $y$ ，显然只有一种填法，那么接下来的 ($\operatorname{Siz}_y - 1$) 个 就可以填到 $y$ 后面的任意一个空

那么就是 $\operatorname{P}(_{\operatorname{Siz}_x + \operatorname{Siz}_y - 2}^{\operatorname{Siz}_y - 1})$ 但是这样可能会不满足子孙的前后限制，所以还要除一个 $\operatorname{P}(_{\operatorname{Siz}_y - 1}^{\operatorname{Siz}_y - 1})$

所以DP方程：

$$f[x] = \sum_{y \in son}f[y] * \operatorname{C}(_{\operatorname{Siz}_x + \operatorname{Siz}_y - 2}^{\operatorname{Siz}_y - 1})$$

Tips：错误原因：做插空法的时候考虑总“空隙数”错误

//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, mod = 10007;
int T, n, tot;
struct node {
    int v, nex;
}edge[maxn << 1];
int head[maxn], len;
int Frac[maxn], Inv[maxn], Answer[maxn], Siz[maxn];
vector <int> E;
inline void make_map(int u, int v) {
    len++;
    edge[len].nex = head[u];
    edge[len].v = v;
    head[u] = len;
}
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() {
    Frac[0] = 1, Inv[0] = 1;
    for(register int i = 1; i < maxn; ++i) Frac[i] = Frac[i - 1] * i % mod, Inv[i] = Ksm(Frac[i], mod - 2);
}
inline int C(int x, int y) { return Frac[y] * Inv[y - x] % mod * Inv[x] % mod;}
inline void Search(int x) {
    Siz[x] = 1, Answer[x] = 1;
    if(!head[x]) return ;
    for(register int i = head[x]; i; i = edge[i].nex) {
        int y = edge[i].v;
        Search(y);
        if(Siz[y] > 1) Answer[x] = Answer[x] * (Answer[y] * C(Siz[y] - 1, Siz[x] + Siz[y] - 2) % mod) % mod;
        Siz[x] += Siz[y];
    }
}
signed main() {
//    freopen("t1.in", "r", stdin);
//    freopen("t1.out", "w", stdout);
    T = read(), Ready();
    while(T--) {
        n = read();
        len = 0, memset(head, 0, sizeof(head)), memset(Answer, 0 ,sizeof(Answer)), memset(Siz, 0, sizeof(Siz));
        for(register int i = 1; i <= n; ++i) {
            tot = read();
            E.clear();
            for(register int j = 1; j <= tot; ++j) E.push_back(read());
            for(register int j = 0; j < E.size(); ++j)  make_map(i, E[j]);
        }
        Search(1);
        printf("%lld\n", Answer[1]);
    }
    return 0;
}

T2 Worried

首先差分，考虑 $[2,x]$ 怎么求

首先想到的是枚每个数最多能多少次方，但这样要枚 $10^9$ ，不可行

考虑枚举次数，那么难点来到怎么求 $\sqrt[k]{x}$ ，考虑二分，但二分过程中会爆longlong（似乎可以避免，但感觉处理起来很麻烦，不管了）

然后我就感觉这个思路也G了，就没往下想了，下面给出来自 Ew_Cors 与 zzm 的两种思路。

思路1：考虑STL的$\operatorname{pow(x, \frac{1}{k}})$ （才知道$\operatorname{pow}$ 能求 $n$ 次根），但这样可能有精度问题，所以需要左右调整一下

思路2：$2$ 次方可以直接 $\operatorname{sqrt}$ ，$3$ 次方及以上最多 $10^6$ 个，所以其实可以直接枚举

但要注意的是，这样求出来的只是 “能够被表示为 $k$ 次方” 的数，并没有保证最大，所以需要容斥。

可以发现这个容斥和 $\operatorname{Dirichlet}$ 前缀和很像：

$$f[i] = f[i] - \sum_{j > 1}{f[i * j]}$$

Tips:
日常数据范围没算准，觉得想不到方法的时候可以算一下范围，以防想复杂

当时也没完全相当用容斥，只觉得这东西很难去重，容斥技巧仍需加强

//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 = 64;
int L, R;
int f[maxn + 5];
inline int Calc(int x) {
    int Answer = 0;
    f[2] = sqrt(x);
    for(register int i = 3; i <= maxn; ++i) {
        f[i] = 0;
        while(pow(f[i] + 1, i) <= x) ++f[i];
        f[i]--;
    }
    for(register int i = 64; i >= 2; --i) 
        for(register int j = 2; i * j <= 64; ++j) f[i] -= f[i * j];
    for(register int i = 2; i <= 64; ++i) Answer += f[i] * (i - 1);
    return Answer + x - 1;
}
signed main() {
    while((L = read()) && (R = read())) printf("%lld\n", Calc(R) - Calc(L - 1));
    return 0;
}

T3 CF

考场上稍微手玩一下，发现第一列可以随便填，考虑其他列填每个位置有什么不同。

$$\begin{matrix} \color{red}{0} & 1 & 0 & 0\\ 1 & \color{red}{0} & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1 \end{matrix}$$

若第二个 $0$ 填在标红的位置，则剩余的矩阵将形成一个 $n - 2$ 的子问题

若填到未标红位置，相当于不能填红色位置，如果将它也看作一个障碍的话，那就是一个 $n - 1$ 的子问题

那么可以考虑DP

$$f[i] = (n - 1) \times (f[i - 1] + f[i - 2])$$

可以发现，这个DP方程，正好也是错排问题的递推式，那么此题是否与错排问题有关呢？

由上面的分析可以发现，答案与矩阵到底是什么样子无关，只与 $n$ 有关，所以可以将此矩形特殊化为对角线为1的矩形。

那么就是错排问题的模型了。

Tips：由于此题没给模数，要用高精，然后高精写挂了（，来自 WoshiSB 的小技巧：不需要压位且复杂度较充裕时，可以直接用加法代替乘法

//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 = 205, maxm = 1000;
int n;
struct node {
    int len;
    int s[maxm] = {0};
}f[maxn];
inline node operator + (node a, node b) {
    int len = max(a.len, b.len);
    int x = 0;
    node c;
    for(register int i = 1; i <= len; ++i) {
        c.s[i] = (a.s[i] + b.s[i] + x) % 10;
        x = (a.s[i] + b.s[i] + x) / 10;
    }
    if(x) c.s[++len] = x; c.len = len;
    return c;
}
signed main() {
//    freopen("t3.in", "r", stdin);
//    freopen("t3.out", "w", stdout);
    n = read();
    f[1].s[1] = 0, f[1].len = 1, f[0].s[1] = 1, f[0].len = 1;
    for(register int i = 2; i <= n; ++i) {
        node Cnt = f[i - 1] + f[i - 2];
        for(register int j = 1; j < i; ++j) f[i] = f[i] + Cnt;
    }
    for(register int i = f[n].len; i >= 1; --i) printf("%lld", f[n].s[i]);
    return 0;
}