A

考虑容斥。如果把每对不合法的相邻的 $a_u,a_{v}a\_u,a\_v$ 连起来的话，发现是若干个连通块。

那么设 $f(x,i)f(x,i)$ 表示 $xx$ 子树内，$xx$ 所在联通块 $b_{i}b\_i$ 最小值为 $ii$ 。（这样的话，这个连通块有 $ii$ 种取值可以连起来）。

转移考虑子树合并。

• 不把儿子 $yy$ 并上来，有 $f^{\mathrm{\prime }}(x,i)=f(x,i)\times \sum j\times f(y,j)f\text{'}(x,i)=f(x,i)\backslash times\; \backslash sum\; j\backslash times\; f(y,j)$
• 把儿子 $yy$ 并上来
  • 儿子 $yy$ 所在连通块最小值大于 $xx$ 所在连通块最小值 $f^{\mathrm{\prime }}(x,i)=f(x,i)\times (-{\sum }_{j\ge i}f(y,j))f\text{'}(x,i)=f(x,i)\backslash times(-\backslash sum\_\{j\backslash geq\; i\}\; f(y,j))$
  • 儿子 $yy$ 所在连通块最小值小于 $xx$ 所在连通块最小值 $f^{\mathrm{\prime }}(x,j)=f(y,j)\times (-{\sum }_{i\ge j}f(x,i))f\text{'}(x,j)=f(y,j)\backslash times(-\backslash sum\_\{i\backslash geq\; j\}\; f(x,i))$

用线段树合并在 $\mathcal{O}(n\log n)\backslash mathcal\; O(n\backslash log\; n)$ 的时间下实现。

#include <bits/stdc++.h>
#define int long long
using namespace std;
#define pi pair<int, int>
const int N = 500010, K = 60;
const int mod = 998244353;
int read() {
    int f = 0, x = 0;
    char ch = getchar();
    while (!isdigit(ch)) {
        f |= (ch == '-');
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return f ? -x : x;
}
int n, b[N];
vector<int> G[N];
int rt[N], lc[N * K], rc[N * K], tag[N * K], sf[N * K], sfi[N * K], idx;
void push_up(int x) {
    sf[x] = (sf[lc[x]] + sf[rc[x]]) % mod;
    sfi[x] = (sfi[lc[x]] + sfi[rc[x]]) % mod;
}
void Mul(int x, int v) {
    sf[x] = sf[x] * v % mod;
    sfi[x] = sfi[x] * v % mod;
    tag[x] = tag[x] * v % mod;
}
void push_down(int x) {
    if (tag[x] != 1) {
        if (lc[x])
            Mul(lc[x], tag[x]);
        if (rc[x])
            Mul(rc[x], tag[x]);
        tag[x] = 1;
    }
}
void insert(int& x, int l, int r, int p) {
    if (!x) {
        x = ++idx;
        tag[x] = 1;
    }
    if (l == r) {
        sf[x] = 1, sfi[x] = p;
        return;
    }
    int mid = l + r >> 1;
    push_down(x);
    if (p <= mid)
        insert(lc[x], l, mid, p);
    else
        insert(rc[x], mid + 1, r, p);
    push_up(x);
}
void merge(int& u1, int u2, int l, int r, int c1, int c2) {
    if (!u1 && !u2)
        return;
    if (!u2) {
        Mul(u1, c1);
        return;
    }
    if (!u1) {
        u1 = u2;
        Mul(u1, c2);
        return;
    }
    if (l == r) {
        int f1 = sf[u1], f2 = sf[u2];
        f1 = f1 * ((c1 - f2 + mod) % mod) % mod;
        f2 = f2 * c2 % mod;
        f1 = (f1 + f2) % mod;
        sf[u1] = f1, sfi[u1] = f1 * l % mod;
        return;
    }
    push_down(u1), push_down(u2);
    int mid = l + r >> 1;
    merge(lc[u1], lc[u2], l, mid, (c1 - sf[rc[u2]] + mod) % mod, (c2 - sf[rc[u1]] + mod) % mod);
    merge(rc[u1], rc[u2], mid + 1, r, c1, c2);
    push_up(u1);
}
void dfs(int x, int f) {
    insert(rt[x], 1, mod - 1, b[x]);
    for (int y : G[x]) {
        if (y == f)
            continue;
        dfs(y, x);
        merge(rt[x], rt[y], 1, mod - 1, sfi[rt[y]], 0);
    }
}
signed main() {
    n = read();
    for (int i = 1; i <= n; i++) b[i] = read();
    for (int i = 1; i < n; i++) {
        int x = read(), y = read();
        G[x].emplace_back(y);
        G[y].emplace_back(x);
    }
    dfs(1, 0);
    printf("%lld\n", sfi[rt[1]]);
    return 0;
}

B

最大值最小，考虑二分答案。

把坐标 $(x,y)(x,y)$ 转化为 $(x+y,x-y)(x+y,x-y)$ 将曼哈顿距离转为切比雪夫距离。

问题变成每种颜色矩形面积并的交是否非空。

每种颜色个数不超过 $2020$ 个，所以暴力离散化，填色，然后在原矩形内打差分标记，二位前缀和看是否有一个格子被覆盖了 $mm$ 次。

#include <bits/stdc++.h>
#define pi pair<int, int>
#define y1 qweqwe
using namespace std;
const int N = 2e3 + 9;
int n, m, a[N][N];
vector<pi> p[N * N];
int s[N][N], v[N][N];
int X[N * N], Y[N * N], x, y;
int ok[N][N];
int check(int d) {
    memset(v, 0, sizeof v);
    for (int c = 1; c <= m; c++) {
        x = 0, y = 0;
        X[x++] = 0;
        Y[y++] = 0;
        for (pi I : p[c]) {
            int i = I.first, j = I.second;
            int x1 = max(1, i - d);
            X[x++] = x1;
            int y1 = max(1, j - d);
            Y[y++] = y1;
            int x2 = min(2 * n + 1, i + d + 1);
            X[x++] = x2;
            int y2 = min(2 * n + 1, j + d + 1);
            Y[y++] = y2;
        }
        sort(X, X + x), sort(Y, Y + y);
        x = unique(X, X + x) - X, y = unique(Y, Y + y) - Y;
        for (int i = 0; i < x; i++)
            for (int j = 0; j < y; j++) s[i][j] = 0;
        for (pi I : p[c]) {
            int i = I.first, j = I.second;
            int x1 = lower_bound(X, X + x, max(1, i - d)) - X;
            int y1 = lower_bound(Y, Y + y, max(1, j - d)) - Y;
            int x2 = lower_bound(X, X + x, min(2 * n + 1, i + d + 1)) - X;
            int y2 = lower_bound(Y, Y + y, min(2 * n + 1, j + d + 1)) - Y;
            s[x1][y1]++;
            s[x1][y2]--;
            s[x2][y1]--;
            s[x2][y2]++;
        }
        for (int i = 1; i < x; i++) {
            for (int j = 1; j < y; j++) {
                s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
            }
        }
        for (int i = 1; i < x; i++) {
            for (int j = 1; j < y; j++) s[i][j] = s[i][j] > 0;
        }
        for (int i = 1; i < x; i++) {
            for (int j = 1; j < y; j++) {
                v[X[i]][Y[j]] += s[i][j] - s[i - 1][j] - s[i][j - 1] + s[i - 1][j - 1];
            }
        }
    }

    for (int i = 1; i <= 2 * n; i++) {
        for (int j = 1; j <= 2 * n; j++) {
            v[i][j] += v[i - 1][j] + v[i][j - 1] - v[i - 1][j - 1];
            if (ok[i][j] && v[i][j] == m)
                return 1;
        }
    }
    return 0;
}
signed main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            scanf("%d", &a[i][j]);
            ok[i + j][i - j + n] = 1;
            p[a[i][j]].push_back({ i + j, i - j + n });
        }
    int l = 0, r = n;
    while (l < r) {
        int mid = l + r >> 1;
        if (check(mid))
            r = mid;
        else
            l = mid + 1;
    }
    cout << r << endl;
    return 0;
}

C

令 $f(x,V)f(x,V)$ 表示前 $xx$ 轮选择后当前连通块为 $VV$ 。

当 $\mathrm{\mid }V\mathrm{\mid }=1|V|=1$ 的时候，可以不用继续搜索。否则，枚举这一层保留哪些边转移到下一层。

而对于一个 $xx$ 所有的合法 $VV$ 大小总和不超过 $2n2n$ 。因为一个连通块的集合可以等价于一个边集。每一层的边集不交，所以经过一轮选择后的边集也不会相交。

只需要 dfs 暴力做即可，用 map 或者桶存储每个点属于哪个连通块。时间复杂度 $\mathcal{O}(nm)\backslash mathcal\; O(nm)$。

#include <bits/stdc++.h>
#define vi vector<int>
#define vii vector<vi>
using namespace std;
const int N = 1e6 + 9;
vii a[2][N];
vi pos[2][N];
int n, m, ans[N], j[N];
void dfs(int d, vector<int>& A) {
    if (A.size() == 1)
        return;
    if (d == m + 1) {
        int len = A.size();
        for (int y : A) ans[y] = max(ans[y], len);
        return;
    }
    for (int o = 0; o < 2; o++) {
        int cnt = 0;
        vii res(0);
        for (int x : A) {
            int t = pos[o][d][x];
            if (j[t] == -1) {
                j[t] = cnt++;
                vi ret(0);
                ret.push_back(x);
                res.push_back(ret);
            } else
                res[j[t]].push_back(x);
        }
        for (int x : A) j[pos[o][d][x]] = -1;
        for (auto re : res) dfs(d + 1, re);
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        for (int k = 0; k <= 1; k++) {
            int cntpart;
            cin >> cntpart;
            a[k][i] = vii(cntpart);
            pos[k][i] = vi(n + 1);
            for (int j = 0; j < cntpart; j++) {
                int cntnode;
                cin >> cntnode;
                a[k][i][j] = vi(cntnode);
                for (int s = 0; s < cntnode; s++) {
                    int node;
                    cin >> node;
                    a[k][i][j][s] = node;
                    pos[k][i][node] = j;
                }
            }
        }
    }
    vector<int> A(n);
    for (int i = 0; i < n; i++) j[i] = -1, A[i] = i + 1;
    for (int i = 1; i <= n; i++) ans[i] = 1;
    dfs(1, A);
    for (int i = 1; i <= n; i++) cout << ans[i] << " ";
}

D

首先把只循环一次的贡献提前计算

枚举周期含有 $kk$ 的子串有多少个。

每 $kk$ 个点设立一个关键点，由于循环一次的贡献已经被计算，那么串长至少为 $2k2k$ ，所以每个符合条件的子串至少包含两个关键点。

假设某一个串 $TT$ 的周期含有 $kk$ ，第一次遇到的关键点为 $ii$ 。由于 $TT$ 肯定会包含 $[i,i+k][i,i+k]$ ，不妨贪心把左端点 $ll$ 从 $ii$ 往前扩展，直到 $S[l-1]≠S[l+k-1]\text{or}l=i-k+1S[l-1]\backslash not=S[l+k-1]\backslash or\; l=i-k+1$，把右端点 $rr$ 从 $i+ki+k$ 扩展，直到 $S[r+1]≠S[r+1-k]\text{or}r=\mathrm{\mid }S\mathrm{\mid }S[r+1]\backslash not=S[r+1-k]\backslash or\; r=|S|$ 。那么左端点在 $ll$ 的时候，右端点有 $\max \{r,l+2k-1\}-(l+2k-1)\backslash max\backslash \{r,l+2k-1\backslash \}-(l+2k-1)$ 种取值。所以可以快速计算第一次遇到的关键点为 $ii$ 的子串方案数。

而贪心扩展的部分，可以使用后缀数组快速求出。

而枚举周期为 $kk$ ，只有 $\frac{\mathrm{\mid }S\mathrm{\mid }}{k}\backslash frac\{|S|\}\{k\}$ 个关键点，总时间复杂度就是 $\mathcal{O}(\mathrm{\mid }S\mathrm{\mid }\log \mathrm{\mid }S\mathrm{\mid })\backslash mathcal\; O(|S|\backslash log\; |S|)$。

#include <bits/stdc++.h>
#define int long long
const int N=1e6+9;
using namespace std;
int lo[N];
int n;
char s[N];
struct suf{
	int m;
	int tong[N],rnk[N],sa[N],y[N],h[N];
	signed p[N][22];
	void qsort(){
		for(int i=0;i<=m;++i)tong[i]=0;
		for(int i=1;i<=n;++i)tong[rnk[i]]++;
		for(int i=1;i<=m;++i)tong[i]+=tong[i-1];
		for(int i=n;i>=1;--i)sa[tong[rnk[y[i]]]--]=y[i];
	}
	inline int lcp(int x,int y){
		x=rnk[x];y=rnk[y];
		if(x>y)swap(x,y);
		x++;
		int o=lo[y-x+1];	
		return min(p[x][o],p[y-(1<<o)+1][o]);
	}
	void SA(){
		m=30;
		for(int i=1;i<=n;++i){rnk[i]=s[i]-'a'+1;y[i]=i;}
	    qsort();
	    for(int w=1,p=0;p<n;w<<=1,m=p){
	    //	cout<<1;
	    	p=0;
	    	for(int i=n-w+1;i<=n;++i)y[++p]=i;
	    	for(int i=1;i<=n;++i)if(sa[i]>w)y[++p]=sa[i]-w;
	        qsort();
	        for(int i=1;i<=n;++i){
	        	swap(rnk[i],y[i]);
			}
		//	swap(rnk,y);
			rnk[sa[1]]=p=1;
	        for(int i=2;i<=n;++i)rnk[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+w]==y[sa[i-1]+w])?p:++p;
	    }
	    for(int i=1,j;i<=n;++i){
	    	if(rnk[i]==1)continue;
	    	j=max(0ll,h[rnk[i-1]]-1);
	    	while(s[i+j]==s[sa[rnk[i]-1]+j])++j;
	    	h[rnk[i]]=j;
	    	p[rnk[i]][0]=j;
	    }
	    for(int i=1;(1<<i)<=n;++i){
	    	for(int j=1;j+(1<<i)-1<=n;++j){
	    		p[j][i]=min(p[j][i-1],p[j+(1<<(i-1))][i-1]);
			}
		}
	}
	void clear(){
		for(int i=0;i<=n;++i){
			tong[i]=rnk[i]=sa[i]=y[i]=h[i]=0;
		}
	}
}sa1,sa2;
signed main(){  
	int T;cin>>T;
	for(int i=2;i<=N-1;++i)lo[i]=lo[i>>1]+1;
	while(T--){
	 	scanf("%s",s+1);
	 	n=strlen(s+1);
	 	sa1.SA();
	 	reverse(s+1,s+n+1);
	 	sa2.SA();
	 	int ans=0;
	 	for(int d=1;d<=n;++d){
	 		for(int i=1;i<=n;i+=d){
	 			int j=i+d,k=j+d-1;
	 			if(k>n)continue;
	 			int num1=min(d,sa2.lcp(n-(j-1)+1,n-k+1));
	 			int q1=i+(d-num1);
	 			int q2=j+(d-num1);
	 			int num=sa1.lcp(q1,q2);
	 			int nn=min(num1,num-(num/d*d)+1);
	 			num=num/d*d;
	 			if(!num)continue;
	 			ans+=num*nn+(num-d)*(num1-nn);
			}
		 }
		for(int i=1;i<=n;++i)
			ans+=i*(n-i+1);
		printf("%lld\n",ans);
		sa1.clear();sa2.clear();
   }
   return 0;
}

E

考虑费用流，源点和每个人，每个人和能审的论文之间连接流量为 $11$ ，费用为 $00$ 的边。每个论文和汇点连 $nn$ 条边，流量都是 $11$ ,权值分别为 $(1,2,\mathrm{3...}n)(1,2,3...n)$ 。那么花费是递增的凸函数，最后的解满足条件。

#include <bits/stdc++.h>
using namespace std;
const int N = 409;
const int M = N << 2;
const int inf = 1 << 30;
struct Edge {
    int nxt, to, c;
} e[M * M];
int head[M << 2], tot = 1;
queue<int> q;
int n, m, S, T;
int d[M << 2], now[M << 2], ans[N << 3];
void add(int from, int to, int c) {
    e[++tot].to = to;
    e[tot].c = c;
    e[tot].nxt = head[from];
    head[from] = tot;
    e[++tot].to = from;
    e[tot].c = 0;
    e[tot].nxt = head[to];
    head[to] = tot;
}
bool bfs() {
    memset(d, 0, sizeof(d));
    while (!q.empty()) q.pop();
    q.push(S);
    d[S] = 1;
    now[S] = head[S];
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int i = head[x]; i; i = e[i].nxt) {
            int y = e[i].to;
            if (e[i].c && !d[y]) {
                q.push(y);
                now[y] = head[y];
                d[y] = d[x] + 1;
                if (y == T)
                    return 1;
            }
        }
    }
    return 0;
}
int dinic(int x, int flow) {
    if (x == T)
        return flow;
    int rest = flow, k;
    for (int i = now[x]; i && rest; i = e[i].nxt) {
        int y = e[i].to;
        now[x] = i;
        if (e[i].c && d[y] == d[x] + 1) {
            k = dinic(y, min(e[i].c, rest));
            if (!k)
                d[y] = 0;
            e[i].c -= k;
            e[i ^ 1].c += k;
            rest -= k;
        }
    }
    return flow - rest;
}
int main() {
    scanf("%d%d", &n, &m);
    char s[M << 2];
    S = n + m + 1, T = n + m + 2;
    for (int i = 1; i <= n; ++i) {
        scanf("%s", s + 1);
        for (int j = 1; j <= m; j++)
            if (s[j] == '1')
                add(i, j + n, 1);
    }
    for (int i = 1; i <= n; ++i) add(S, i, 1);
    int flow, maxflow = 0;
    for (int t = 1; t <= n; ++t) {
        for (int j = 1; j <= m; j++) add(j + n, T, 1);
        while (bfs())
            while (flow = dinic(S, inf)) maxflow += flow;
        if (maxflow == n) {
            for (int i = 1; i <= n; ++i)
                for (int j = head[i]; j; j = e[j].nxt)
                    if (e[j].c == 0) {
                        ans[i] = e[j].to - n;
                        break;
                    }
            for (int i = 1; i <= n; ++i) printf("%d%c", ans[i], (i == n) ? '\n' : ' ');
            return 0;
        }
    }
    puts("-1");
    return 0;
}

