2018 Multi-University Training Contest 4__全部题解+标程

​​​​​
6道题排名：29~79

出题人预计难度分布：   Easy - DJKL,      Medium - ABCEG,      Hard - FHI
题解较长，可查看右方目录

##A. Integers Exhibition

不难发现非 $K$K-magic 数是非常少的，考虑先预处理出来，二分回答询问。

以下我们讨论如何求出非 $K$K-magic 数，为方便描述，我们称一个正整数是良好的当且仅当其是非 $K$K-magic 的。

对于一个质数 $p$p，我们考虑所有仅包含小于 $p$p 的质因子的正整数集 $G$G。不难发现：

• 若 $x \in G$x∈G，且在 $G$G 中已经有超过 $K$K 个小于 $x$x 的整数约数个数多于 $x$x，即 $x$x 一定不是良好的，则 $x p ^ c$xpc $(c \ge 0)$(c≥0) 也一定不可能是良好的。

这样我们就可以得到一个初步的想法。开始我们认为仅有 $1$1 是良好的，枚举质因子 $p$p，对于每一个原来认为是良好的数 $x$x，将 $x p ^ c$xpc $(c \ge 0)$(c≥0) 加入候选列表，接着将候选列表排序，除去已经可以确定不是良好的数，进入下一轮迭代。容易证明，在这个算法中，筛去一个不是良好的数 $x$x，是不会在后续过程中令一个原本不是良好的数，变成一个良好的数的，故筛去良好的数的过程是合法的剪枝。

然而枚举的质因子的范围有多大呢？联想 $K = 0$K=0 这一经典问题，我们知道对于 $10 ^ {18}$1018 的范围，考虑前 $20$20 个质因子都绰绰有余了，因为将更大的质因子加入是非常不优的。在 $K$K 更大的时候，我们采用“迭代至稳定”的思想，每一轮迭代后检查答案是否变化，如果在较长一段迭代后答案无任何变化，我们就认为质因子 $p$p 的上界已经达到。经过实践，在 $K = 233$K=233 时，$p$p 的最大值取到 $293$293 即可。

我们考虑如何在一轮迭代中除去确定不是良好的数。考虑维护前 $K + 1$K+1 大值，从小到大枚举候选列表中的数 $x$x，若 $x$x 小于第 $K + 1$K+1 大值，我们就把这个数除去。否则更新前 $K + 1$K+1 大值。根据上述描述可以大致估算复杂度。设 $K = 233$K=233 时，$10 ^ {18}$1018 内良好的数的数量为 $N$N，经过实践，可以知道 $N$N 约为 $50000$50000。每次扩展最多把一个数扩展成 $\log M$logM 个数，在剪枝完毕后，列表大小又回归到 $N$N 以下，故时间复杂度可以估算为 $O(NK Max(p) \log M)$O(NKMax(p)logM)，常数较小。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL, int> pii;

int pr[305], chk[305], cnt;

const int maxM = (int)(1e6);
const int maxK = 240;
const LL MAX = (LL)(1e18) + maxM;
const LL K = 233;

pii b[maxM], c[maxM];
int mx[maxK], ps[maxK];
LL va[maxM * 10];
int tot;

void upd(int x) {
	int p = K; while(p && mx[p - 1] < x) --p;
	for (int i = K; i > p; --i) mx[i] = mx[i - 1]; 
	mx[p] = x;
 }

bool valid(LL a, LL b) {
	LL ret = 0;
	for (; b; b >>= 1) {
		if (b & 1) {
			ret += a;
			if (a < 0 || ret >= MAX) return 0;
		}
		a += a; if (a >= MAX) a = -1;
	} return 1;
}

void gen() {
	int M = 293;
	for (int i = 2; i <= M; ++i) if (!chk[i]) {
		pr[++cnt] = i;
		for (int j = i + i; j <= M; j += i) chk[j] = 1;
	}
	tot = 0; b[++tot] = make_pair(1, 1);
	for (int i = 1; i <= cnt; ++i) {
		LL now = pr[i]; int idx = 0;
		for (int j = 1; j <= tot; ++j) {
			c[++idx] = b[j]; int w = 0;
			LL va = b[j].first; int di = b[j].second;
			while (valid(va, now)) {
				va *= now; ++w;
				c[++idx] = make_pair(va, di * (w + 1));
			}
		}
		sort(c + 1, c + idx + 1); tot = 0; 
		memset(mx, 0, sizeof(mx));
		for (int j = 1; j <= idx; ++j) {
			if (c[j].second >= mx[K]) {
				upd(c[j].second); b[++tot] = c[j];
			}
		}
	}
	int cur = 0;
	for (int i = 0; i <= K; ++i) {
		int cnt = 0;
		ps[i] = cur + 1;
		memset(mx, 0, sizeof(mx));
		for (int j = 1; j <= tot; ++j) {
			if (b[j].second >= mx[i]) {
				upd(b[j].second); va[++cur] = b[j].first - (cnt++);
			}
		}
	}
	ps[K + 1] = cur + 1;
}

void solve () {
	LL n; int m;
	cin >> n >> m;
	int p = upper_bound(va + ps[m], va + ps[m + 1], n) - va - ps[m];
	cout << n + p << endl;
}

int main () {
	ios::sync_with_stdio(false);
	int T;
	cin >> T; gen();
	while (T--) solve();
	return 0;
}

---

B. Harvest of Apples

定义 $S(n, m) = \sum_{i = 0} ^ {m} {n \choose i}$S(n,m)=∑i=0m​(in​)，不难发现 $S(n, m) = S(n, m - 1) + {n \choose m}, S(n, m) = 2S(n - 1, m) - {n - 1 \choose m}$S(n,m)=S(n,m−1)+(mn​),S(n,m)=2S(n−1,m)−(mn−1​)。也就是说，如果我们知道 $S(n, m)$S(n,m)，就能以 $O(1)$O(1) 的代价计算出 $S(n - 1, m), S(n, m - 1), S(n + 1, m), S(n, m + 1)$S(n−1,m),S(n,m−1),S(n+1,m),S(n,m+1)，可以采用莫队算法。

时间复杂度 $O(T \sqrt{MAX})$O(TMAX​)。

#include <bits/stdc++.h>
using namespace std;

const int N = 200000;
const int MOD = 1000000007;
struct query
{
    int n, k, i;
} Q[N];
int T;
vector <query> lst[N];
int cnt, mx, chunk;
int fac[N], inv[N], res[N], in_chunk[N];
int powi(int a, int b)
{
    int c = 1;
    for (; b; b >>= 1, a = 1ll * a * a % MOD)
        if (b & 1) c = 1ll * c * a % MOD;
    return c;
}
int C(int a, int b)
{
    return 1ll * fac[a] * inv[b] % MOD * inv[a - b] % MOD;
}
int comp(query a, query b)
{
    return a.n < b.n;
}
int main()
{
    mx = 100000;
    fac[0] = 1; for (int i = 1; i <= mx; ++ i) fac[i] = 1ll * fac[i - 1] * i % MOD;
    inv[mx] = powi(fac[mx], MOD - 2); for (int i = mx - 1; ~i; -- i) inv[i] = 1ll * inv[i + 1] * (i + 1) % MOD;
    chunk = sqrt(mx);
    cnt = 1;
    for (int i = 1; i <= mx; i += chunk, ++ cnt)
        for (int j = i; j < i + chunk && j <= mx; ++ j)
            in_chunk[j] = cnt;
    cnt --;
    scanf("%d", &T);
    for (int i = 1; i <= T; ++ i)
    {
        scanf("%d%d", &Q[i].n, &Q[i].k), Q[i].i = i;
        lst[in_chunk[Q[i].k]].push_back(Q[i]);
    }
    for (int i = 1; i <= cnt; ++ i) if (lst[i].size())
    {
        sort(lst[i].begin(), lst[i].end(), comp);
        int val = 0, in = lst[i][0].n, ik = -1;
        for (int j = 0; j < lst[i].size(); ++ j)
        {
            while (in < lst[i][j].n) val = (0ll + val + val + MOD - C(in ++, ik)) % MOD;
            while (ik < lst[i][j].k) val = (val + C(in, ++ ik)) % MOD;
            while (ik > lst[i][j].k) val = (val + MOD - C(in, ik --)) % MOD;
            res[lst[i][j].i] = val;
        }
    }
    for (int i = 1; i <= T; ++ i) printf("%d\n", res[i]);
}

