也快退役了，早日飞升。
Codechef December Challenge 2020
-CALCULUS
题目描述：给定正整数 (n)，求
数据范围：(nle 10^6)。
solution
帕塞瓦尔定理给出了：
其中 (F_c(omega)=int_0^{+infty}f(x)sin(omega x) ext dx) 是 (f(x)) 的正弦傅里叶变换。
LCASQRT
题目描述：给定正整数 (n,p)，设 (mathbb A_p) 是所有元素 (<p) 且长度为 (n) 的自然数序列。给定 (n) 个点的有根树和序列 (cinmathbb A_p)，定义 LCA 卷积 (c=a imes b) 为
求使得 (ainmathbb A_p,c=a imes a) 的 (a) 数量(mod 998244353)，并给出一个满足要求的序列 (a)（若存在）。(T) 组数据。
数据范围：(Tle 10^5,sum nle 5 imes 10^5,3le ple 10^9+7,p) 是质数。
solution
设 (hat c) 是 (c) 的子树和，则 (hat c_u=hat a_u^2)，计算二次剩余即可。时间复杂度 (O(nlog p))。
DIVPERMS
题目描述：给定集合 (Ssubseteq[1,n]capN)，定义长为 (n) 的排列 (p) 的权值为 (sum_{i=2}^n[frac{p_i}{p_{i-1}}in S])。对所有 (kin[0,n)capN)，求长为 (n)，权值为 (k) 的排列数量(mod 998244353)。
数据范围：(nle 40)。
solution
发现贡献权值的 (p_{i-1}) 满足 (p_{i-1}lelfloorfrac n2 floor)。dp 考虑从小到大插入数，设 (f_{i,S}) 表示所有长为 (i) 的排列，且 (frac{p_i}{p_{i-1}}in S) 用到的 (p_{i-1}) 组成的集合为 (S)。时间复杂度 (O(n^22^{lfloorfrac n2 floor}))。
MODPARRS
题目描述：给定长为 (n) 的自然数序列 (A)，求满足以下条件的自然数序列 (X) 的数量(mod 998244353)：
- (forall i,X_i<239)
- (forall i e j,X_i e X_j)
- (239|sum_{i=1}^nA_iX_i)
数据范围：(nle 20)。
solution
若任意选择 (X_1,dots,X_{n-1})，则第三个条件唯一确定 (X_n)。设集合 (S={i|X_i e X_n})，则可以把 (S) 之外的元素求和并看成一个。
设 (dp_S) 表示 (S) 之外的数合并为一个，(S) 内部的数任意选择系数的方案数。设 (sum_S=sum_{i otin S}X_i)。
若 (sum_S e 0)，则方案数为总方案-有至少一个的系数与 (S) 之外的系数相同。此时不可能多于一个，则 (dp_S=frac{239!}{(239-|S|)!}-sum_{iin S}dp_{S-{i}})。
若 (sum_S=0)，则可以去掉任意一个元素并加进 (complement_US)，(S) 之外的系数可以任意选择，所以 (dp_S=(239-|S|)dp_{S-{i}})，其中 (iin S)。
答案即为 (dp_{2^{n-1}-1})。时间复杂度 (O(2^{n-1}))。
DGMATRIX
题目描述：给定 (n imes n) 的矩阵 (A)，求 ((n+1) imes (n+1)) 的矩阵 (B)，使得 (A_{i,j}=B_{i,j}+B_{i+1,j}+B_{i,j+1}+B_{i+1,j+1})。
数据范围：(nle 100)，保证有解。
solution
设第 (0) 行是 (x_0,x_1,dots,x_n)，第 (0) 列是 (y_0,y_1,dots,y_m)，枚举 (x_0=y_0)，则第 (i) 行第 (j) 列的数为 (?+(-1)^{i+j}((-1)^ix_i+(-1)^jy_j-x_0))，其中 (?) 可以通过递推计算。直接列不等式用 spfa 做差分约束即可，时间复杂度 (O(n^4))。
弦图 (2)
对于无向简单图 (G=(V,E))，定义团树 (T=(mathcal V,mathcal E)) 满足：
- (mathcal V) 是 (G) 中所有极大团构成的集合。
- 对于 (vin V)，包含点 (v) 的极大团在 (T) 中是连通子集。
定理：一个无向简单图是弦图当且仅当它存在团树。
构造 (Bernstein-Goodman 算法)：
- 找到弦图的所有极大团 (Q_1,Q_2,dots,Q_k)。
- 若两个极大团 (Q_i,Q_j) 有交，则连一条权值为 (|Q_icap Q_j|) 的边，这个图称为团图。
- 求团图的最大生成树。
时间复杂度 (O(k^2))。
*PALINDEQ
题目描述：给定正整数 (n) 和长为 (n) 的字符串 (S)。定义两个长度为 (n) 的字符串 (A,B)，定义 (A) 与 (B) 等价当且仅当 (forall 1le lle rle n,A[l:r])是回文串 (Leftrightarrow B[l:r])是回文串。求满足存在字符 (c) 和字符串 (X)，使得 (X) 与 (S) 等价，且 (forall pin P,X_p=c) 的非空集合 (Psubseteq[1,n]capN) 的数量(mod 998244353)。(T) 组数据。
数据范围：(Tle 1000,nle 2000,|Sigma|=26)。
solution
这题的条件跟校内 OJ 的某道题比较像...
对于这个条件，若 (S[l+1:r-1]) 是回文串而 (S[l:r]) 不是回文串，则 (X_l e X_r,X_{l+1}=X_{r-1},dots)。将要求相等的点合并，要求不相等的点连边，最终就是求一个类似独立集个数的东西。
这个图是弦图，证明如下：考虑所有的这些区间 ([l,r])，(l+1,r-1) 必定属于同一块，分三种情况：
- (S_l=S_{l+1})，则 (l,l+1) 属于同一块，连接两个点。
- (S_r=S_{r-1})，与 1. 同理。
- (S_l e S_{l+1},S_r e S_{r-1})，有三条边 ((l,r),(l,l+1),(r-1,r)) 形成三元环。
求出这个弦图并构造出团树。对团树做树形 dp，开一个虚点 (rt) 连向所有连通块中的任意一个团，并将 (rt) 作为根。设 (C_u) 表示团 (u) 的点集，(T_u) 表示团 (u) 的儿子，(g_u) 表示仅考虑 (u) 的子树，(u) 中不选点的方案数，(f_{u,x}) 表示仅考虑 (u) 的子树，(u) 中选 (x) 的方案数，(val_x) 表示 (2^{siz}-1)，其中 (siz) 是点 (x) 包含的字符串中位置个数（上面的合并）。
答案即为 (g_{rt})，时间复杂度 (O(n^2))。
Codechef November Challenge 2020
-CHEFSSM
题目描述：给定 (n) 个齿轮，第 (i) 个齿轮上有 (A_i+1) 个齿，每一步可以选择一个齿轮，将其顺时针或逆时针旋转一格，求最少步数的期望值(mod 998244353) 使得至少存在一个齿轮的某个位置是第 (0) 个或第 (A_i) 个齿。
数据范围：(nle 10^5)。
-PANIC
题目描述：给定 (k imes k) 的矩阵 (M)，求
其中 (F) 是斐波那契数。(T) 组数据。
数据范围：(sum kle 100,a,dle 10^9,nle 10^{1000})。
CF1464E No Game No Life
题目描述：给定 (n) 个自然数 (a_i)，初始自然数 (x=0)，做如下操作：生成 ([0,n]) 的随机正整数 (k)，若 (k=0) 则结束操作，否则将 (x:=xoplus a_k) 并重复操作。求最终 (x e 0) 的概率(mod 998244353)。
数据范围：(nle 10^5,a_i<512)。
solution
设 (c_i) 是 (a_i) 的桶，则所求即为
的第 (0) 项，此处乘法是异或卷积，(整数-序列)是对序列的 (0) 项做运算。使用 FWT 计算，由于 (sum c=n) 所以不会出现除以 (0) 的情况。时间复杂度 (O(n+Vlog V))。
#include<bits/stdc++.h>
#define PB emplace_back
using namespace std;
typedef long long LL;
const int N = 100003, M = 512, mod = 998244353;
template<typename T>
void read(T &x){
int ch = getchar(); x = 0;
for(;ch < '0' || ch > '9';ch = getchar());
for(;ch >= '0' && ch <= '9';ch = getchar()) x = x * 10 + ch - '0';
}
void qmo(int &x){x += x >> 31 & mod;}
void div2(int &x){if(x & 1) x += mod; x >>= 1;}
int n, m, sg[N], cnt[M], vis[M], inv[N<<1], ans; vector<int> E[N];
void init(int m){
inv[1] = 1;
for(int i = 2;i <= m;++ i) inv[i] = mod - (LL) mod / i * inv[mod % i] % mod;
}
void dfs(int x){ sg[x] = 0;
for(int v : E[x]) if(!~sg[v]) dfs(v);
for(int v : E[x]) vis[sg[v]] = x;
while(vis[sg[x]] == x) ++ sg[x];
}
int main(){
read(n); read(m); init(n<<1|1);
for(int i = 1, u, v;i <= m;++ i){
read(u); read(v); E[u].PB(v);
} memset(sg, -1, sizeof sg); cnt[0] = n+1;
for(int i = 1;i <= n;++ i){if(!~sg[i]) dfs(i); --cnt[sg[i]];}
for(int mid = 1;mid < M;mid <<= 1)
for(int i = 0;i < M;i += mid<<1)
for(int j = 0;j < mid;++ j){
int y = cnt[mid+i+j];
qmo(cnt[mid+i+j] = cnt[i+j] - y);
qmo(cnt[i+j] += y - mod);
}
for(int i = 0;i < M;++ i) qmo(ans += inv[cnt[i]] - mod);
for(int i = 0;i < 9;++ i) div2(ans); qmo(ans = 1 - ans);
printf("%d
", ans);
}
CF1464F My Beautiful Madness
题目描述：给定 (n) 个点的树，(m) 次操作，对于初始为空的路径多重集合 (P)，
- 给定 (u,v)，在 (P) 中加入一条路径 ((u,v))。
- 给定 (u,v)，在 (P) 中删除一条路径 ((u,v))。
- 给定 (d)，问是否存在点 (u)，使得 (u) 到 (P) 中的每一条路径的距离 (le d)。
数据范围：(n,mle 2 imes 10^5)。
solution
对于询问，发现这样的点 (u) 若存在，则一定可以是所有路径的 ( ext{lca}) 中最深的点的 (d) 级祖先。证明显然
然后就可以改为询问 (d,u)，判断是否 (u) 到所有路径的距离都 (le d)。
设 (u) 的 (d) 级祖先为 (v)，则所有路径一定要与 (v) 的子树有交。然后若路径不完全在 (v) 的子树内，则一定合法，否则只需判断 ( ext{lca}) 与 (u) 的距离是否 (le d)
那么现在的问题相当于：在点集 (S) 中加删点，求 (S) 的子树内点到 (x) 的距离最大值。这个可以用线段树维护区间直径的方法做，时间复杂度 (O((n+m)log n))。
-CF1458F Range Diameter Sum
题目描述：给定 (n) 个点的树，求所有编号区间的直径之和。
数据范围：(nle 10^5)。
*CF1458D Flip and Reverse
题目描述：给定长为 (n) 的 (01) 字符串 (S)，每次你可以选择一段 (01) 个数相同的子串，然后反转并翻转，求能得到的字典序最小的字符串。
数据范围：(sum nle 5cdot 10^5)。
神奇转化.jpg
solution
设 (0) 是 (-1)，(1) 是 (+1)，然后做前缀和 (s)，则 (s_{i-1}) 向 (s_i) 连边，操作即为将一个环的边反向。
然后发现操作前后的边集不变，同时原图任意一个环的两种顺序都可以操作到（证明略），于是直接求字典序最小的欧拉路径即可，直接贪心，时间复杂度 (O(n))。
*CF1446F Line Distance
题目描述：给定 (n) 个点 ((x_i,y_i))，求所有点对连成的直线到原点的距离的第 (k) 小值。
数据范围：(nle 10^5)。
神奇套路.pdf
solution
二分答案 (d)，问题就转化为有多少个直线与 (x^2+y^2=d^2) 有交。
结论：圆外两点连成的直线 (AB) 与圆 (C) 有交 (Leftrightarrow) (A,B) 到 (C) 的切点弦不严格相交。
然后直接扫描线+树状数组即可，时间复杂度 (O(nlog n))。
AGC014F Strange Sorting
题目描述：给定长度为 (n) 的排列，每次操作将前缀最大值按顺序丢到后面。求多少次操作后排列升序。
数据范围：(nle 2 imes 10^5)。
神奇结论.png
solution
从大到小考虑每个数 (i)，设当前已经加入 ((i,n]) 这些数，(q_i) 是 (i) 的位置（即逆排列），(f_i) 表示 ([i,n]) 排好序所需的操作次数，若 (f_i>0) 则 (g_i) 表示 (f_i-1) 次操作之后 ([i,n]) 中最前的数。定义前缀最大值的元素为 high，其他的为 low。
若 (f_{i+1}=0)，则若 (q_i>q_{i+1}) 则 (f_i=1,g_i=i+1)，否则 (f_i=0)。
若 (f_{i+1}>0)，则可以得到 (g_{i+1}>i+1)（因为若 (g_{i+1}=i+1) 则已排序或至少需两次操作），并且若 (f_{i+1}-1) 次操作后 (i) 在 (i+1) 之前，则 (f_i=f_{i+1},g_i=g_{i+1})，否则 (f_i=f_{i+1}+1,g_i=i+1)。
结论 1：在前 (f_{i+1}) 次操作中，若 (g_{i+1}) 不在第一个位置，则 (g_{i+1}) 是 low。
考虑反证法，若某一次操作中 (g_{i+1}) 不在第一个位置且是 high，设第一个数为 (y)，此次操作中是 (g_{i+1}) 之前的 high。以后的操作中 (y) 是 high (Rightarrow g_{i+1}) 是 high，即 (y) 始终在 (g_{i+1}) 之前，矛盾。Q.E.D.
结论 2：在前 (f_{i+1}) 次操作中，(g_{i+1},i,i+1) 的循环顺序不会变。
考虑分类讨论，对于 ([i,n]) 这些数组成的序列：
-
(i) 是第一个元素：
-
(i+1) 是第二个元素：(i,i+1) 是 high，(g_{i+1}) 是 low。
-
(g_{i+1}) 是第二个元素：(i,g_{i+1}) 是 high，(i+1) 是 low。
-
其他情况：(i) 是 high，(i+1,g_{i+1}) 是 low。
-
-
(i+1) 是第一个元素：(i+1) 是 high，(i,g_{i+1}) 是 low。
-
(g_{i+1}) 是第一个元素：(g_{i+1}) 是 high，(i,i+1) 是 low。
-
其他情况：都是 low。
这些情况都不会改变循环顺序，Q.E.D.
由此可得 (f_{i+1}-1) 次操作后 (i) 在 (i+1) 之前 (Leftrightarrow) 初始时循环顺序为 (g_{i+1},i,i+1)。
#include<bits/stdc++.h>
using namespace std;
const int N = 200003;
template<typename T>
void read(T &x){
int ch = getchar(); x = 0;
for(;ch < '0' || ch > '9';ch = getchar());
for(;ch >= '0' && ch <= '9';ch = getchar()) x = x * 10 + ch - '0';
}
int n, q[N], f[N], g[N];
int main(){
read(n);
for(int i = 1, x;i <= n;++ i){read(x); q[x] = i;}
for(int i = n-1;i;-- i)
if(f[i+1]){
if((q[g[i+1]] < q[i]) + (q[i] < q[i+1]) + (q[i+1] < q[g[i+1]]) == 2){
f[i] = f[i+1]; g[i] = g[i+1];
} else {
f[i] = f[i+1] + 1; g[i] = i+1;
}
} else if(q[i] > q[i+1]){
f[i] = 1; g[i] = i+1;
}
printf("%d
", f[1]);
}
AGC017F Zigzag
题目描述：求满足以下条件的 (m) 个长为 (n) 的 (01) 字符串 (X_i) 的个数(mod(10^9+7))。
- (k) 个限制 ((a,b,c))，表示 (X_{a,b}=c)。
- (forall iin[1,m),jin[1,n]left[sumlimits_{k=1}^jX_{i,k}lesumlimits_{k=1}^jX_{i+1,k} ight])。
数据范围：(n,mle 20, ext{TL}=4 ext s)。
被打傻了.nin
solution
考虑轮廓线 dp，从上一个字符串转移到下一个字符串时，(dp_{i,S}) 表示考虑到第 (i) 位，新串的前 (i) 位和后 (n-i) 位的限制组成 (S)，具体来说就是当旧串的该位为 (0) 且新串的该位为 (1) 时，把旧串"掰一下"：
此时旧串前 (i) 位的前缀和即为 (S) 前 (i) 位的前缀和，不需要多记一维来维护这个值了。
此时状态数为 (O(n2^n))，转移 (O(1))，总时间复杂度 (O(nm2^n))。
#include<bits/stdc++.h>
using namespace std;
const int N = 20, mod = 1000000007;
template<typename T>
void read(T &x){
int ch = getchar(); x = 0;
for(;ch < '0' || ch > '9';ch = getchar());
for(;ch >= '0' && ch <= '9';ch = getchar()) x = x * 10 + ch - '0';
}
int n, m, k, lim, o, ans, t[N][N], f[2][1<<N];
void qmo(int &x){x += x >> 31 & mod;}
int main(){
read(n); read(m); read(k); -- n; memset(t, -1, sizeof t);
while(k --){
int a, b, c;
read(a); read(b); read(c);
t[a-1][b-1] = c;
} f[0][0] = 1; lim = 1<<n;
for(int i = 0;i < m;++ i)
for(int j = 0;j < n;++ j){
o ^= 1; memset(f[o], 0, lim<<2);
for(int S = 0;S < lim;++ S) if(f[!o][S]){
int val = f[!o][S] - mod;
if(t[i][j] != 1 && !(S >> j & 1)) qmo(f[o][S] += val);
if(t[i][j])
if(S >> j & 1) qmo(f[o][S] += val);
else {
int T = S >> j; T &= T - 1;
qmo(f[o][(T+1 << j) | (S & (1<<j)-1)] += val);
}
}
}
for(int i = 0;i < lim;++ i) qmo(ans += f[o][i] - mod);
printf("%d
", ans);
}
-CF1446D2 Frequency Problem (Hard Version)
题目描述：给定长为 (n) 的正整数序列 (a)，求众数不唯一的子串长度的最大值。
数据范围：(a_ile nle 2cdot 10^5)。