F

考虑求出一个集合 $AA$ 满足 $S\in AS\backslash in\; A$ 都是先手必胜的起点。那么 $tt$ 必定在这个集合中。

若 $x\in Ax\backslash in\; A$ ，那么 $xx$ 的所有出边一定能达到至少两个 $AA$ 中的点。否则先手会把唯一那条边ban掉，从而导致后手输掉。

那么建反图，从 $tt$ 开始用队列更新出所有在 $AA$ 的点。时间复杂度 $\mathcal{O}(n+m)\backslash mathcal\; O(n+m)$ 。

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int n, m, s, t, w[N];
vector<int> g[N];

void dfs(int u) {
    w[u]++;
    if (w[u] != 2)
        return;
    for (auto v : g[u]) {
        dfs(v);
    }
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d%d%d", &n, &m, &s, &t);
        for (int i = 0; i <= n; i++) g[i].clear();
        memset(w, 0, sizeof(w));
        for (int i = 1; i <= m; i++) {
            int u, v;
            scanf("%d%d", &u, &v);
            g[u].push_back(v);
            g[v].push_back(u);
        }
        w[t] = 1;
        dfs(t);
        if (w[s] >= 2)
            puts("Join Player");
        else
            puts("Cut Player");
    }
    return 0;
}

G