---

C. Problems on a Tree

用并查集维护两种连通块 —— Easy + Medium 题的连通块，维护大小；Easy 题的连通块，维护大小以及与此连通块只隔一个 Hard 题的 Easy + Medium 连通块大小之和即可。

#include<bits/stdc++.h>
using namespace std;

int CASES;
int n,T;

struct R{
	int to,val,nex;
}r[222222];
int hea[111111]={0},cnt=1,fa[111111],dep[111111];
int f1[111111],f2[111111],sch[111111],sz2[111111];

int GF1(int x){
	return x==f1[x]? x: f1[x]=GF1(f1[x]);
}
int GF2(int x){
	return x==f2[x]? x: f2[x]=GF2(f2[x]);
}
void uni1(int y,int x){
	x=GF1(x);y=GF1(y);
	f1[y]=x;
	sch[x]+=sch[y];
}
void uni2(int y,int x){
	x=GF2(x);y=GF2(y);
	f2[y]=x;
	sz2[x]+=sz2[y];
	sch[GF1(fa[y])]-=sz2[y];
	if (fa[x]) sch[GF1(fa[x])]+=sz2[y];
}

void dfs(int x,int fff){
	fa[x]=fff;dep[x]=dep[fff]+1;
	for (int y,i=hea[x];i;i=r[i].nex){
		y=r[i].to;if (y==fff) continue;
		sch[x]++;
		dfs(y,x);
	}
	for (int y,i=hea[x];i;i=r[i].nex){
		y=r[i].to;if (y==fff) continue;
		if (r[i].val==1){
			uni2(y,x);uni1(y,x);
		}else if (r[i].val==2){
			uni2(y,x);
		}
	}
}

void doit(int x,int y){
	if (GF1(x)==GF1(y)) return;
	for (int z;(x=GF1(x))!=(y=GF1(y));x=z){
		if (dep[x]<dep[y]) swap(x,y);
		z=GF1(fa[x]);
		if (GF2(x)==GF2(z)){
			uni1(x,z);
		}else{
			uni2(x,z);
		}
	}
}

void __main(){
	scanf("%d%d",&n,&T);
	int u,v,w;
	for (int i=1;i<n;i++){
		scanf("%d%d%d",&u,&v,&w);w=max(1,w);
		r[++cnt]=(R){v,w,hea[u]};hea[u]=cnt;
		r[++cnt]=(R){u,w,hea[v]};hea[v]=cnt;
	}
	for (int i=1;i<=n;i++){
		f1[i]=f2[i]=i;
		sch[i]=0;sz2[i]=1;
	}
	dep[0]=0;
	dfs(1,0);
	int times=1;
	for (int st,en,fl,ans;T--;times++){
		scanf("%d%d%d%d",&u,&v,&en,&st);
		doit(u,v);
		fl=0;
		if (GF2(st)==GF2(en)) fl=1;
		if (GF1(fa[GF2(st)])==GF1(en)) fl=1;
		if (GF2(fa[GF1(en)])==GF2(st)) fl=1;
		sz2[0]=0;
		ans=sz2[GF2(en)]+sch[GF1(en)]\
			+( GF2(fa[GF1(en)])==GF2(en)? 0: sz2[GF2(fa[GF1(en)])] );
		printf("%d %d\n",fl,ans);
	}

    cnt = 1;
    for (int i = 1; i <= n; ++ i)
        hea[i] = 0;
    for (int i = 1; i <= n; ++ i)
        f1[i] = f2[i] = sch[i] = sz2[i] = fa[i] = dep[i] = 0;
}

int main()
{
    scanf("%d", &CASES);
    while (CASES --)
        __main();
}

---

D. Nothing is Impossible

如果仅有 1 道题，至少有一个人做对这题需要有 错误答案个数 + 1 个人。

那么容易发现在每道题正确答案只有一个的情况下，如果 $n$n 道题中存在 $s$s 道题，使得学生人数 $m$m 不少于每道题 错误答案个数 + 1 相乘的结果，那么一定有人能够得到 $s$s 分。故我们将题目按错误答案个数从小到大排序，找到最大的 $p$p 满足 $\prod_{i \le p} {(b_i + 1)} \le m$∏i≤p​(bi​+1)≤m 就是答案。

#include <bits/stdc++.h>
using namespace std;
const int N = 500000;
int n, m;
int ai[N];
void solve()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++ i)
        scanf("%*d%d", &ai[i]);
    sort(ai + 1, ai + n + 1);
    for (int i = 1, j = 1; i <= n + 1; ++ i)
        if (i == n + 1 || 1ll * j * (ai[i] + 1) > m)
        {
            printf("%d\n", i - 1);
            break;
        }
        else j *= (ai[i] + 1);
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T --) solve();
}

---

E. Matrix from Arrays

简单推导可得

$M[i][j] = A[(\frac{(i + j)(i + j + 1)}{2} + i) \mod L] = A[(\frac{3i}{2} + \frac{j}{2} + \frac{i ^ 2} {2} + \frac{j ^ 2}{2} + ij) \mod L] = M[i + 2L][j] = M[i][j + 2L]$M[i][j]=A[(2(i+j)(i+j+1)​+i)modL]=A[(23i​+2j​+2i2​+2j2​+ij)modL]=M[i+2L][j]=M[i][j+2L]

预处理左上角 $2L \times 2L$2L×2L 的矩阵的二维前缀和，$O(1)$O(1) 回答询问。时间复杂度 $O(L ^ 2 + Q)$O(L2+Q)。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

int A[10], M[400][400];
int L;

LL calc (int n, int m) {
    if (n < 0 || m < 0) return 0;
    return 1LL * M[L - 1][L - 1] * (n / L) * (m / L) + \
           1LL * M[n % L][L - 1] * (m / L) + \
           1LL * M[L - 1][m % L] * (n / L) + \
           1LL * M[n % L][m % L];
}

void solve () {
    cin >> L;
    for (int i = 0; i < L; ++i) cin >> A[i];
    int k = 0;
    for (int i = 0; i < 4 * L; ++i) {
        for (int j = 0; j <= i; ++j) {
            if (j < 2 * L && i - j < 2 * L) M[j][i - j] = A[k];
            k = (k + 1) % L;
        }
    }
    L *= 2;
    for (int i = 0; i < L; ++i) for (int j = 0; j < L; ++j) {
        if (i) M[i][j] += M[i - 1][j];
        if (j) M[i][j] += M[i][j - 1];
        if (i && j) M[i][j] -= M[i - 1][j - 1];
    }
    int Q; cin >> Q;
    while (Q--) {
        int xL, yL, xR, yR;
        cin >> xL >> yL >> xR >> yR;
        cout << calc(xR, yR) - calc(xL - 1, yR) - calc(xR, yL - 1) + calc(xL - 1, yL - 1) << endl;
    }
}