发现和 staircase nim 类似，于是直接写出有解条件。

当 $nn$ 为奇数时，先手必败当且仅当 $(A_n-A_{n-1})\oplus (A_{n-2}-A_{n-3})\oplus \mathrm{.}\mathrm{.}\mathrm{.}\oplus (A_1-A_0)=0(A\_n-A\_\{n-1\})\backslash oplus(A\_\{n-2\}-A\_\{n-3\})\backslash oplus...\backslash oplus(A\_1-A\_0)=0$

当 $nn$ 为偶数时，先手必败当且仅当 $(A_n-A_{n-1})\oplus (A_{n-2}-A_{n-3})\oplus \mathrm{.}\mathrm{.}\mathrm{.}\oplus (A_2-A_1)=0(A\_n-A\_\{n-1\})\backslash oplus(A\_\{n-2\}-A\_\{n-3\})\backslash oplus...\backslash oplus(A\_2-A\_1)=0$

我们假设 $nn$ 是偶数（否则可以补一个 $00$ ）。并且令 $A_{n+1}=mA\_\{n+1\}=m$ 。

将 $AA$ 差分得到数组 $B_i=A_i-A_{i-1}B\_i=A\_i-A\_\{i-1\}$ ，序列需要满足

• ${\sum }_{i=1}^{n+1}{B}_i=m\backslash sum\; \_\{i=1\}^\{n+1\}B\_i=m$
• $B_i\ge 0B\_i\backslash geq\; 0$
• ${⨁}_{i=1}^{n\mathrm{/}2}{B}_{2i}=0\backslash bigoplus\_\{i=1\}^\{n/2\}B\_\{2i\}=0$

二进制问题，考虑数位dp。设 $f(i,S)f(i,S)$ 表示选定 $BB$ 序列的前 $ii$ 位，并且满足异或和为 $00$ 的条件下，${\sum }_{i=1}^{n+1}{B}_i=m_i-S\backslash sum\; \_\{i=1\}^\{n+1\}B\_i=m\_i-S$ 的方案数。其中 $m_{i}m\_i$ 表示保留 $mm$ 二进制下前 $ii$ 位的值。

其中 $g(j)g(j)$ 表示，给 $n+1n+1$ 个数这一位选取 $0\mathrm{/}10/1$ ，和为 $jj$ ，其中下标为偶数的位置异或和是 $00$ 的方案数。

可以把下标为偶数的全部移到前面来，所以等价于 $n+1n+1$ 个 $0\mathrm{/}10/1$ ，和为 $jj$ ，前 $\frac{n}{2}\backslash frac\{n\}\{2\}$ 个数异或和为 $00$ 的方案数。

设多项式 $A_i=[i\mathrm{\%}2=0]\left(\genfrac{}{}{0px}{}{n\mathrm{/}2}{i}\right)A\_i=[i\backslash \%2=0]\backslash binom\{n/2\}\{i\}$

那么 $g=A\times (1+x{)}^{n\mathrm{/}2+1}g=A\backslash times(1+x)^\{n/2+1\}$ ，因为最后 $n\mathrm{/}2+1n/2+1$ 个数可以任选。