int main () {
    ios::sync_with_stdio(false);
    int T; cin >> T;
    while (T--) solve();
    return 0;
}

---

F. Travel Through Time

由于可持久化的存在，直接维护哪些位置有棋子十分困难。考虑维护一些全是棋子的线段，这些线段可以有重叠部分，但是需要保证这些线段覆盖了所有的棋子。

注意到如果我们只维护了线段的左右边界，甚至不用知道某个左边界具体对应的是哪个右边界，就可以知道某个位置上有没有棋子。因此只维护左右边界，把左边界看成左括号，右边界看成右括号，那么这就是一个括号序列。

比如说对于 0111011110 这样一串格子（1表示有棋子，0表示没有），我们可以用这样的括号序列来维护：0(111)0(1111)0。由于一个局面并不对应了唯一的括号序列，因此这些括号序列也是可以的：0(111)0(11)(11)0，0(1(1(1)))0(((11(11))))0。

对于每一个操作，都可以用括号序列维护：

• 操作一：在 $x$x 前加入一对括号。

• 操作二：将所有左括号向左移动 $x$x，将所有右括号向右移动 $x$x。

• 操作三：在 $l$l 的前面与 $r$r 的后面加入形如 ... )))((( ... 的括号使得没有线段穿过 $l$l 和 $r$r。然后将 $l, r$l,r之间的括号直接翻转并反转。比如说对于 0(111)0(11(1)1)0，如果要翻转 $[3,8]$[3,8]，首先补充括号，变成：0(1] [11)0(11(1]] [[1)1)0（为了区分,[与]是新加入的括号），然后翻转，得到：0(1] [[1)11)0(11] [[)1)0。

对于左括号与右括号，分别开一棵可持久化 Treap 维护即可。时间复杂度 $O(n \log n)$O(nlogn)。

#include <bits/stdc++.h>
using namespace std;

#define LL long long
const int N = 300000;
const int M = 5000000;
struct point
{
    int left, right, stamp, size;
    int rev; LL add, pos;
    int val, sum;
} tr[M];

int now, tot, key, n;
int rtL[N], rtR[N];

int check(int t)
{
    if (tr[t].stamp != now)
    {
        int p = ++ tot;
        tr[p] = tr[t];
        tr[p].stamp = now;
        return p;
    }
    else return t;
}
int upd(int t)
{
    if (!t) return 0;
    tr[t].sum = tr[tr[t].left].sum + tr[tr[t].right].sum + tr[t].val;
    tr[t].size = tr[tr[t].left].size + tr[tr[t].right].size + 1;
    return t;
}
int rev(int t)
{
    if (!t) return 0;
    t = check(t);
    tr[t].rev ^= 1;
    tr[t].add *= -1;
    tr[t].pos *= -1;
    swap(tr[t].left, tr[t].right);
    return t;
}
int add(int t, LL v)
{
    if (!t) return 0;
    t = check(t);
    tr[t].add += v;
    tr[t].pos += v;
    return t;
}
int psdw(int t)
{
    if (!t) return 0;
    t = check(t);
    if (tr[t].rev)
    {
        if (tr[t].left) tr[t].left = rev(tr[t].left);
        if (tr[t].right) tr[t].right = rev(tr[t].right);
        tr[t].rev = 0;
    }
    if (tr[t].add)
    {
        if (tr[t].left) tr[t].left = add(tr[t].left, tr[t].add);
        if (tr[t].right) tr[t].right = add(tr[t].right, tr[t].add);
        tr[t].add = 0;
    }
    return t;
}
void split(int t, LL p, int &l, int &r)
{
    if (!t) {l = r = 0; return;}
    t = psdw(t);
    if (p <= tr[t].pos)
    {
        split(tr[t].left, p, l, r);
        tr[t].left = r; r = upd(t);
    }
    else
    {
        split(tr[t].right, p, l, r);
        tr[t].right = l; l = upd(t);
    }
}
int merge(int a, int b)
{
    if (!a || !b) return a | b;
    if (1ll * rand() * (tr[a].size + tr[b].size) < 1ll * tr[a].size * RAND_MAX)
    {
        a = psdw(a); tr[a].right = merge(tr[a].right, b); return upd(a);
    }
    else
    {
        b = psdw(b); tr[b].left = merge(a, tr[b].left); return upd(b);
    }
}
void init(LL pos, int &l, int &r, int v)
{
    l = ++ tot; r = ++ tot;
    tr[l].stamp = tr[r].stamp = now;
    tr[l].pos = tr[r].pos = pos;
    tr[l].val = tr[r].val = v;
    upd(l); upd(r);
}
void solve(istream &in, ostream &os, int online = 1)
{
    for (int i = 1; i <= n; ++ i) rtL[i] = rtR[i] = 0;
    for (int i = 1; i <= tot; ++ i) tr[i] = tr[0]; key = tot = now = 0;
    in >> n;
    init(0, rtL[0], rtR[0], 1);
    for (int i = 1; i <= n; ++ i)
    {
        int opt; LL x, l, r; now = i;
        int Ll, Lr, Lm, Rl, Rr, Rm;
        in >> opt;
        rtL[i] = rtL[i - 1]; rtR[i] = rtR[i - 1];
        if (opt == 1)
        {
            in >> x; x ^= key;
            split(rtL[i], x, Ll, Lr);
            split(rtR[i], x, Rl, Rr);
            init(x, Lm, Rm, 1);
            rtL[i] = merge(merge(Ll, Lm), Lr);
            rtR[i] = merge(merge(Rl, Rm), Rr);
        }
        else if (opt == 2)
        {
            in >> x; x ^= key;
            rtL[i] = add(rtL[i], -x);
            rtR[i] = add(rtR[i], x);
        }
        else if (opt == 3)
        {
            in >> l >> r; l ^= key; r ^= key;
            split(rtL[i], l, Ll, Lr); split(Lr, r + 1, Lm, Lr);
            split(rtR[i], l, Rl, Rr); split(Rr, r + 1, Rm, Rr);
            int Lx, Ly, Rx, Ry;
            init(0, Lx, Ly, tr[Rr].sum - tr[Lr].sum);
            tr[Lx].pos = l; tr[Ly].pos = r + 1;
            init(0, Rx, Ry, tr[Ll].sum - tr[Rl].sum);
            tr[Rx].pos = l - 1; tr[Ry].pos = r;
            rtL[i] = merge(merge(merge(Ll, Lx), add(rev(Rm), l + r)), merge(Ly, Lr));
            rtR[i] = merge(merge(merge(Rl, Rx), add(rev(Lm), l + r)), merge(Ry, Rr));
        }
        else if (opt == 4)
        {
            in >> x; x ^= key;
            rtL[i] = rtL[x]; rtR[i] = rtR[x];
        }
        else
        {
            in >> x; x ^= key;
            split(rtL[i], x + 1, Ll, Lr);
            split(rtR[i], x, Rl, Rr);
            if (tr[Ll].sum ^ tr[Rl].sum)
                os << "Yes" << endl, key += online;
                else os << "No" << endl;
            rtL[i] = rtL[i - 1]; rtR[i] = rtR[i - 1];
        }
    }
    // cerr << key << endl;
}

int main()
{
    ios::sync_with_stdio(0);
    int T;
    for (cin >> T; T; T --) solve(cin, cout);
}

---

G. Depth-First Search

由于题目和字典序有关，不妨运用逐位确定的思想。

首先，我们要求第一位小于 $B_1$B1​ 的序列总数，即我们需要快速求出以每个点为根时的DFS序列总数。对于有根树，设 $f(i)$f(i) 为以 $i$i 为根的子树的DFS序列总数，有

$f(u) = |son(u)|! \prod_{v \in son(u)} {f(v)}$f(u)=∣son(u)∣!v∈son(u)∏​f(v)

我们可以先任选一个根 DFS 求出 $f$f，在第二遍 DFS 考虑祖先的贡献即可将所有点的答案求出。

接着我们以 $B_1$B1​ 为根，逐位确定求出所有的答案。和上述方法类似，即如果当前在 $B_i$Bi​ 点，要走到 $B_{i+1}$Bi+1​ 点，需要求出所有第 $i + 1$i+1 位小于 $B_{i+1}$Bi+1​ 的方案数，简单计算即可。

需要注意的是，由于我们可能需要快速计算某个点下某个子树的名次，所以需要用树状数组或线段树来优化这个过程。

时间复杂度 $O(n \log n)$O(nlogn)。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
  
#define lowbit(x) ((x) & (-x))
  
LL pow_mod(LL b, LL p, LL k) {
    LL ret = 1;
    for (; p; p >>= 1) {
        if (p & 1) ret = ret * b % k;
        b = b * b % k;
    } return ret;
}
  
const int maxn = (int)(2e6) + 5;
const int mo = (int)(1e9) + 7;
  
int b[maxn], son[maxn];
vector<int> nxt[maxn], C[maxn];
LL f[maxn], g[maxn], fac[maxn], ret;
  
void dfs(int x, int fa) {
    f[x] = 1;
    if (fa) nxt[x].erase(find(nxt[x].begin(), nxt[x].end(), fa));
    son[x] = nxt[x].size(); nxt[x].insert(nxt[x].begin(), 0); C[x].push_back(0);
    for (int i = 1; i <= son[x]; ++i) {
        dfs(nxt[x][i], x); f[x] = f[x] * f[nxt[x][i]] % mo; C[x].push_back(0);
    } LL w;
    w = 1; for (int i = 1; i <= son[x]; ++i) g[nxt[x][i]] = w, w = w * f[nxt[x][i]] % mo;
    w = 1; for (int i = son[x]; i >= 1; --i) (g[nxt[x][i]] *= w) %= mo, w = w * f[nxt[x][i]] % mo;
    f[x] = f[x] * fac[son[x]] % mo;
}
  
void calcPre(int x, LL v) {
    int cnt = son[x];
    if (x == b[1]) --cnt;
    else if (x < b[1]) (ret += (f[x] * v % mo) * (cnt + 1) % mo) %= mo;
    for (int i = 1; i <= son[x]; ++i) calcPre(nxt[x][i], (v * g[nxt[x][i]] % mo) * fac[cnt] % mo);
}
  
inline void add(int p, int x, int v) {
    for (; x <= son[p]; x += lowbit(x)) C[p][x] += v;
}
  
inline int sum(int p, int x) {
    int ret = 0; for (; x; x -= lowbit(x)) ret += C[p][x]; return ret;
}
  
inline int findNxt(int p, int x) {
    int ps = 0;
    for (int i = 20; i >= 0; --i) if (ps + (1 << i) <= son[p] && nxt[p][ps + (1 << i)] < x) ps += (1 << i);
    return ps;
}
  
int idx;
bool calcNow(int x, LL v) {
    LL now = 1; ++idx;
    for (int i = 1; i <= son[x]; ++i) now = now * f[nxt[x][i]] % mo, add(x, i, 1);
    for (int i = son[x] - 1; i >= 0; --i) {
        int s = findNxt(x, b[idx + 1]);
        (ret += ((fac[i] * now % mo) * sum(x, s) % mo) * v % mo) %= mo; ++s;
        if (s > son[x] || nxt[x][s] != b[idx + 1]) return 1;
        add(x, s, -1); now = now * pow_mod(f[nxt[x][s]], mo - 2, mo) % mo;
        if (calcNow(nxt[x][s], (v * fac[i] % mo) * now % mo)) return 1;
    } return 0;
}

void solve () {
    int n; idx = 0;
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> b[i], nxt[i].clear(), C[i].clear();
    for (int i = 2; i <= n; ++i) {
        int u, v; cin >> u >> v;
        nxt[u].push_back(v); nxt[v].push_back(u);
    }
    b[n + 1] = 0; g[0] = 1; ret = 0;
    for (int i = 1; i <= n; ++i) sort(nxt[i].begin(), nxt[i].end());
    dfs(b[1], 0); calcPre(b[1], 1); calcNow(b[1], 1);
    cout << ret << endl;
}

int main() {
    ios::sync_with_stdio(false);
    int MAX = (int)(1e6);
    fac[0] = 1;
    for (int i = 1; i <= MAX; ++i) fac[i] = fac[i - 1] * i % mo;
    int T; cin >> T;
    while (T--) solve();
    return 0;
}

---

H. Eat Cards, Have Fun

考虑如何计算某个特定排列 $A$A 的 Value.

KaTeX parse error: Expected '}', got '&' at position 49: … - i)! \sum_{j &̲gt; i} {[A_j &l…

这启发我们对于每个 $i$i 分别计算贡献。考虑当第 $i$i 张卡片被吃掉的时候，我们需要知道这张卡片左边、右边分别已有多少卡片被吃掉（记为 $l, r$l,r），才能确定第 $i$i 张卡片在 $A$A 中的位置；我们还需要知道这张卡片左边、右边分别已有多少卡面数字小于 $a_i$ai​ 的卡片被吃掉（记为 $\hat{l}, \hat{r}$l^,r^），才能确定第 $i$i 张卡片对答案的贡献，即 KaTeX parse error: Expected '}', got '&' at position 9: \sum_{j &̲gt; i} {[A_j &l…。如果知道了 $l, r, \hat{l}, \hat{r}$l,r,l^,r^，那么答案就是

$Ans = \sum_{i = 1} ^ {n} \sum_{l = 0} ^ {i - 1} \sum_{r = 0} ^ {n - i} \sum_{\hat{l} = 0} ^ {l} \sum_{\hat{r} = 0} ^ {r} {(n - l - r - 1)! (a_i - 1 - \hat{l} - \hat{r}) P(i, l, r, \hat{l}, \hat{r})}$Ans=i=1∑n​l=0∑i−1​r=0∑n−i​l^=0∑l​r^=0∑r​(n−l−r−1)!(ai​−1−l^−r^)P(i,l,r,l^,r^)

其中 $P(i, l, r, \hat{l}, \hat{r})$P(i,l,r,l^,r^) 是达到对应情况的概率。我们可以枚举第 $i$i 张卡片是在第 $k$k 轮 KaTeX parse error: Expected 'EOF', got '&' at position 4: (k &̲gt; 0) 被吃掉的来计算概率：

$P(i, l, r, \hat{l}, \hat{r}) = {b_i \choose \hat{l}} {i - b_i - 1 \choose l - \hat{l}} {a_i - b_i - 1 \choose \hat{r}} {n - i - a_i + b_i + 1 \choose r - \hat{r}} \sum_{k = 1} ^ {\infty} {(1 - (1 - p) ^ k) ^ l ((1 - p) ^ k) ^ {i - 1 - l} p (1 - p) ^ {k - 1} (1 - (1 - p) ^ {k - 1}) ^ r ((1 - p) ^ {k - 1}) ^ {n - i - r}}$P(i,l,r,l^,r^)=(l^bi​​)(l−l^i−bi​−1​)(r^ai​−bi​−1​)(r−r^n−i−ai​+bi​+1​)k=1∑∞​(1−(1−p)k)l((1−p)k)i−1−lp(1−p)k−1(1−(1−p)k−1)r((1−p)k−1)n−i−r

其中 KaTeX parse error: Expected '}', got '&' at position 15: b_i = \sum_{j &̲lt; i} {[a_j &l….

观察式子 $(1 - (1 - p) ^ x) ^ y$(1−(1−p)x)y，可以用二项式定理展开：

$(1 - (1 - p) ^ x) ^ y = \sum_{i = 0} ^ {y} {{y \choose i} (-1) ^ i (1 - p) ^ {xi}}$(1−(1−p)x)y=i=0∑y​(iy​)(−1)i(1−p)xi

利用上述结论，进一步化简：

$\begin{aligned} & \sum_{k = 1} ^ {\infty} {(1 - (1 - p) ^ k) ^ l ((1 - p) ^ k) ^ {i - 1 - l} p (1 - p) ^ {k - 1} (1 - (1 - p) ^ {k - 1}) ^ r ((1 - p) ^ {k - 1}) ^ {n - i - r}} \\ = & p \sum_{k = 1} ^ {\infty} {(1 - p) ^ {k(i - 1 - l) + k - 1 + (k - 1)(n - i - r)} \sum_{x = 0} ^ {l} {{l \choose x} (-1) ^ x (1 - p) ^ {xk}} \sum_{y = 0} ^ {r} {{r \choose y} (-1) ^ y (1 - p) ^ {y(k - 1)}}} \\ = & p \sum_{x = 0} ^ {l} \sum_{y = 0} ^ {r} {(-1) ^ {x + y} {l \choose x} {r \choose y} \sum_{k = 1} ^ {\infty} {(1 - p) ^ {k(i - 1 - l) + k - 1 + (k - 1)(n - i - r) + xk + y(k - 1)}}} \\ = & p \sum_{x = 0} ^ {l} \sum_{y = 0} ^ {r} {(-1) ^ {x + y} {l \choose x} {r \choose y} \sum_{k = 0} ^ {\infty} {(1 - p) ^ {k (n - l - r + x + y) + (i - 1 - l + x)}}} \\ = & p \sum_{x = 0} ^ {l} \sum_{y = 0} ^ {r} {(-1) ^ {x + y} {l \choose x} {r \choose y} \frac{(1 - p) ^ {i - 1 - l + x}} {1 - (1 - p) ^ {n - l - r + x + y}}} \end{aligned}$====​amp;k=1∑∞​(1−(1−p)k)l((1−p)k)i−1−lp(1−p)k−1(1−(1−p)k−1)r((1−p)k−1)n−i−ramp;pk=1∑∞​(1−p)k(i−1−l)+k−1+(k−1)(n−i−r)x=0∑l​(xl​)(−1)x(1−p)xky=0∑r​(yr​)(−1)y(1−p)y(k−1)amp;px=0∑l​y=0∑r​(−1)x+y(xl​)(yr​)k=1∑∞​(1−p)k(i−1−l)+k−1+(k−1)(n−i−r)+xk+y(k−1)amp;px=0∑l​y=0∑r​(−1)x+y(xl​)(yr​)k=0∑∞​(1−p)k(n−l−r+x+y)+(i−1−l+x)amp;px=0∑l​y=0∑r​(−1)x+y(xl​)(yr​)1−(1−p)n−l−r+x+y(1−p)i−1−l+x​​

至此，我们获得了一个时间复杂度为 $O(n ^ 5)$O(n5) 的算法。上述公式显然有不少冗余，可以进一步优化。

回顾原式：

$Ans = p \sum_{i = 1} ^ {n} \sum_{l = 0} ^ {i - 1} \sum_{r = 0} ^ {n - i} {(n - l - r - 1)! (\sum_{x = 0} ^ {l} \sum_{y = 0} ^ {r} {(-1) ^ {x + y} {l \choose x} {r \choose y} \frac{(1 - p) ^ {i - 1 - l + x}} {1 - (1 - p) ^ {n - l - r + x + y}}}) (\sum_{\hat{l} = 0} ^ {l} \sum_{\hat{r} = 0} ^ {r} {(a_i - 1 - \hat{l} - \hat{r}) {b_i \choose \hat{l}} {i - b_i - 1 \choose l - \hat{l}} {a_i - b_i - 1 \choose \hat{r}} {n - i - a_i + b_i + 1 \choose r - \hat{r}}})}$Ans=pi=1∑n​l=0∑i−1​r=0∑n−i​(n−l−r−1)!(x=0∑l​y=0∑r​(−1)x+y(xl​)(yr​)1−(1−p)n−l−r+x+y(1−p)i−1−l+x​)(l^=0∑l​r^=0∑r​(ai​−1−l^−r^)(l^bi​​)(l−l^i−bi​−1​)(r^ai​−bi​−1​)(r−r^n−i−ai​+bi​+1​))

以下将定义若干辅助函数加速计算答案。

---

定义 $F$F：
$F(i, l, r) = \sum_{x = 0} ^ {l} \sum_{y = 0} ^ {r} {(-1) ^ {x + y} {l \choose x} {r \choose y} \frac{(1 - p) ^ {i - 1 - l + x}} {1 - (1 - p) ^ {n - l - r + x + y}}}$F(i,l,r)=x=0∑l​y=0∑r​(−1)x+y(xl​)(yr​)1−(1−p)n−l−r+x+y(1−p)i−1−l+x​

考虑如何快速计算 $F$F。不妨定义 $F_n$Fn​：

$F_n(l, r) = \sum_{x = 0} ^ {l} \sum_{y = 0} ^ {r} {(-1) ^ {x + y} {l \choose x} {r \choose y} \frac{(1 - p) ^ {n - 1 - l + x}} {1 - (1 - p) ^ {n - l - r + x + y}}}$Fn​(l,r)=x=0∑l​y=0∑r​(−1)x+y(xl​)(yr​)1−(1−p)n−l−r+x+y(1−p)n−1−l+x​

显然 $F(i, l, r) = F_n(l, r) (1 - p) ^ {i - n}$F(i,l,r)=Fn​(l,r)(1−p)i−n。

$F_n(l, r) = l! r! \sum_{x = 0} ^ {l} \sum_{y = 0} ^ {r} {\frac{(-1) ^ x} {x!} \frac{(-1) ^ y} {y!} \frac{(1 - p) ^ {n - 1 - (l - x)}} {(l - x)! (r - y)! (1 - (1 - p) ^ {n - (l - x) - (r - y)})}}$Fn​(l,r)=l!r!x=0∑l​y=0∑r​x!(−1)x​y!(−1)y​(l−x)!(r−y)!(1−(1−p)n−(l−x)−(r−y))(1−p)n−1−(l−x)​

令 $G(x, y) = \frac{(1 - p) ^ {n - 1 - x}} {x! y! (1 - (1 - p) ^ {n - x - y})}$G(x,y)=x!y!(1−(1−p)n−x−y)(1−p)n−1−x​：

$F_n(l, r) = l! r! \sum_{x = 0} ^ {l} {\frac{(-1) ^ x} {x!} \sum_{y = 0} ^ {r} {\frac{(-1) ^ y} {y!} G(l - x, r - y)}}$Fn​(l,r)=l!r!x=0∑l​x!(−1)x​y=0∑r​y!(−1)y​G(l−x,r−y)

可以在 $O(n ^ 3)$O(n3) 的时间计算出 $F_n$Fn​。

---

定义 $L, R, L_{+}, R_{+}, H$L,R,L+​,R+​,H：

$L(i, l) = \sum_{\hat{l} = 0} ^ {l} {{b_i \choose \hat{l}} {i - b_i - 1 \choose l - \hat{l}}}, R(i, r) = \sum_{\hat{r} = 0} ^ {r} {{a_i - b_i - 1 \choose \hat{r}} {n - i - a_i + b_i + 1 \choose r - \hat{r}}}$L(i,l)=l^=0∑l​(l^bi​​)(l−l^i−bi​−1​),R(i,r)=r^=0∑r​(r^ai​−bi​−1​)(r−r^n−i−ai​+bi​+1​)

$L_{+}(i, l) = \sum_{\hat{l} = 0} ^ {l} {\hat{l} {b_i \choose \hat{l}} {i - b_i - 1 \choose l - \hat{l}}}, R_{+}(i, r) = \sum_{\hat{r} = 0} ^ {r} {\hat{r} {a_i - b_i - 1 \choose \hat{r}} {n - i - a_i + b_i + 1 \choose r - \hat{r}}}$L+​(i,l)=l^=0∑l​l^(l^bi​​)(l−l^i−bi​−1​),R+​(i,r)=r^=0∑r​r^(r^ai​−bi​−1​)(r−r^n−i−ai​+bi​+1​)

$H(i, l, r) = \sum_{\hat{l} = 0} ^ {l} \sum_{\hat{r} = 0} ^ {r} {(a_i - 1 - \hat{l} - \hat{r}) {b_i \choose \hat{l}} {i - b_i - 1 \choose l - \hat{l}} {a_i - b_i - 1 \choose \hat{r}} {n - i - a_i + b_i + 1 \choose r - \hat{r}}} = (a_i - 1) L(i, l) R(i, r) - L_{+}(i, l) R(i, r) - L(i, l) R_{+}(i, r)$H(i,l,r)=l^=0∑l​r^=0∑r​(ai​−1−l^−r^)(l^bi​​)(l−l^i−bi​−1​)(r^ai​−bi​−1​)(r−r^n−i−ai​+bi​+1​)=(ai​−1)L(i,l)R(i,r)−L+​(i,l)R(i,r)−L(i,l)R+​(i,r)

以 $O(n ^ 3)$O(n3) 的代价预处理 $L, R, L_{+}, R_{+}$L,R,L+​,R+​, 可以在 $O(n ^ 3)$O(n3) 的时间计算出 $H$H。

---

现在 $Ans$Ans 就可以在 $O(n ^ 3)$O(n3) 的时间计算出来啦。

$Ans = p \sum_{i = 1} ^ {n} \sum_{l = 0} ^ {i - 1} \sum_{r = 0} ^ {n - i} {(n - l - r - 1)! F_n(l, r) (1 - p) ^ {i - n} H(i, l, r)}$Ans=pi=1∑n​l=0∑i−1​r=0∑n−i​(n−l−r−1)!Fn​(l,r)(1−p)i−nH(i,l,r)

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

LL pow_mod(LL b, LL p, LL k) {
    LL ret = 1;
    for (; p; p >>= 1) {
        if (p & 1) ret = ret * b % k;
        b = b * b % k;
    }
    return ret;
}

const int maxn = 305;
const int mo = (int)(1e9) + 7;
const LL mo2 = 1LL * mo * mo;
int a[maxn], b[maxn];
LL fac[maxn], ivf[maxn], h[maxn];
LL C[maxn][maxn];
LL g1[maxn][maxn];
LL g2[maxn][maxn];
LL l0[maxn][maxn];
LL l1[maxn][maxn];
LL r0[maxn][maxn];
LL r1[maxn][maxn];
LL pw[maxn];

LL P;

void add(LL& x, LL v) {
    x += v; if (x >= mo2) x -= mo2;
}

void gen () {
    int M = 300;
    fac[0] = ivf[0] = 1;
    for (int i = 1; i <= M; ++i) fac[i] = fac[i - 1] * i % mo;
    ivf[M] = pow_mod(fac[M], mo - 2, mo);
    for (int i = M - 1; i >= 1; --i) ivf[i] = ivf[i + 1] * (i + 1) % mo;
    for (int i = 0; i <= M; ++i) C[i][0] = 1;
    for (int i = 1; i <= M; ++i) for (int j = 1; j <= i; ++j) C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mo;

    for (int i = 0; i <= M; ++i) h[i] = ((i & 1) ? mo - 1 : 1) * ivf[i] % mo;
}

void solve () {
    int n, _p, _q;
    cin >> n;
    cin >> _p >> _q;
    P = (1 + (mo -_p) * pow_mod(_q, mo - 2, mo)) % mo;
    pw[0] = 1;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i]; b[i] = 0; pw[i] = pw[i - 1] * P % mo;
        for (int j = 1; j < i; ++j) if (a[j] < a[i]) ++b[i];
    }
    
    memset(g2, 0, sizeof(g2));
    for (int i = 0; i < n; ++i) for (int j = 0; j < n - i; ++j) {
        g1[i][j] = pow_mod(P, n - 1 - i, mo) * ivf[i] % mo * ivf[j] % mo * pow_mod((1 + mo - pow_mod(P, n - i - j, mo)), mo - 2, mo) % mo;
        for (int k = 0; k < n - i - j; ++k) add(g2[i + k][j], g1[i][j] * h[k]);
    }
    for (int i = 0; i < n; ++i) for (int j = 0; j < n - i; ++j) g2[i][j] %= mo;
    memset(g1, 0, sizeof(g1));
    for (int i = 0; i < n; ++i) for (int j = 0; j < n - i; ++j) {
        for (int k = 0; k < n - i - j; ++k) add(g1[i][j + k], g2[i][j] * h[k]);
    }
    for (int i = 0; i < n; ++i) for (int j = 0; j < n - i; ++j) g1[i][j] = g1[i][j] % mo * fac[i] % mo * fac[j] % mo;

    for (int i = 1; i <= n; ++i) for (int j = 0; j < n; ++j) {
        l0[i][j] = l1[i][j] = r0[i][j] = r1[i][j] = 0;
        for (int k = 0; k <= j; ++k) {
            LL v = C[b[i]][k] * C[i - b[i] - 1][j - k] % mo;
            add(l0[i][j], v); add(l1[i][j], v * k);
            v = C[a[i] - b[i] - 1][k] * C[n - i - a[i] + b[i] + 1][j - k] % mo;
            add(r0[i][j], v); add(r1[i][j], v * k);
        }
        l0[i][j] %= mo; l1[i][j] %= mo; r0[i][j] %= mo; r1[i][j] %= mo;
    }
    
    LL ret = 0;
    for (int i = 1; i <= n; ++i) for (int j = 0; j < i; ++j) for (int k = 0; k <= n - i; ++k) {
        LL w = (l0[i][j] * r0[i][k] % mo * (a[i] - 1) + (mo - l1[i][j]) * r0[i][k] + (mo - l0[i][j]) * r1[i][k]) % mo;
        add(ret, fac[n - j - k - 1] * g1[j][k] % mo * pw[i] % mo * w);
    }

    ret = ret % mo * pow_mod(pow_mod(P, n, mo), mo - 2, mo) % mo * (1 + mo - P) % mo;
    cout << (ret + 1) % mo << endl;
}

int main () {
    gen();
    ios::sync_with_stdio(false);
    int T; cin >> T;
    while (T--) solve();
    return 0;
}

---

I. Delighful Formulas

根据题意列出式子：

$Ans = \sum_{i = 1} ^ {N} {[\gcd(i, N) = 1] \sum_{j = 1} ^ {i} {j ^ K}}$Ans=i=1∑N​[gcd(i,N)=1]j=1∑i​jK

莫比乌斯反演：

$\begin{aligned} Ans & = \sum_{d \mid N} {\mu(d) \sum_{i = 1} ^ {N} {[d \mid i] \sum_{j = 1} ^ {i} {j ^ K}}} \\ & = \sum_{d \mid N} {\mu(d) \sum_{i = 1} ^ {\frac{N} {d}} \sum_{j = 1} ^ {id} {j ^ K}}\end{aligned}$Ans​amp;=d∣N∑​μ(d)i=1∑N​[d∣i]j=1∑i​jKamp;=d∣N∑​μ(d)i=1∑dN​​j=1∑id​jK​

定义 $F$F：

$F_p(N) = \sum_{i = 1} ^ {N} {i ^ p}$Fp​(N)=i=1∑N​ip

显然 $F_p$Fp​ 是 $p + 1$p+1 阶多项式：

$F_p(N) = \sum_{i = 0} ^ {p + 1} {a_{p, i} N ^ i}$Fp​(N)=i=0∑p+1​ap,i​Ni

利用 $F$F 化简原式：

$\begin{aligned} Ans & = \sum_{d \mid N} {\mu(d) \sum_{i = 1} ^ {\frac{N} {d}} {F_K(id)}} \\ & = \sum_{d \mid N} {\mu(d) \sum_{i = 1} ^ {\frac{N} {d}} \sum_{j = 0} ^ {K + 1} {a_{K, j} (id) ^ j}} \\ & = \sum_{d \mid N} {\mu(d) \sum_{j = 0} ^ {K + 1} {a_{K, j} d ^ j \sum_{i = 1} ^ {\frac{N} {d}} {i ^ j}}} \\ & = \sum_{d \mid N} {\mu(d) \sum_{j = 0} ^ {K + 1} {a_{K, j} d ^ j F_j(\frac{N}{d})}} \\ & = \sum_{d \mid N} {\mu(d) \sum_{j = 0} ^ {K + 1} {a_{K, j} d ^ j \sum_{k = 0} ^ {j + 1} {a_{j, k} (\frac{N} {d}) ^ k}}} \\ & = \sum_{d \mid N} {\mu(d) \sum_{i = -1} ^ {K + 1} {d ^ i \sum_{j = 0} ^ {K + 1} \sum_{k = 0} ^ {j + 1} {[j - k = i] a_{K, j} a_{j, k} N ^ k}}} \end{aligned}$Ans​amp;=d∣N∑​μ(d)i=1∑dN​​FK​(id)amp;=d∣N∑​μ(d)i=1∑dN​​j=0∑K+1​aK,j​(id)jamp;=d∣N∑​μ(d)j=0∑K+1​aK,j​dji=1∑dN​​ijamp;=d∣N∑​μ(d)j=0∑K+1​aK,j​djFj​(dN​)amp;=d∣N∑​μ(d)j=0∑K+1​aK,j​djk=0∑j+1​aj,k​(dN​)kamp;=d∣N∑​μ(d)i=−1∑K+1​dij=0∑K+1​k=0∑j+1​[j−k=i]aK,j​aj,k​Nk​

定义 $G$G：

$G_i = \sum_{j = 0} ^ {K + 1} \sum_{k = 0} ^ {j + 1} {[j - k = i] a_{K, j} a_{j, k} N ^ k}$Gi​=j=0∑K+1​k=0∑j+1​[j−k=i]aK,j​aj,k​Nk

利用 $G$G 化简原式：

$\begin{aligned} Ans & = \sum_{d \mid N} {\mu(d) \sum_{i = -1} ^ {K + 1} {d ^ i G_i}} \\ & = \sum_{i = -1} ^ {K + 1} {G_i \sum_{d \mid N} {\mu(d) d ^ i}} \\ & = \sum_{i = -1} ^ {K + 1} {G_i \prod_{p \mid N} {(1 - p ^ i)}} \end{aligned}$Ans​amp;=d∣N∑​μ(d)i=−1∑K+1​diGi​amp;=i=−1∑K+1​Gi​d∣N∑​μ(d)diamp;=i=−1∑K+1​Gi​p∣N∏​(1−pi)​

如果我们能快速计算出 $G$G，就可以在 $O(MK)$O(MK) 的时间计算答案，其中 $M$M 为质因子个数。

将 $G$G 用伯努利数展开，可以发现是卷积的形式，直接 NTT，时间复杂度 $O(K \log K)$O(KlogK)。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

LL pow_mod(LL b, LL p, LL k) {
    LL ret = 1;
    for (; p; p >>= 1) {
        if (p & 1) ret = ret * b % k;
        b = b * b % k;
    }
    return ret;
}

const int maxn = (int)(3e5) + 5;
const int mo = 998244353;
const int rt = 3;
LL fac[maxn], ivf[maxn], B[maxn];
LL T[2][maxn], P[maxn], Q[maxn];
int K;

inline LL C(int n, int m) {
    return fac[n] * ivf[m] % mo * ivf[n - m] % mo;
}

void ntt(LL a[], int n, int d = 1) {
	for (int i = (n >> 1), j = 1; j < n; ++j) {
		if (i < j) swap(a[i], a[j]);
		int k; for (k = (n >> 1); i & k; i ^= k, k >>= 1); i ^= k;
	}
	for (int m = 2; m <= n; m <<= 1) {
		LL w = pow_mod(rt, 1LL * (mo - 1) / m * (mo - 1 + d), mo);
		for (int i = 0; i < n; i += m) {
			LL s = 1;
			for (int j = i; j < i + (m >> 1); ++j) {
				LL u = a[j], v = a[j + (m >> 1)] * s % mo;
				a[j] = u + v; a[j + (m >> 1)] = u - v; s = s * w % mo;
				if (a[j] >= mo) a[j] -= mo; 
				if (a[j + (m >> 1)] < 0) a[j + (m >> 1)] += mo;

			}
		}
	}
	if (d == -1) {
		LL xinv = pow_mod(n, mo - 2, mo);
		for (int i = 0; i < n; ++i) a[i] = a[i] * xinv % mo;
	}
}

void inverse(LL a[], LL b[], LL c[], int n) {
    int stk[22];
    for (stk[0] = 0; n > 1; stk[++stk[0]] = n, n = (n + 1) >> 1);
    b[0] = pow_mod(a[0], mo - 2, mo);
    for (int i = stk[0]; i >= 1; --i) {
        int m = stk[i], len = 0;
        while ((1 << len) < (m << 1)) ++len;
        for (int i = 0; i < m; ++i) c[i] = a[i];
        for (int i = m; i < (1 << len); ++i) c[i] = 0;
        ntt(b, 1 << len); ntt(c, 1 << len);
        for (int i = 0; i < (1 << len); ++i) b[i] = ((mo - c[i]) * b[i] + 2) % mo * b[i] % mo;
        ntt(b, 1 << len, -1);
        for (int i = m; i < (1 << len); ++i) b[i] = 0;
    }
}

void gen() {
    fac[0] = ivf[0] = 1;
    int M = (int)(1e5) + 1;
    for (int i = 1; i <= M; ++i) fac[i] = fac[i - 1] * i % mo;
    ivf[M] = pow_mod(fac[M], mo - 2, mo);
    for (int i = M - 1; i >= 1; --i) ivf[i] = ivf[i + 1] * (i + 1) % mo;
    for (int i = 0; i < M; ++i) T[0][i] = ivf[i + 1];
    inverse(T[0], B, T[1], M);
    for (int i = 0; i < M; ++i) B[i] = B[i] * fac[i] % mo;
    ++B[1];
}

int ai[25], bi[25];

void solve() {
    LL N = 1; int M;
    scanf("%d%d", &K, &M);
    for (int i = 1; i <= M; ++i) {
        scanf("%d%d", &ai[i], &bi[i]); N = N * pow_mod(ai[i], bi[i], mo) % mo;
    }
    memset(T, 0, sizeof(T));
    for (int i = 0; i <= K; ++i) T[0][i] = ivf[K - i] * B[K - i] % mo;
    for (int i = 0; i <= K + 1; ++i) T[1][i] = ivf[i + 1] * pow_mod(N, i + 1, mo) % mo;
    reverse(T[1], T[1] + K + 2);
    int len = 0;
    while ((1 << len) < ((K + 1) << 1)) ++len;
    ntt(T[0], 1 << len); ntt(T[1], 1 << len);
    for (int i = 0; i < (1 << len); ++i) T[0][i] = T[0][i] * T[1][i] % mo;
    ntt(T[0], 1 << len, -1);
    for (int i = K; i <= 2 * K + 1; ++i) {
        int dt = i - K; P[dt] = T[0][i] * fac[K] % mo * B[dt] % mo * ivf[dt] % mo;
    }
    for (int i = 0; i <= K + 1; ++i) Q[i] = 1;
    for (int i = 1; i <= M; ++i) {
        LL p = ai[i] % mo; LL now = pow_mod(p, mo - 2, mo);
        for (int j = 0; j <= K + 1; ++j) Q[j] = Q[j] * (1 + mo - now) % mo, now = now * p % mo;
    }
    LL ret = 0;
    for (int i = 0; i <= K + 1; ++i) (ret += P[i] * Q[i]) %= mo;
    printf("%lld\n", ret);
}

int main () {
    gen();
    int T;
    scanf("%d", &T);
    while (T--) solve();
    return 0;
}

---

J. Let Sudoku Rotate

搜索加可行性剪枝即可通过。由于数独限制较强，剪枝效果良好。

#include <bits/stdc++.h>
using namespace std;

int ord(char c) {
    if (isdigit(c)) return c - '0';
    return c - 'A' + 10;
}

char str(int c) {
    if (c < 10) return c + '0';
    return c + 'A' - 10;
}

int r[16][16], c[16][16];
int a[16][16];
int b[4][4];
char s[16];
int ret;

void add(int ip, int jp, int v) {
    for (int i = ip * 4; i < (ip + 1) * 4; ++i) {
        for (int j = jp * 4; j < (jp + 1) * 4; ++j) {
            r[i][a[i][j]] += v; c[j][a[i][j]] += v;
        }
    }
}

bool rot(int ip, int jp) {
    for (int i = ip * 4; i < (ip + 1) * 4; ++i) {
        for (int j = jp * 4; j < (jp + 1) * 4; ++j) {
            --r[i][a[i][j]]; --c[j][a[i][j]];
            b[j - jp * 4][(ip + 1) * 4 - i - 1] = a[i][j];
        }
    }
    bool succ = true;
    for (int i = ip * 4; i < (ip + 1) * 4; ++i) {
        for (int j = jp * 4; j < (jp + 1) * 4; ++j) {
            a[i][j] = b[i - ip * 4][j - jp * 4];
            if ((++r[i][a[i][j]] > 1) || (++c[j][a[i][j]] > 1)) succ = false;
        }
    }
    return succ;
}

void dfs(int ip, int jp, int now) {
	cout<<ip<<" "<<jp<<" "<<now<<" "<<ret<<endl; 
    if (ip == 4 && jp == 0) {
        ret = min(ret, now);
        return;
    }
    add(ip, jp, 1); if (now >= ret) return;
    for (int i = 1; i <= 4; ++i) {
        if (rot(ip, jp)) dfs(jp == 3 ? ip + 1 : ip, jp == 3 ? 0 : jp + 1, now + (i & 3));
    }
    add(ip, jp, -1);
}

void solve () {
    for (int i = 0; i < 16; ++i) {
        scanf("%s", s);
        for (int j = 0; j < 16; ++j) a[i][j] = ord(s[j]);
    }
    memset(r, 0, sizeof(r)); memset(c, 0, sizeof(c));
    ret = 16 * 4; dfs(0, 0, 0);
    printf("%d\n", ret);
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) solve();
    return 0;
}

---

K. Expression in Memories

注意在类似 +0? 的情况下，? 须被替换为 + 或 *，其余情况直接将 ? 替换为非零数字就好。替换完成后判断一下是否合法。

#include <bits/stdc++.h>
using namespace std;

int T; string res;
int main()
{
    ios :: sync_with_stdio(0);
    cin >> T;
    while (T --)
    {
        cin >> res;
        int flag = 1;
        for (int i = 1; i < res.size(); ++ i)
            if (res[i] == '?' && res[i - 1] == '0' && (i == 1 || res[i - 2] == '+' || res[i - 2] == '*'))
                res[i] = '+';
        for (int i = 0; i < res.size(); ++ i)
            if (res[i] == '?') res[i] = '1';
        if (res[0] == '+' || res[0] == '*') flag = 0;
        if (res[res.size() - 1] == '+' || res[res.size() - 1] == '*') flag = 0;
        for (int i = 0; i < res.size() - 1; ++ i)
            if ((res[i] == '+' || res[i] == '*') && (res[i + 1] == '+' || res[i + 1] == '*'))
                flag = 0;
        for (int i = 0; i < res.size() - 1; ++ i)
            if ((i == 0 || res[i - 1] == '+' || res[i - 1] == '*') && (res[i] == '0') && (res[i + 1] != '+' && res[i + 1] != '*'))
                flag = 0;
        if (flag) cout << res << endl;
        else cout << "IMPOSSIBLE" << endl;
    }
}

---

L. Graph Theory Homework

容易证明 $\lfloor \sqrt{a} \rfloor + \lfloor \sqrt{b} \rfloor \ge \lfloor \sqrt{a + b} \rfloor$⌊a​⌋+⌊b​⌋≥⌊a+b​⌋，进而可以证明边权满足三角不等式，故直接从 $1$1 走到 $n$n 就是最优的。

#include <bits/stdc++.h>
using namespace std;

void solve () {
    int n, a; cin >> n;
    for (int i = 1; i <= n; ++i) {
        int x; cin >> x;
        if (i == 1) a = x;
        if (i == n) cout << (int)sqrt(fabs(x - a) + 1e-3) << endl;
    }
}

int main () {
    ios::sync_with_stdio(false);
    int T; cin >> T;
    while (T--) solve();
    return 0;
}