这个和转移都用多项式来转移，时间复杂度 $\mathcal{O}(n\log n\log m)\backslash mathcal\; O(n\backslash log\; n\backslash log\; m)$。

#include <bits/stdc++.h>
#define int long long
#define PII pair<int, int>
#define x first
#define y second
using namespace std;
const int N = 8e5 + 9;
const int mod = 998244353;
const int G = 3;
const int Gi = 332748118;
int n, k, T;
int m;
int limit = 1, L, r[N];
int a[N], b[N];
int jie[N], rjie[N];
int g[N], temp[N], dp[N];

int inv(int a, int k, int p) {
    int res = 1;
    while (k) {
        if (k & 1)
            res = res * a % p;
        a = a * a % p;
        k >>= 1;
    }
    return res;
}
int re(int x) { return inv(x, mod - 2, mod); }
void NTT(int *A, int op) {
    for (int i = 0; i < limit; i++)
        if (i < r[i])
            swap(A[i], A[r[i]]);
    for (int mid = 1; mid < limit; mid <<= 1) {
        int Wn = inv(op == 1 ? G : Gi, (mod - 1) / (mid << 1), mod);
        for (int j = 0; j < limit; j += (mid << 1)) {
            int w = 1;
            for (int k = 0; k < mid; k++, w = (w * Wn) % mod) {
                int x = A[j + k], y = w * A[j + k + mid] % mod;
                A[j + k] = (x + y) % mod, A[j + k + mid] = (x - y + mod) % mod;
            }
        }
    }
}
signed main() {
    scanf("%lld%lld", &n, &m);
    jie[0] = rjie[0] = 1;
    for (int i = 1; i <= n; i++) jie[i] = jie[i - 1] * i % mod, rjie[i] = re(jie[i]);
    for (int i = 0; i <= (n + 1) / 4; i++)
        a[i << 1] = jie[(n + 1) / 2] * rjie[2 * i] % mod * rjie[(n + 1) / 2 - 2 * i] % mod;
    for (int i = 0; i <= n / 2; i++) b[i] = jie[n / 2] * rjie[i] % mod * rjie[n / 2 - i] % mod;

    int ma = 2 * n;
    while (limit <= ma) limit <<= 1, L++;
    for (int i = 0; i < limit; i++) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (L - 1));
    NTT(a, 1);
    NTT(b, 1);
    for (int i = 0; i < limit; i++) a[i] = (a[i] * b[i]) % mod;
    NTT(a, -1);
    int rll = re(limit);
    for (int i = 0; i <= n; i++) g[i] = a[i] * rll % mod;
    dp[0] = 1;
    limit = 1, L = 0;
    while (limit <= 3 * n) limit <<= 1, L++;
    for (int i = 0; i < limit; i++) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (L - 1));
    int rl = re(limit);
    NTT(g, 1);
    for (int i = 40; i >= 0; i--) {
        int d = m >> i & 1;
        for (int j = 0; j < limit; j++) temp[j] = 0;
        for (int j = 0; j <= 2 * n; j++) (temp[min(2 * n, 2 * j + d)] += dp[j]) %= mod;

        reverse(temp, temp + 2 * n + 1);
        NTT(temp, 1);
        for (int i = 0; i < limit; i++) temp[i] = (temp[i] * g[i]) % mod;
        NTT(temp, -1);
        for (int i = 0; i <= 2 * n; i++) temp[i] = temp[i] * rl % mod;
        reverse(temp, temp + 2 * n + 1);
        for (int i = 0; i <= 2 * n; i++) dp[i] = temp[i];
    }
    int res = 0;
    for (int i = 0; i <= 2 * n; i++) res = (res + dp[i]) % mod;
    printf("%lld", res);
}

H

无论还剩几个随从，随机到 $AA$ 和 $BB$ 的概率都是相等的，于是可以不考虑随从。

令 $a=\lceil \frac{A}{10}\rceil ,b=\lceil \frac{B}{10}\rceil a=\backslash lceil\backslash frac\{A\}\{10\}\backslash rceil,b=\backslash lceil\backslash frac\{B\}\{10\}\backslash rceil$ 。

上述式子表示在第 $i+bi+b$ 轮结束，其中“我”损失血量只能在前 $i+b-1i+b-1$ 轮，而每一轮的概率为 $\frac{1}{2}\backslash frac\{1\}\{2\}$。

#include <bits/stdc++.h>
using namespace std;
const int P = 998244353;
const int N = 1e6 + 9;

int A, B;
long long inv[N], cur, ans;

int main() {
    scanf("%d", &A);
    for (int i = 0; i < 8; ++i) scanf("%d", &B);
    A = (A - 1) / 10 + 1;
    B = (B - 1) / 10 + 1;
    inv[1] = 1;
    for (int i = 2; i <= 1000000; ++i) inv[i] = (P - P / i) * inv[P % i] % P;
    cur = 1;
    for (int i = 1; i <= B; ++i) cur = cur * inv[2] % P;
    ans = cur;
    for (int i = B + 1; i < A + B; ++i) {
        cur = cur * (i - 1) % P * inv[i - B] % P * inv[2] % P;
        ans = (ans + cur) % P;
    }
    printf("%lld\n", ans);
    return 0;
}

I

等价于 $a_i+b_l=a_j+b_{k}a\_i+b\_l=a\_j+b\_k$ 。因为 $a_i,b_j\in [10^7]a\_i,b\_j\backslash in[10^7]$ ，所以 $\max \{a_i+b_l\}\le 2\times 10^7\backslash max\backslash \{a\_i+b\_l\backslash \}\backslash leq\; 2\backslash times\; 10^7$ 。首先特殊处理有重复元素的情况，剩下的根据鸽巢原理，保留 $\{b\}\backslash \{b\backslash \}$ 的前 $\lceil \frac{2\times 10^7}{n}\rceil \backslash lceil\backslash frac\{2\backslash times\; 10^7\}\{n\}\backslash rceil$ 即可保证一定有至少两对和相等且下标不同。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e7 + 9;
const int M = 1e6 + 9;
int i, j, k, l, n, m, a[M], b[M], A, B, p1, p2, p3, p4, e[M], f[M];
int ais[N], bis[N];
int p[2 * N][2];
int main() {
    cin >> n >> m;
    for (i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (i = 1; i <= m; i++) scanf("%d", &b[i]);
    for (i = 1; i <= n; i++) {
        if (ais[a[i]]) {
            p2 = ais[a[i]], p1 = i;
        } else
            ais[a[i]] = i, e[++k] = i;
    }
    for (i = 1; i <= m; i++) {
        if (bis[b[i]]) {
            p4 = bis[b[i]], p3 = i;
        } else
            bis[b[i]] = i, f[++l] = i;
    }
    if (p1 && p3) {
        cout << p1 << ' ' << p2 << ' ' << p3 << ' ' << p4 << '\n';
        return 0;
    }
    for (i = 1; i <= k; i++) {
        for (j = 1; j <= l; j++) {
            int x = a[e[i]] + b[f[j]];
            if (p[x][0]) {
                cout << e[p[x][0]] << ' ' << e[i] << ' ' << f[p[x][1]] << ' ' << f[j];
                return 0;
            } else
                p[x][0] = i, p[x][1] = j;
            ;
        }
    }
    cout << -1;
    return 0;
}

J

首先考虑排列的情况，并离散化使得 $A_i=iA\_i=i$ 。由于交换一次会使得逆序对奇偶性变化，所以直接判掉 $\left(\genfrac{}{}{0px}{}{n}{2}\right)\backslash binom\{n\}\{2\}$ 和 $BB$ 逆序对奇偶性不同的情况。

然后进行归纳构造

• 当存在 $A_u≠B_{u}A\_u\backslash not\; =B\_u$ 时，找到 $A_v=B_{u}A\_v=B\_u$ ，依次操作 $(u,i)(i≠u,v)(u,i)(i\backslash not\; =u,v)$，最后操作 $(u,v)(u,v)$ 。操作后 $A_u=B_{u}A\_u=B\_u$，并把问题变成 $n-1n-1$ 的子问题。
• $\mathrm{\forall }i,A_i=B_i\backslash forall\; i,A\_i=B\_i$ ，根据有解必有 $n\mathrm{\%}4=1,0n\backslash \%4=1,0$ 。那么假设 $n\ge 4n\backslash geq\; 4$ ， 依次进行 $(1,5),(1,6)\mathrm{.}\mathrm{.}(1,n),(1,2),(2,n),(2,n-1)\mathrm{.}\mathrm{.}\mathrm{.}(2,5)(1,5),(1,6)..(1,n),(1,2),(2,n),(2,n-1)...(2,5)$ ，此时交换了 $11$ 和 $22$ 。再对 $3,43,4$ 也进行上述操作，使得 $3,43,4$ 的值也交换了。最后执行 $(1,4),(2,3),(1,3),(2,4)(1,4),(2,3),(1,3),(2,4)$ 让四个元素归位，并删除了这四个点所有相邻的边，变成 $n-4n-4$ 的子问题。

而对于不是排列的情况，交换两个相等的元素，使得序列不变但是逆序对奇偶性变化从而一定有解。

#include <bits/stdc++.h>
using namespace std;
const int N = 2e2 + 9;
int T, n, a[N], b[N], aa[N], bb[N], ok, v[N], c[N], cnt, p, x[N], t, q;
void opt(int x, int y) {
    if (x < y)
        printf("%d %d\n", x, y);
    else
        printf("%d %d\n", y, x);
    swap(c[x], c[y]);
}
void solve(int t) {
    if (t < 4)
        return;
    t -= 4;
    for (int i = 1; i <= t; i++) opt(x[i], x[t + 1]);
    for (int i = t + 1; i; i--) opt(x[i], x[t + 2]);
    for (int i = 1; i <= t; i++) opt(x[i], x[t + 3]);
    for (int i = t + 3; i; i--)
        if (i != t + 2 && i != t + 1)
            opt(x[i], x[t + 4]);
    opt(x[t + 1], x[t + 3]);
    opt(x[t + 2], x[t + 4]);
    opt(x[t + 1], x[t + 4]);
    opt(x[t + 2], x[t + 3]);
    solve(t);
}

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
        for (int i = 1; i <= n; i++) scanf("%d", &b[i]);
        for (int i = 1; i <= n; i++) v[i] = c[i] = 0;
        ok = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++)
                if (!v[j] && a[i] == b[j]) {
                    v[j] = 1;
                    c[i] = j;
                    break;
                }
            if (!c[i]) {
                printf("NO\n");
                ok = 0;
                break;
            }
        }
        if (!ok)
            continue;
        cnt = 0;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j < i; j++)
                if (c[j] > c[i])
                    cnt++;
        if ((cnt + n * (n - 1) / 2) % 2 != 0) {
            ok = 0;
            for (int i = 1; i <= n; i++)
                for (int j = 1; j < i; j++)
                    if (ok == 0 && b[c[i]] == b[c[j]]) {
                        ok = 1;
                        swap(c[i], c[j]);
                    }
            if (!ok) {
                printf("NO\n");
                continue;
            }
        }
        printf("YES\n");
        for (int i = 1; i <= n; i++) v[i] = 0;
        for (int i = 1; i <= n; i++) {
            p = 0;
            for (int j = 1; j <= n; j++)
                if (c[j] != j)
                    p = j;
            if (p == 0) {
                t = 0;
                for (int j = 1; j <= n; j++)
                    if (!v[j])
                        x[++t] = j;
                solve(t);
                break;
            } else {
                for (int j = 1; j <= n; j++)
                    if (c[j] == p)
                        q = j;
                v[p] = 1;
                for (int j = 1; j <= n; j++)
                    if (!v[j] && j != q)
                        opt(j, p);
                opt(q, p);
            }
        }
    }
    return 0;
}

K

当点权范围只有 $[1,k][1,k]$ 的时候，可以状压 $f(x,S)f(x,S)$ 表示以 $xx$ 为根的子树，选了的颜色集合为 $SS$ 的最大权值。时间复杂度 $\mathcal{O}(n\times 3^k)\backslash mathcal\; O(n\backslash times\; 3^k)$。

那么给每一种原本的权值随机一个新的权值 $[1,k][1,k]$ 。随机后得到的一组合法解，在随机前也一定是合法解。设最优答案的 $kk$ 个颜色随机后仍然互不相同，概率为 $\frac{k!}{k^k}\backslash frac\{k!\}\{k^k\}$ 。$k=5k=5$ 时为 $0.03840.0384$ 。多随机几次即可。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e3 + 9;
int f[N][(1 << 5) + 10];
struct node {
    int v, w;
};
vector<node> g[N];
int pos[N], a[N];
int res, n, k;
;
void dfs(int u, int fa) {
    f[u][0] = 0;
    f[u][1 << (pos[a[u]])] = 0;
    for (auto X : g[u]) {
        int v = X.v, w = X.w;
        if (v == fa) {
            continue;
        }
        dfs(v, u);
        for (int i = (1 << k) - 1; i >= 1; i--) {
            for (int j = i; j; j = (j - 1) & i) {
                f[u][i] = max(f[u][i], f[u][i - j] + f[v][j] + w);
                if (i - j) {
                    res = max(res, f[u][i - j] + f[v][j] + w);
                }
            }
        }
    }
}
signed main() {
    scanf("%lld%lld", &n, &k);
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    for (int i = 1, u, v, w; i < n; i++) {
        scanf("%lld%lld%lld", &u, &v, &w);
        g[u].push_back({ v, w });
        g[v].push_back({ u, w });
    }
    int t = 200;
    while (t--) {
        memset(f, -0x3f, sizeof(f));
        for (int i = 1; i <= n; i++) pos[i] = rand() % k;
        dfs(1, 0);
    }
    printf("%lld\n", res);
    return 0;
}