就要WC了，然而我还是一堆简单题不会做。人弱就要多刷题，于是就刷了一些我觉得很难的题。
如果大家发现有什么问题欢迎提出。
目录
- 1、Codeforces 717A
- 2、TCO2014 Round 3B Div1 1000
- 3、Codeforces 722E
- 4、Codeforces 713D
- 5、Codeforces 762F
- 6、UOJ #54
- 7、Codeforces 715C
- 8、LYDSY 3451
- 9、UOJ #59
1、Codeforces 717A
给定整数 $k,l,r$，设 $T$ 为所有长度在 $[l,r]$ 间且不存在相邻两个0的01串的集合，求从 $T$ 中取出恰好 $k$ 个长度相同的串的方案数除以 $1,000,000,007$ 的余数。$1\le k\le 200,1\le l\le r\le 10^{18}$。
http://codeforces.com/problemset/problem/717/A
这场比赛我参加过，然后挂了……主要就是一开始想了很久的这一题，一直以为是矩阵快速幂，结果想了很久没能把矩阵构造出来。最后只好放弃了这题。
后来看了题解才发现这题做法好神。
首先，记 $f_i$ 为长度等于 $i$ 且不存在相邻两个0的01串个数，显然 $f_0=1,f_1=2$。考虑一个长度等于 $i$ 的01串，如果第 $i$ 位是1，那么只需前 $i-1$ 位不存在两个相邻的0即可，有 $f_{i-1}$ 种，如果第 $i$ 位是0，那么第 $i-1$ 位是1，有 $f_{i-2}$ 种，即
$$f_i=f_{i-1}+f_{i-2}$$
不难发现这就是一个Fibonacci数列，如果记 $F_i=\begin{cases}i,&i < 2,\\F_{i-1}+F_{i-2},&i\ge 2\end{cases}$，那么 $f_i=F_{i+2}$，于是答案等于
$$\sum_{i=l}^rC_{f_i}^k=\sum_{i=l}^rC_{F_{i+2}}^k$$
用经典的计数方法，记 $S_n=\sum_{i=0}^{n-1}C_{F_i}^k$，则答案为 $S_{r+3}-S_{l+2}$。
前面的这些转化都很简单，问题来了，如何计算 $S_i$？
组合数的式子看起来比较复杂，不过通过观察发现，$C_x^k=\frac{1}{k!}x(x-1)(x-2)...(x-k+1)$，是一个关于 $x$ 的 $k$ 次多项式，于是设对于所有 $x$ 有 $C_x^k=\sum_{i=0}^ka_ix^i$，显然通过 $O(k^2)$ 暴力求多项式乘法就能求出所有 $a_i$，则现在需要计算的是
$$S_i=\sum_{i=0}^{n-1}\sum_{j=0}^ka_jF_i^j=\sum_{i=0}^ka_i\sum_{j=0}^{n-1}F_j^i$$
我在考场上就卡在了如何计算 $\sum_{j=0}^{n-1}F_j^i$ 上。用类比思想，如果 $i=1$，那么就是求前 $n$ 项Fibonacci数的和，这个显然是矩阵快速幂可以解决的。那么 $i$ 更大的时候是不是能用一个 $O(k)\times O(k)$ 的矩阵来做呢？于是就掉坑了——就算能用矩阵做，复杂度也是错误的。
看了题解。正解利用到Fibonacci数的性质，更准确的说，是通项公式：
$$F_i=\frac{1}{\sqrt{5}}[(\frac{1+\sqrt{5}}{2})^i-(\frac{1-\sqrt{5}}{2})^i]$$
问题是模 $1,000,000,007$ 意义下 $5$ 没有平方根，怎么办？有一种很好的思路：用 $\sqrt 5$ 和有理数进行加、减、乘、除的结果在 $U=\{a+b\sqrt 5|a,b\in\mathbf{Q}\}$ 上封闭，因此把所有数表示为 $a+b\sqrt 5$ 即可，其中有理数的除法在模大质数 $1,000,000,007$ 意义下可以用乘法逆元来等效代替。
因此计算和式的时候可以展开 $F_i$，即：
$$\sum_{j=0}^{n-1}F_j^i=(\frac{1}{\sqrt{5}})^i\sum_{j=0}^{n-1}[(\frac{1+\sqrt{5}}{2})^j-(\frac{1-\sqrt{5}}{2})^j]^i \\ =(\frac{1}{\sqrt{5}})^i\sum_{j=0}^{n-1}\sum_{k=0}^iC_i^k(-1)^{i-k}(\frac{1+\sqrt{5}}{2})^{jk}(\frac{1-\sqrt{5}}{2})^{j(i-k)} \\ =(\frac{1}{\sqrt{5}})^i\sum_{k=0}^iC_i^k(-1)^{i-k}\sum_{j=0}^{n-1}[(\frac{1+\sqrt{5}}{2})^k(\frac{1-\sqrt{5}}{2})^{(i-k)}]^j$$
UPD：这里把和式的 $k$ 和题目给出的 $k$ 混淆了，不过由于式子中没有用到题目给出的 $k$，所以可以忽略。
计算 $\sum_{j=0}^{n-1}[(\frac{1+\sqrt{5}}{2})^k(\frac{1-\sqrt{5}}{2})^{(i-k)}]^j$ 可以使用快速幂在 $O(\log n)$ 时间内计算出来。这个算法枚举了 $i,k$，所以总复杂度就是 $O(k^2\log r)$。代码如下：
#include <iostream>
#define ll long long
#define MOD 1000000007
ll inv(int a,int p=MOD){return a==1?1:(1+p*(a-inv(p%a,a)))/a%p;}
struct num{ // a+b*sqrt(5)
int a,b;
num(int a=0,int b=0){this->a=a;this->b=b;}
num operator+(num x){return num((a+x.a)%MOD,(b+x.b)%MOD);}
num operator-(num x){return num((a-x.a+MOD)%MOD,(b-x.b+MOD)%MOD);}
num operator*(num x){return num((1ll*a*x.a+5ll*b*x.b)%MOD,(1ll*a*x.b+1ll*b*x.a)%MOD);}
};
num pow(num a,ll n,bool t=0){
num p=1,s=0;
int i=0;while(n>>i)i++;
while(i--){
s=s*(p+1),p=p*p;
if(n>>i&1)s=s+p,p=p*a;
}
return t?s:p;
}
ll a[210],C[210];
num pA[210],pB[210];
int main(){
int k;ll l,r;
std::cin>>k>>l>>r;
*pA=*pB=*a=*C=1;
for(int i=1;i<=k;(*a*=MOD+2-++i)%=MOD){
for(int j=i;j;j--)a[j]=(a[j-1]+a[j]*(MOD-i+1))%MOD;
pA[i]=pow(num(inv(2),inv(2)),i);
pB[i]=pow(num(inv(2),MOD-inv(2)),i);
}
num S=0,c=*a,x;
for(int i=0;i<=k;i++,c=pow(num(0,inv(5)),i)*a[i]){
for(int j=i;j>=0;j--){
x=(pow(pA[j]*pB[i-j],r+3,1)-pow(pA[j]*pB[i-j],l+2,1))*(j?(C[j]+=C[j-1])%=MOD:1)*c;
i-j&1?S=S-x:S=S+x;
}
}
for(int i=1;i<=k;i++)S=S*inv(i);
std::cout<<S.a<<'\n';
}2、TCO2014 Round 3B Div1 1000
给定长度为 $N-1$ 的数组 $p$ 以及整数 $K$，设无根树 $T=(V,E)$ 满足 $V=[0,N)\cap\mathbf{N}$，$E=\{(p[i],i+1)|i\in\mathbf{N},i < N-1\}$，求有多少个无根树 $T'=(V',E')$ 满足 $V'=V$ 且 $|E|-|E\cap E'|\le K$。$2\le N\le 50,0\le K\le 50$。
一开始看题的时候啥思路也没有，一开始从DP的角度考虑，发现树的条件难以用DP阶段来描述，如果强行DP只能状压，复杂度指数级。
正解依旧很神。
首先，考虑这样一个问题：给定带权完全图 $G=(V,E)$，$(u,v)\in E$ 的权值为 $w(u,v)$，可以认为 $w(u,u)=0$，设 $ST(G)$ 为 $G$ 的生成树集合，求
$$\sum_{T\in ST(G)}\prod_{(u,v)\in E(T)}w(u,v)$$
即经典的生成树计数问题。
结论是这样的：记 $n=|V(G)|$，用自然数 $0,1,...,n-1$ 代替 $V(G)$ 中的节点，构造 $(n-1)\times(n-1)$ 矩阵 $A$，其中
$$A_{i,j}=[i=j]\sum_{k=0}^{n-1}w(i,k)-w(i,j),0\le i,j < n-1$$
那么 $\det A$ 即为答案，求解模意义下的高斯消元即可在 $O(n^3)$ 时间内求出其值。证明比较复杂，vfk大神的博客 http://vfleaking.blog.163.com/blog/static/1748076342013112523651955/ 有详细的证明。
现在我们来做一件事情：随便设一个数 $x$，然后构造一个完全图 $G=(V,E_G)$，对于 $(u,v)\in E_G$，定义
$$w(u,v)=\begin{cases}1,&(u,v)\in E\\ x&(u,v)\not\in E\end{cases}$$
说白了就是把完全图中属于树 $T$ 的边权设为 $1$，不属于树 $T$ 的边权设为 $x$。然后对于一个 $G$ 的生成树 $T'=(V,E')$，设 $k=|E|-|E\cap E'|$，那么 $\prod{(u,v)\in E'}w(u,v)$ 的值是多少呢？由于 $T'$ 中有 $k$ 条边不属于 $T$，所以，很显然，这个式子的值是 $x^k$。
那么 $\sum_{T\in ST(G)}\prod_{(u,v)\in E(T)}w(u,v)$ 是一个关于 $x$ 的多项式 $a_0+a_1x+a_2x^2+...+a_{N-1}x^{N-1}$，其中 $a_i$ 为满足 $|E|-|E\cap E'|=i$ 的无根树 $T'$ 的数目。这里的问题解决方法思想类似于待定系数法，通过把 $x=0,1,2,...,N-1$ 的值代入求出 $\det A$，就能得到关于 $a_0,a_1,...,a_{N-1}$ 的一个方程组，用高斯消元解方程组即可求出每个 $a_i$，问题得以解决。
因为把每个 $x$ 代入求 $\det A$ 需要 $O(N^3)$ 的时间，所以总复杂度为 $O(N^4)$。代码如下：
#include <vector>
#define MOD 1000000007
using namespace std;
class TreeDistance{
public:
int a[50][50],b[50],x[50];
long long inv(int a,int p=MOD){return a==1?1:(1+p*(a-inv(p%a,a)))/a%p;}
int det(int n){
long long D=1;
for(int i=0,j,t;i<n;i++){
for(j=i;j<n&&!a[j][i];j++);
if(j==n)return 0;
for(int k=i;k<n;k++)t=a[i][i],a[i][i]=a[j][i],a[j][i]=t;
t=b[i];b[i]=b[j];b[j]=t;
D=D*(j==i?a[i][i]:MOD-a[i][i])%MOD;
for(j=i+1;j<n;j++)if(a[j][i]){
t=(MOD-a[j][i])*inv(a[i][i])%MOD;
for(int k=i;k<n;k++)a[j][k]=(a[j][k]+1ll*a[i][k]*t)%MOD;
b[j]=(b[j]+1ll*b[i]*t)%MOD;
}
}
return D;
}
int countTrees(vector <int> p, int K){
int n=p.size(),N=n+1;
for(int t=0;t<N;t++){
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)a[i][j]=0;
for(int i=0;i<n;i++)
for(int j=i+1,z;j<N;j++)z=i&&p[i-1]==j||j&&p[j-1]==i?1:t,(a[i][j]+=MOD-z)%=MOD,(a[j][i]+=MOD-z)%=MOD,(a[i][i]+=z)%=MOD,(a[j][j]+=z)%=MOD;
x[t]=det(n);
}
for(int i=0;i<N;b[i]=x[i],i++)
for(int j=*a[i]=1;j<N;j++)a[i][j]=1ll*a[i][j-1]*i%MOD;
det(N);
for(int i=N,j;i--;x[i]=x[i]*inv(a[i][i])%MOD)
for(x[i]=b[i],j=N;--j>i;)x[i]=(x[i]+1ll*(MOD-a[i][j])*x[j])%MOD;
long long s=0;
for(int i=0;i<N&&i<=K;i++)(s+=x[i])%=MOD;
return s;
}
};3、Codeforces 722E
给定 $n\times m$ 的网格图和图中一个大小为 $k$ 的格子集合 $S$，再给定正整数 $s$。现在从所有从网格图的左上角走到右下角，每一步只往下或往右走一格的路径中随机选取一条，然后沿着这条路径走，每次经过属于 $S$ 的格子时，修改 $s\leftarrow\lceil\frac{s}{2}\rceil$。求到达右下角时 $s$ 的值的期望除以 $1,000,000,007$ 的余数，即 $E(s)\bmod 1,000,000,007$。显然 $E(s)$ 是一个有理数。$1\le n, m\le 100,000, 0\le k\le 2,000, 1\le s\le 1,000,000$。
http://codeforces.com/problemset/problem/722/E
这场比赛我也参加过，也打挂了……主要就是因为这题花了太多时间，然而没有做出来。
这道题我想复杂掉坑了，只想出了 $O(k^3\log s)$ 的做法，过不了，然后一直想着怎么去优化这个算法，结果失败了。为什么掉坑了？因为之前做过一道求不经过 $S$ 中的格子的路径条数，我用的是容斥原理来解决，因此觉得这题只能用容斥原理……
我的思路是这样的：设 $f_A$ 为所有路径中，经过的 $S$ 中的格子的集合恰好为 $A$ 的路径条数，$g_A$ 为所有路径中，经过了集合 $A$ 中的所有格子的路径条数。那么显然有 $g_A=\sum_{B\subseteq S,B\supseteq A}f_B$。这样是指数级的，我们只需要知道经过的格子个数即可，因此记 $f'_i=\sum_{A\subseteq S,|A|=i}f_A,g'_i=\sum_{A\subseteq S,|A|=i}g_A$，则
$$g'_i=\sum_{A\subseteq S,|A|=i}\sum_{B\subseteq S,B\supseteq A}f_B=\sum_{B\subseteq S}f_B\sum_{A\subseteq B,|A|=i}1=\sum_{B\subseteq S}C_{|B|}^if_B=\sum_{j=i}^kC_j^i\sum_{B\subseteq S,|B|=j}f_B=\sum_{j=i}^kC_j^if'_j$$
从而可以得到容斥的式子 $f'_i=\sum_{j=i}^kC_j^i(-1)^{j-i}g'_j$.
同时 $g'_i$ 可以用DP求出：记 $g(i,j)$ 为以 $i\in S$ 为起点，右下角为终点时，对于所有 $S$ 的大小为 $j$ 的子集 $A$，从 $i$ 到终点经过子集 $A$ 中的所有格子到终点的路径条数之和，则 $g(i,0)=C_{n-r_i+m-c_i}^{n-r_i}$，当 $j > 0$ 时
$$g(i,j)=\sum_{r_{i'}\ge r_i,c_{i'}\ge c_i,i'\ne i}C_{r_{i'}-r_i+c_{i'}-c_i}^{r_{i'}-r_i}g(i',j-1)$$
这里我们把左上角格 $s$ 加入 $S$，那么 $g'_i=g(s,i)$，这样就能得到所有 $f'_i$，答案就是 $1+\frac{1}{C_{n+m-2}^{n-1}}\sum_{i=0}^kf'_i\lfloor\frac{s-1}{2^i}\rfloor$。
问题来了！$g(i,j)$ 的状态数是 $O(k^2)$，每个状态转移数为 $O(k)$，总转移数为 $O(k^3)$，无法通过！虽然注意到答案中 $f'_i$ 的 $i$ 这一维只用到了 $\log_2s$，但是计算 $f'_i$ 所用到的 $g'_j$ 的 $j$ 到了 $k$ 级别。怎么优化呢？我一直觉得很容易优化，但尝试多种思路之后以失败告终。
最后去看了题解……
首先题目说不经过任何一个 $S$ 中的格子的路径条数可以用 $g(i)=C_{n-r_i+m-c_i}^{n-r_i}-\sum_{j\ne i}C_{r_j-r_i+c_j-c_i}^{r_j-r_i}g(j)$ 来递推，这其实就是之前的容斥原理。问题是题解并没有用到容斥啊！那这是由什么依据得到的？枚举第一个经过的点？
如果从 $i$ 出发第一个到 $j$，那么 $i$ 到 $j$ 这一段不能经过别的 $S$ 中的点，这个好像也不能预处理……继续不知所措。
继续对着式子理解才发现——原来枚举的是最后一个经过的点！
是啊，既然枚举第一个经过的点不可行，那我们就用逆向思维：枚举最后一个经过的点就可以啦！
求从 $i$ 出发至少经过一个 $S$ 中的点的路径条数，枚举最后一个经过的点 $j$，那么 $i$ 到 $j$ 可以任意走，$j$ 到终点不能经过 $S$ 中的点。类似的，原来的问题也很好解决了：设 $f(i,j)$ 为从 $i$ 出发经过恰好 $j$ 个 $S$ 中的点的方案数，首先一共有 $C_{n-r_i+m-c_i}$ 条路径，其中，计算经过超过 $j$ 个 $S$ 中的点的方案数，可以枚举倒数第 $j+1$ 个点 $i'$，方案数为 $C_{r_{i'}-r_i+c_{i'}-c_i}^{r_{i'}-r_i}f(i',j-1)$，从总路径数减掉超过 $j$ 个点的路径数以后，再减掉少于 $j$ 个点的，即 $\sum_{j'=0}^{j-1}f(i,j')$。于是我们得到了递推式：
$$f(i,j)=C_{n-r_i+m-c_i}-\sum_{i'\ne i}C_{r_{i'}-r_i+c_{i'}-c_i}^{r_{i'}-r_i}f(i',j-1)-\sum_{j'=0}^{j-1}f(i,j')$$
设左上角为 $s$，则 $f'_i=f(s,i)$，用之前计算答案的式子计算即可。状态数优化到了 $O(k\log s)$，复杂度 $O(k^2\log s)$。代码如下：
#include <cstdio>
#include <iostream>
#define ll long long
#define MOD 1000000007
int n,m,k,s,r[2010],c[2010];
ll fac[200010],ifac[200010],f[2010][21];
ll inv(int a,int p){return a==1?1:(1+p*(a-inv(p%a,a)))/a%p;}
ll dfs(int i,int j){
if(f[i][j])return f[i][j]-1;
f[i][j]=fac[n+m-r[i]-c[i]]*ifac[n-r[i]]%MOD*ifac[m-c[i]]%MOD;
for(int t=j;t--;)(f[i][j]+=MOD-dfs(i,t))%=MOD;
for(int t=k;t--;)if(t!=i&&r[t]>=r[i]&&c[t]>=c[i])(f[i][j]+=(MOD-fac[r[t]+c[t]-r[i]-c[i]])*ifac[r[t]-r[i]]%MOD*ifac[c[t]-c[i]]%MOD*dfs(t,j))%=MOD;
return f[i][j]++;
}
int main(){
scanf("%d%d%d%d",&n,&m,&k,&s);
for(int i=0;i<k;i++)scanf("%d%d",r+i,c+i);
r[k]=c[k]=1;
for(int i=*fac=1;i<=n+m;i++)fac[i]=fac[i-1]*i%MOD;
ifac[n+m]=inv(fac[n+m],MOD);
for(int i=n+m;i--;)ifac[i]=ifac[i+1]*(i+1)%MOD;
ll ans=0;s--;
for(int j=0;s;j++,s/=2)(ans+=dfs(k,j)*s)%=MOD;
std::cout<<(ans*ifac[n+m-2]%MOD*fac[n-1]%MOD*fac[m-1]+1)%MOD;
}其实问题比我想象的简单得多，完全没有必要用到容斥之类的复杂算法，这也说明思考问题不能局限于一种思路。比如统计“不含 $S$”的方案数时，可以用容斥，也可以用总的方案数减去至少含一个 $S$ 的方案数，而后者可以枚举第一个 $S$ 中的元素，等等。
4、Codeforces 713D
给定 $n\times m$ 的01矩阵 $a_{i,j}$（$1\le i\le n,1\le j\le m,0\le a_{i,j}\le 1$），再给出 $t$ 组询问，每组询问给出四个整数 $x_1,y_1,x_2,y_2$（$1\le x_1\le x_2\le n,1\le y_1\le y_2\le m$），求第 $x_1$ 至 $x_2$ 行第 $y_1$ 至第 $y_2$ 列的最大全1子正方形大小，形式化地，求一个最大的 $b$，使得存在整数 $x,y$ 使得 $x,x+b-1\in[x_1,x_2]$，$y,y+b-1\in[y_1,y_2]$，且 $\forall x'\in\{x,x+1,...,x+b-1\},y'\in\{y,y+1,...,y+b-1\},a_{x',y'}=1$。$1\le n,m\le 1,000$，$t\le 1,000,000$。
http://codeforces.com/problemset/problem/713/D
考场上因为没时间所以没看这题，后来看这题的时候想了很久，并没有想出什么靠谱的做法。
我的想法是，首先如果是单次询问，可以DP求出最大的子正方形：$f(x,y)$ 表示以 $(x,y)$ 为左上角的最大全1子正方形大小，那么
$$f(x,y)=\begin{cases}0,&a_{x,y}=0,\\ \max\{f(x,y+1),f(x+1,y),f(x+1,y+1)\}+1,&a_{x,y}=1.\end{cases}$$
既然询问次数 $t$ 这么大，就不能每次求一遍DP，那么子矩阵的DP值有没什么性质呢？然后我发现，设 $f'(x,y)$ 为询问子矩形内以 $(x,y)$ 为左上角的最大全1子正方形大小，则
$$f'(x,y)=\min\{f(x,y),x_2-x+1,y_2-y+1\}$$
接着，我想用一些数据结构来维护上面这个式子的值，然而似乎各种数据结构都维护不了。还尝试着把每个格子和它的 $f(x,y)$ 表示成一个三维点，然后维护不同的区域的点权最大值——但是并不可做。
看完题解发现这题并不难，是我自己太傻逼了没想到做法。
这种最大化最小值（即 $\min\{f(x,y),|x_2-x+1|,|y_2-y+1|\}$）的题，显然要想到二分啊！二分一个 $b$，然后判定是否存在 $x,y$ 使得 $x_1\le x\le x_2,y_1\le y\le y_2,\min\{f(x,y),x_2-x+1,y_2-y+1\}\ge b$，即
$$\begin{cases}x_1\le x\le x_2-b+1 \\ y_1\le y\le y_2-b+1 \\ f(x,y)\ge b\end{cases}$$
只需查询子矩形内的 $f(x,y)$ 最大值即可，这是一个二维RMQ问题，使用Sparse Table即可用 $O(nm\log n\log m)$ 的时间预处理，每次 $O(1)$ 的时间查询。
由于每次询问要二分，所以总复杂度就是 $O(nm\log n\log m+t\log\min\{n,m\})$。代码如下（为了节省内存，我开了 short）：
#include<cstdio>
#define g f[x][y]
short f[1001][1001][10][10],log[1001];
short min(short x,short y){return x<y?x:y;}
short max(short x,short y){return x>y?x:y;}
int main(){
int n,m,t,x1,y1,x2,y2,N;scanf("%d%d",&n,&m);N=n>m?n:m;
for(int x=0;x<n;x++)for(int y=0;y<m;y++)scanf("%d",&t),**f[x][y]=t;
for(int i=2;i<=N;i++)log[i]=log[i/2]+1;
for(int x=n;x--;)for(int y=m;y--;){
if(**g)**g=1+min(min(**f[x][y+1],**f[x+1][y]),**f[x+1][y+1]);
for(int i=0;i<=log[n];i++)for(int j=0;j<=log[m];j++)g[i][j]=j?max(g[i][j-1],y+(1<<j-1)<m?f[x][y+(1<<j-1)][i][j-1]:0):i?max(g[i-1][j],x+(1<<i-1)<n?f[x+(1<<i-1)][y][i-1][j]:0):g[i][j];
}
for(scanf("%d",&t);t--;){
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);x1--;y1--;
int L=0,R=min(x2-x1,y2-y1)+1,M,i,j;
while(R-L>1)M=L+R>>1,i=log[x2-x1-M+1],j=log[y2-y1-M+1],max(max(f[x1][y1][i][j],f[x1][y2-M+1-(1<<j)][i][j]),max(f[x2-M+1-(1<<i)][y1][i][j],f[x2-M+1-(1<<i)][y2-M+1-(1<<j)][i][j]))<M?R=M:L=M;
printf("%d\n",L);
}
}这题一开始的时候把一个 y1 打成了 y2，导致样例通过然而提交之后WA。后来通过自己手工测试小数据就发现了这个问题。所以，以后在Codeforces这种无法花太多时间对拍的比赛时务必多测试几组手构的数据。
5、Codeforces 762F
给定无根树 $S,T$，求有多少个 $S$ 的连通子图 $G$ 与 $T$ 同构，答案对 $10^9+7$ 取模。图 $G$ 与 $T$ 同构当且仅当存在一个满单射 $f:V(G)\rightarrow V(T)$ 使得 $\forall (u,v)\in E(G),(f(u),f(v))\in E(T)$。
用 $|S|,|T|$ 表示 $S,T$ 的节点数，$|S|\le 1,000$，$|T|\le 12$。
http://codeforces.com/problemset/problem/762/F
这题是前几天Educational Round的题，我作为未参加比赛的场外选手围观了一下，发现这题看起来挺简单，于是就准备直接上树形DP：任取 $S$ 中的节点作为根，然后枚举 $G$ 中深度最小的点 $u$，接着枚举 $T$ 的根 $v$，令 $f(u)=v$，接着就可以设计一个DP了？$f(u,v)$ 表示 $S_u$ 取一个连通子图和 $T_v$ 同构的方案数（这里 $S_u$ 表示 $S$ 中以 $u$ 为根的子树，$T_v$ 意思类似），那么就是枚举每个 $v$ 的子节点 $c_v\in C_v$ 和哪个 $u$ 的子节点 $c_u\in C_u$ 配对，也就是枚举 $C_v\rightarrow C_u$ 的所有可能的映射，答案乘上 $f(c_u,c_v)$，所有乘积加起来就好了？（$C_u$ 表示 $u$ 的子节点集合，$C_v$ 类似）
$$f(u,v)=\sum_{g:C_v\rightarrow C_u,\forall p\ne q,g(p)\ne g(q)}\prod_{p\in C_v}f(g(p),p)$$
但当我写完这个式子以后发现是错的，因为这样会算重复。比如 $S=T=(\{1,2,3\},\{(1,2),(1,3)\})$，那么 $g(2)=2,g(3)=3$ 和 $g(2)=3,g(3)=2$ 算了两次，导致 $f(1,1)=2$，但是 $S$ 与 $T$ 同构的子图只有 $S$ 本身一个。
怎么办呢？当时想能否不枚举映射而枚举子集，这样就能满足定义，然而枚举了子集却无法转移，因为就不知道哪个子树和哪个子树对应。
于是就不会了……接着又想了一会儿，发现了一种一直被我忽略的思路。
如果强行按照上面这种“错误算法”来算，那么算出来的是啥？很显然，就是所有从 $S$ 中选出 $|T|$ 个节点标上标号 $1,2,...,|T|$，使得对任意 $(u,v)\in T$，$S$ 中标号 $u,v$ 的两点必有一条边相连。
然后我们要求的答案是啥？是选出 $S$ 中的 $|T|$ 个节点，使得它的导出子图与 $T$ 同构。
如果用“错误算法”选出了一个大小为 $|T|$ 的子集，它和 $T$ 是不同构的，那么它有几种标号方案？显然是 $0$，根据定义显然。
如果是同构的呢？这就相当于有两个完全相同的树 $T_1,T_2$，要求把 $T_2$ 中的所有节点 $v$ 重新编号为 $f(v)$（$f$ 是 $V(T)$ 的一个满单射），使得 $\forall (u,v)\in E(T_1),(f(u),f(v))\in E(T_2)$。也就是标号方案数只和 $T$ 有关。我们用 $K$ 表示这样的标号方案数。
这样，如果答案是 $I$，那么“错误算法”求出的答案就是 $IK\bmod(10^9+7)$。而 $K$ 显然是可以用同样的“错误算法”求出来的。
并且由于 $|T|\le 12$，可得 $1\le K\le 12! < 10^9+7$，因此 $K$ 在模 $10^9+7$ 意义下有逆元，把错误的答案乘上 $K$ 就能得到正确的答案了。
现在的算法就明确了，枚举 $T$ 的根 $v$，然后做一遍上述的DP，计算出答案 $\mathrm{ans}(S,T)=\sum_{u\in V(S)}f(u,v)$；之后把 $S$ 换成 $T$ 再做一遍求出 $\mathrm{ans}(T,T)$，答案就是 $\mathrm{ans}(S,T)\cdot\mathrm{ans}(T,T)^{-1}\pmod{10^9+7}$。
然而DP还需要优化，因为求 $f(u,v)$ 时不能暴力枚举所有 $C_v\rightarrow C_u$ 的映射。我们可以用一个辅助的状压DP，记 $f'(i,V)$ 为将 $V$ 用 $g$ 映射到 $u$ 的前 $i$ 个子节点的 $\prod_{v}f(g(v),v)$ 的和，枚举第 $i$ 个子节点 $c_i$ 是否被 $V$ 中的点映射，以及被 $V$ 中哪一个点映射，即可得到
$$f'(i,V)=f'(i-1,V)+\sum_{j\in V}f'(i-1,V-\{j\})f(c_i,j)$$
这样对于 $T$ 的每一个根，DP复杂度就是 $O(|S||T|\cdot 2^{|T|})$，总复杂度 $O(|S||T|^2\cdot 2^{|T|})$，实际上已经可以通过了：
#include <cstdio>
#include <cstring>
#define MOD 1000000007
struct edge{int to;edge*next;};
struct Tree{
int n,ch[1001][1001],ccnt[1001],cset[1001];
edge E[2000],*ne,*first[1001];
void link(int u,int v){*ne=(edge){v,first[u]};first[u]=ne++;}
void read(){
scanf("%d",&n);ne=E;
for(int i=1,u,v;i<n;i++)scanf("%d%d",&u,&v),link(u,v),link(v,u);
}
void dfs(int i,int f){
int c=cset[i]=0;
for(edge*e=first[i];e;e=e->next)
if(e->to!=f)dfs(ch[i][c++]=e->to,i),cset[i]|=1<<e->to-1;
ccnt[i]=c;
}
}S,T;
int f[1001][1<<12];
int dfs(int i,int j,int V){
if(!j)return!V;
int&s=f[S.ch[i][j-1]][V];
if(s)return s-1;
s=dfs(i,j-1,V);
for(int c=S.ch[i][j-1],k=0;k<T.n;k++)
if(V>>k&1)s=(s+1ll*dfs(i,j-1,V-(1<<k))*dfs(c,S.ccnt[c],T.cset[k+1]))%MOD;
return s++;
}
long long inv(int a,int p){return a==1?1:(1+p*(a-inv(p%a,a)))/a%p;}
int main(){
S.read();T.read();
S.dfs(1,0);
int ans=0;
for(int r=1;r<=T.n;r++){
T.dfs(r,0);
for(int i=1;i<=S.n;i++)ans=(ans+dfs(i,S.ccnt[i],T.cset[r]))%MOD;
memset(f,0,sizeof(f));
}
S=T;
S.dfs(1,0);
int ans2=0;
for(int r=1;r<=T.n;r++){
T.dfs(r,0);
ans2=(ans2+dfs(1,S.ccnt[1],T.cset[r]))%MOD;
memset(f,0,sizeof(f[0])*13);
}
ans=ans*inv(ans2,MOD)%MOD;
printf("%d\n",ans);
}我一开始提交的时候WA了，经过检查枚举 $T$ 的根 r 时，f 数组忘记每次清空，于是加了一个 memset 清空数组，然而交上去再次WA，因为前面一个循环加了后面一个循环忘了加= =b
后来 immortalCO 告诉我他的做法，不用枚举 $T$ 的根，而是在DP中记边的信息，即记 $f(u,e)$ 表示 $S$ 的 $u$ 子树和 $T$ 中由 $e$ 这条边指向的子树的匹配方案数，这样复杂度就少一个 $|T|$ 了。
6、UOJ #54
求有多少种方案从 $n$ 维空间中选取 $c$ 个点，每个点的第 $i$ 维坐标为不超过 $m_i$ 的正整数，对于每一维坐标所有点的坐标严格递增，且 $c$ 个点共线。详细题意及数据规模见题目链接。
这题是我去年就思考过的一个问题。$n$ 维空间比较抽象，因此先从 $2$ 维空间开始考虑。一种容易入手的思路是这样的：枚举第一个点 $P_1$ 和最后一个点 $P_c$，那么需要在线段 $P_1P_c$（除去 $P_1,P_c$ 两点）上取 $c-2$ 个整点 $P_2,...,P_{c-1}$。设 $P_i(x_i,y_i)$，则点 $P_i$ 在直线 $P_1P_c$ 上的条件是 $(x_c-x_1)(y_i-y_1)=(y_c-y_1)(x_i-x_1)$，记 $g=\gcd(x_c-x_1,y_c-y_1)$，那么方程的通解是 $x_i=x_1+\frac{x_c-x_i}{g}t,y_i=y_1+\frac{y_c-y_i}{g}t,t\in\mathbf{Z}$。$P_i$ 在线段 $P_1P_c$ 上还需要多一个条件 $x_1 < x_i < x_c$，即 $0 < t < g$。因此如果已经确定 $P_1,P_c$，那么线段 $P_1P_c$（除去 $P_1,P_c$ 两点）上有 $g-1$ 个整点，因此再取 $c-2$ 个整点有 $C_{g-1}^{c-2}$ 种方案，其中 $g=\gcd(x_c-x_1,y_c-y_1)$。
当然枚举 $P_1,P_c$ 太慢，可以枚举 $x=x_c-x_1$ 和 $y=y_c-y_1$，接下来 $P_1$ 和 $P_c$ 的选取方案数为 $(m_1-x)(m_2-y)$，答案就是 $\sum_{x=1}^{m_1}\sum_{y=1}^{m_2}(m_1-x)(m_2-y)C_{\gcd(x,y)-1}^{c-2}$。
这个结论可以推广为 $n$ 维的情形，原理是一致的，答案为：
$$\sum_{x_1=1}^{m_1}(m_1-x_1)\sum_{x_2=1}^{m_2}(m_2-x_2)...\sum_{x_n=1}^{m_n}(m_n-x_n)C_{\gcd(x_1,x_2,...,x_n)}^{c-2}$$
这个式子怎么优化计算？之前我研究 $n=2$ 怎么做的时候想到的做法是这样的：构造一个 $m_1\times m_2$ 的表，左上角为 $(1,1)$，右下角为 $(m_1,m_2)$，然后进行 $\min\{m_1,m_2\}$ 轮填数，第 $i$（$1\le i\le\min\{m_1,m_2\}$）轮将 $x,y$ 均为 $i$ 的倍数的格子 $(x,y)$ 内填入 $(m_1-x)(m_2-y)$ 个数 $i$。填完之后，每个格子 $(x,y)$ 内的数的集合就是 $\gcd(x,y)$ 的所有因数，如果能构造一个函数 $f(x)$ 满足对任意 $x$，有
$$\sum_{d|x}f(d)=C_{x-1}^{c-2}$$
那么每个格子 $(x,y)$ 内所有数 $x$ 的 $f(x)$ 之和就是 $(m_1-x)(m_2-y)C_{\gcd(x,y)-1}^{c-2}$。考虑填的过程，可得答案为
$$\sum_{i=1}^{\min\{m_1,m_2\}}f(i)\sum_{x=1}^{\lfloor\frac{m_1}{i}\rfloor}(m_1-ix)\sum_{y=1}^{\lfloor\frac{m_2}{i}\rfloor}(m_2-iy)$$
化简得到
$$\sum_{i=1}^{\min\{m_1,m_2\}}f(i)\left[m_1\lfloor\frac{m_1}{i}\rfloor-\frac{1}{2}\lfloor\frac{m_1}{i}\rfloor(\lfloor\frac{m_1}{i}\rfloor+1)i\right]\left[m_2\lfloor\frac{m_2}{i}\rfloor-\frac{1}{2}\lfloor\frac{m_2}{i}\rfloor(\lfloor\frac{m_2}{i}\rfloor+1)i\right]$$
类似的，可以得到 $n$ 维的情形：
$$\sum_{i=1}^{\min\{m_1,...,m_n\}}f(i)\prod_{j=1}^n\left[m_j\lfloor\frac{m_j}{i}\rfloor-\frac{1}{2}\lfloor\frac{m_j}{i}\rfloor(\lfloor\frac{m_j}{i}\rfloor+1)i\right]$$
其中，$f(x)$ 函数可以递推计算：一开始令所有 $f(x)\leftarrow C_{x-1}^{c-2}$，然后依次对于 $i=1,2,...$，令所有 $j=2,3,...$ 更新 $f(ij)\leftarrow f(ij)-f(i)$ 即可，记 $M=\min\{m_1,m_2,...,m_n\}$，复杂度为 $O(\frac{M}{1}+\frac{M}{2}+...+\frac{M}{M})=O(M\log M)$。
这样对于每组数据的复杂度为 $O(M\log M+Mn)$，可以通过部分测试点，但不能AC。如何优化？
去年的时候 immortalCO 讲过一种技巧：$\lfloor\frac{M}{i}\rfloor$ 只有不超过 $2\sqrt M$ 种取值，所以可以枚举 $\lfloor\frac{M}{i}\rfloor$ 的每种取值对应的 $i$ 的区间，每个区间可以快速计算。于是当时我就仔细研究了下 $n=2$ 的情形：由于 $\lfloor\frac{m_1}{i}\rfloor$ 和 $\lfloor\frac{m_2}{i}\rfloor$ 的段数之和不超过 $2\sqrt{m_1}+2\sqrt{m_2}$，设某一段区间 $i\in[l,r]$ 的 $\lfloor\frac{m_1}{i}\rfloor=a,\lfloor\frac{m_2}{i}\rfloor=b$，则这一段的和为
$$\sum_{i=l}^rf(i)\left[m_1a-\frac{1}{2}a(a+1)i\right]\left[m_2b-\frac{1}{2}b(b+1)i\right] \\ =\sum_{i=l}^r\left[m_1m_2abf(i)-\frac{1}{2}a(a+1)m_2bif(i)-\frac{1}{2}b(b+1)m_1aif(i)+\frac{1}{4}a(a+1)b(b+1)i^2f(i)\right]$$
因此维护 $f(i)$ 的前缀和、$if(i)$ 的前缀和、$i^2f(i)$ 的前缀和，就能在预处理之后 $O(\sqrt{M}n)$ 解决每组数据，预处理时对每一个 $c$ 预处理 $f(i),if(i),i^2f(i)$ 的前缀和，可以通过 $n=2$ 的数据。
然后，由于我太辣鸡了并没有想出 $n > 2$ 时怎么做……
等我后来看这道题的题解的时候，发现自己很蠢，明明想法已经十分接近正解，却没有继续想下去。其实这个性质进一步推广就是：对于所有的正整数 $j\le n$，$\lfloor\frac{m_j}{i}\rfloor$ 的段数之和不超过 $n\sqrt M$，而 $n\le 11$，所以这个值显然是可以接受的。
对于每一段 $i\in[l,r]$，记 $\lfloor\frac{m_j}{i}\rfloor=a_j$，则 $\prod_{j=1}^n\left[m_ja_j-\frac{1}{2}a_j(a_j+1)i\right]$ 是一个 $n$ 次多项式 $k_0+k_1i+k_2i^2+...+k_ni^n$，可以用 $O(n^2)$ 的时间暴力乘法，只要对每个 $j=0,1,...,n$ 维护了 $i^jf(i)$ 的前缀和，就能对于每一段 $[l,r]$，在 $O(n^2)$ 的时间内求出 $\sum_{i=l}^r\prod_{j=1}^n\left[m_ja_j-\frac{1}{2}a_j(a_j+1)i\right]$。
预处理对每一个 $c,j$ 预处理 $i^jf(i)$ 的前缀和，因此总复杂度为 $O(cnM+Tn^3\sqrt M)$。注意模意义下的运算比较多，注意乘法溢出，我一开始写的时候就因为乘法溢出WA成了50分，样例和 $n$ 较大的测试点都通过了，而 $n$ 较小的测试点反而错了，建议构造易于手算的 $m_i$ 比较大的测试数据，以及将代码中的 int 改成 long long 对拍。代码如下（由于LYDSY评测较慢且计算总时限，预处理满的 $19\times 12\times 100000$ 如果常数大会导致过不了，于是我先读入所有数据，得到最大的 $n,c,m_i$ 再预处理以缩短小测试点的运行时间）：
#include <cstdio>
#include <algorithm>
#define MOD 10007
int T,N[1000],C[1000],M[1000][11],maxn,maxc,maxm,
f[19][100001][12],pos[7100],a[12];
int main(){
scanf("%d",&T);
for(int t=0;t<T;t++){
scanf("%d%d",N+t,C+t);
if(N[t]>maxn)maxn=N[t];
if((C[t]-=2)>maxc)maxc=C[t];
for(int i=0;i<N[t];i++)scanf("%d",M[t]+i),M[t][i]>maxm?maxm=M[t][i]:1;
}
for(int i=0;i<=maxc;i++)
for(int j=*f[0][1]=1;j<=maxm;j++)*f[i][j]=i?(*f[i][j-1]+*f[i-1][j-1])%MOD:1;
for(int i=0;i<=maxc;i++){
for(int j=1;j<=maxm;j++){
for(int k=j+j;k<=maxm;k+=j)(*f[i][k]+=MOD-*f[i][j])%=MOD;
for(int k=1;k<=maxn;k++)f[i][j][k]=f[i][j][k-1]*j%MOD;
for(int k=maxn;k>=0;k--)(f[i][j][k]+=f[i][j-1][k])%=MOD;
}
}
for(int t=0;t<T;t++){
int n=N[t],c=C[t],*m=M[t],M=1<<30,cnt=0,S=0;
for(int i=0;i<n;i++)m[i]<M?M=m[i]:1;
for(int i=0;i<n;i++)
for(int j=1,t;j<=M;j=m[i]/(m[i]/j)+1)pos[cnt++]=j;
std::sort(pos,pos+cnt);
cnt=std::unique(pos,pos+cnt)-pos;
pos[cnt]=M+1;
for(int i=0;i<cnt;i++){
*a=1;
for(int j=0,A,B;j<n;j++){
A=m[j]/pos[i]%MOD;B=-A*(A+1ll)/2%MOD;(A*=m[j])%=MOD;
a[j+1]=a[j]*(B<0?B+=MOD:B)%MOD;
for(int k=j;k;k--)a[k]=(a[k]*A+a[k-1]*B)%MOD;
(*a*=A)%=MOD;
}
for(int j=0;j<=n;j++)(S+=(f[c][pos[i+1]-1][j]-f[c][pos[i]-1][j]+MOD)*a[j])%=MOD;
}
printf("%d\n",S);
}
}7、Codeforces 715C
给定无根树 $T=(V,E)$ 和正整数 $M$，保证 $\gcd(M,10)=1$，每条边 $e_i=(u_i,v_i)\in E$ 上有一个数 $w_i\in\{1,2,...,9\}$，求 $T$ 中有多少条非空的有向路径 $(u,v)$，满足 $u$ 到 $v$ 的路径经过的数能被 $M$ 整除。一条依次经过边 $e_1,e_2,...,e_{k-1}$ 的路径经过的数定义为
$$\sum_{i=1}^{k-1}w_i\cdot 10^{k-i-1}$$
树 $T$ 的节点数 $n\le 100,000$，$M\le 10^9$。
http://codeforces.com/problemset/problem/715/C
这场CF也是我打挂的一场，我考场上没做出这题。
这是一道解法比较显然的题。
路径统计问题很容易想到树分治，即先找出树的重心 $g\in V$，然后统计经过 $g$ 且满足条件的路径数，接着把 $g$ 删掉，将 $T$ 分成多个子树 $T_1,T_2,...,T_k$，对每个子树 $T_i(i=1,2,...,k)$ 递归处理。
如果找出了树的重心 $g$，怎么求有多少条路径经过点 $g$ 且路径经过的数在模 $M$ 意义下为 $0$？这个也是很好处理的，对于路径 $(u,v)$，如果记 $w_1,w_2,...,w_p$ 为从 $u$ 到 $g$ 的路径依次经过的数，$g$ 到 $v$ 的路径依次经过的数为 $w_{p+1},...,w_{k-1}$，那么
$$\sum_{i=1}^{k-1}10^{k-i-1}w_i\equiv 0\pmod M\Leftrightarrow\sum_{i=1}^p10^{p-i}w_i\equiv-\sum_{i=p+1}^{k-1}10^{p-i}w_i\pmod M$$
注意上面的式子除以了 $10$ 的幂，需要利用 $\gcd(M,10)$ 的性质，求出 $10$ 在模 $M$ 意义下的逆元。以 $u\rightarrow g$ 的路径为例，$p-i$ 就是以 $g$ 为根时这条边的终点在 $T$ 中的深度。
以 $g$ 为根对 $T$ 遍历求出每个点的深度 $d_i$（$d_g=0,d_i=d_{f_i}+1$），然后对于一条边 $e_i=(f_v,v)$，定义其权值
$$a_v=10^{d_{f_v}}w_i\bmod M$$
$$b_v=-10^{-d_v}w_i$$
求出每个点到 $g$ 的路径上的 $a_v$ 和 $b_v$ 边权的和 $A_v,B_v$（$A_g=B_g=0,A_v=A_{f_v}+a_v\bmod M,B_v=B_{f_v}+b_v\bmod M$），这样一条过点 $g$ 的路径 $(u,v)$ 合法当且仅当 $A_u=B_v$。
如何只统计过点 $g$ 的路径？以 $g$ 为根时，记 $g$ 有 $c$ 个子节点，把 $g$ 标记为 $0$，把 $g$ 的每一个子树标记为 $1,2,...,c$，记 $t_i$ 为节点 $i$ 标记的树，现在的任务是统计满足以下条件的点对 $u,v$ 数：
$$t_u\ne t_v,A_u=B_v$$
一种简单粗暴的做法是把 $V$ 中的点按双关键字 $(A_v,t_v)$ 排序得到序列 $A'$，按双关键字 $(B_v,t_v)$ 排序得到序列 $B'$，接着对 $A'$ 中的每个元素 $u$ 在 $B'$ 中用Two-Pointers技巧找出满足 $A_u=B_v$ 的 $v$ 的个数以及 $A_u=B_v,t_u=t_v$ 的 $v$ 的个数，相减就是满足 $A_u=B_v,t_u\ne t_v$ 的 $v$ 的个数。由于要排序，每层复杂度为 $O(n\log n)$，总复杂度是 $O(n\log^2n)$，可以通过本题。也可以使用Hash表进一步优化复杂度。
然而就这么一道裸题我在考场上都写不出来，可见我的代码能力有多差……代码如下：
#include <cstdio>
#include <iostream>
#include <algorithm>
#define Fe for(edge*e=first[x];e;e=e->next)if(!vis[e->to]&&e->to!=fa[x])
int n,M;
long long pow1[100010],pow2[100010],ans;
struct edge{int to,w;edge*next;}E[200010],*ne=E,*first[100010];
void link(int u,int v,int w){*ne=(edge){v,w,first[u]};first[u]=ne++;}
int Q[100010],fa[100010],siz[100010],fr[100010],dep[100010],D1[100010],D2[100010],L[100010];
bool vis[100010];
long long inv(int a,int p){return a==1?1:(1+p*(a-inv(p%a,a)))/a%p;}
bool cmp1(int i,int j){return D1[i]<D1[j]||D1[i]==D1[j]&&fr[i]<fr[j];}
bool cmp2(int i,int j){return D2[i]<D2[j]||D2[i]==D2[j]&&fr[i]<fr[j];}
void solve(int root){
int head=0,tail=1,x=Q[0]=root,g=0;fa[x]=-1;siz[x]=1;
for(;head<tail;x=Q[++head])
Fe fa[Q[tail++]=e->to]=x,siz[e->to]=1;
while(head--){
if(fa[x=Q[head]]!=-1)siz[fa[x]]+=siz[x];
bool isg=tail-siz[x]<=tail/2;
Fe if(siz[e->to]>tail/2)isg=0;
if(isg){g=x;break;}
}
vis[g]=1;
head=0,tail=1,Q[0]=L[0]=x=g,fa[x]=-1,dep[x]=fr[x]=D1[x]=D2[x]=0;
int ccnt=0,len=0;
for(;head<tail;x=Q[++head],L[head]=x)Fe{
fa[Q[tail++]=e->to]=x;fr[e->to]=x==g?++ccnt:fr[x];dep[e->to]=dep[x]+1;
D1[e->to]=(D1[x]+pow1[dep[x]]*e->w)%M;
D2[e->to]=(D2[x]+pow2[dep[e->to]]*e->w)%M;
}
std::sort(Q,Q+tail,cmp2);
std::sort(L,L+tail,cmp1);
int l0=0,r0=0,l1=0,r1=0;
for(int i=0;i<tail;i++){
while(l0<tail&&D2[Q[l0]]<D1[L[i]])l0++;
while(r0<tail&&D2[Q[r0]]<=D1[L[i]])r0++;
while(l1<tail&&(D2[Q[l1]]<D1[L[i]]||D2[Q[l1]]==D1[L[i]]&&fr[Q[l1]]<fr[L[i]]))l1++;
while(r1<tail&&(D2[Q[r1]]<D1[L[i]]||D2[Q[r1]]==D1[L[i]]&&fr[Q[r1]]<=fr[L[i]]))r1++;
ans+=r0-l0-r1+l1;
}
for(edge*e=first[g];e;e=e->next)
if(!vis[e->to])solve(e->to);
}
int main(){
scanf("%d%d",&n,&M);
for(int i=1,u,v,w;i<n;i++){
scanf("%d%d%d",&u,&v,&w);
link(u,v,w);link(v,u,w);
}
long long I=inv(10,M);
*pow1=1%M;*pow2=(M-1)%M;
for(int i=*pow1=1;i<=n;i++){
pow1[i]=pow1[i-1]*10%M;
pow2[i]=pow2[i-1]*I%M;
}
solve(0);
std::cout<<ans<<'\n';
}8、LYDSY 3451
给定无根树 $T$，记 $T$ 的节点数 $n=|V(T)|$，初始时 $S=0$，然后进行如下的分治过程：
- $S\leftarrow S+|T|$
- 若 $|T|=1$，结束
- 等概率随机选取 $T$ 的一个节点 $v\in V(T)$，从 $T$ 中删去 $v$ 及与 $v$ 关联的边，把 $T$ 分成若干个更小的树 $T_1,T_2,...,T_k$
- 对每个 $T_i(i=1,2,...,k)$ 递归处理该过程
求分治过程结束之后，$S$ 的值的期望值 $E(S)$。$n\le 30,000$。
http://www.lydsy.com/JudgeOnline/problem.php?id=3451
首先说一下，这题的解法是树分治。
用树分治求树分治的期望复杂度？
这是一道很神的题。
首先，联想一下普通的点分治为什么每层分治的复杂度是 $O(|T|)$ 的，因为通常需要遍历一遍整个树 $T$。所以我们可以修改一下分治过程：对每个点 $v$ 记录 $v$ 被经过的次数 $S(v)$，然后把 $S\leftarrow S+|T|$ 这一步改成对于每个 $v\in V(T)$，修改 $S(v)\leftarrow S(v)+1$（一个点被删去后 $S(v)$ 的值就确定下来了）。那么 $S=\sum_{v\in V(T)}S(v)$，因此
$$E(S)=E(\sum_{v\in V(T)}S(v))=\sum_{v\in V(T)}E(S(v))$$
因此只需对每个点 $v$ 考虑 $E(S(v))$。问题已经简单了一些，不过 $E(S(v))$ 该怎么求？
继续分析。考虑 $v$ 在递归过程中递归了几层（以下记 $u$ 为这一层递归选取删除的点）：
（1）如果 $u=v$，那么 $v$ 被删去，结束；
（2）如果 $u\ne v$，将 $T$ 以 $v$ 为根转成有根树，删去 $u$ 为根的子树即可（剩下部分就是删去 $u$ 后 $v$ 所在的连通块，删除部分不再考虑），递归处理。
因此 $S(v)$ 的值其实是这样的：以 $v$ 为根，一开始 $S(v)=0$，然后重复以下过程：
- 令 $S(v)\leftarrow S(v)+1$
- 等概率随机选取 $u\in V(T)$，从 $T$ 中删去以 $u$ 为根的子树
- 如果 $T$ 为空，结束
$S(v)$ 就是这个过程的期望步数，但我们还是不知道它是多少。
这里我的处理方法是这样的：记 $U$ 为该过程中所有被第2步选为 $u$ 的节点集合，那么 $S(v)=|U|$，因此
$$E(S(v))=E(|U|)=E(\sum_{u\in V(T)}[u\in U])=\sum_{u\in V(T)}P(u\in U)$$
问题更加简单了，只需求每个点出现在 $U$ 中的概率。设以 $v$ 为根时 $u$ 的祖先个数为 $d_{v,u}$（假设一个点的祖先包含其本身，因此就是 $u,v$ 路径上的节点数），在删的过程中，每一步删除的点或者不是 $u$ 的祖先，这时候 $u$ 的祖先集合不变，或者删的点是 $u$ 的祖先，因选取是等概率的，有 $\frac{1}{d_{v,u}}$ 的概率删去 $u$，此时必有 $u\in U$，还有 $1-\frac{1}{d_{v,u}}$ 的概率删去除 $u$ 外 $u$ 的祖先，此时 $u$ 作为子树内节点被删除，必有 $u\not\in U$。由于最终至少有一个 $u$ 的祖先被删去（起码根 $v$ 会被删去），而 $u$ 的任何一个祖先被删除 $[u\in U]$ 就确定了，所以 $P(u\in U)=\frac{1}{d_{v,u}}$。
这样结论就出来了：
$$E(S)=\sum_{v\in V(T)}E(S(v))=\sum_{v\in V(T)}\sum_{u\in V(T)}P(u\in U)=\sum_{v\in V(T)}\sum_{u\in V(T)}\frac{1}{d_{v,u}}$$
你可能会说，到这里我们都只是在用树分治的性质啊，并没有真正写树分治啊！慢着——你有没发现直接用上面的式子计算起码是 $O(n^2)$ 的？怎么优化？
这个问题是“求树的所有路径的经过节点数的倒数和”，其实是一个树路径统计问题，有一种经典的做法——树分治。
由于我们只要对每个 $l=0,1,...,n-1$ 求出距离为 $l$ 的有对数 $\mathrm{cnt}_l$ 就能得到答案 $\sum_{l=0}^l\frac{\mathrm{cnt}_l}{l+1}$，所以接着讨论如何计算所有 $\mathrm{cnt}_l$。考虑点分治，找出树的重心 $g$ 后，把有向路径分成两类：不过点 $g$ 的路径、过点 $g$ 的路径。对于前者可以递归处理，因此只讨论后者。先预处理出 $f_T(i)$ 为树 $T$ 中距离 $g$ 为 $i$（这里的距离定义为经过的边数）的节点数，$f_{T_c}(i)$ 为 $T$ 的子树 $c$（删去 $g$ 之后，一个连通块就是一个子树）中和 $T$ 重心 $g$ 距离为 $i$ 的节点数，则过点 $g$ 且长度为 $l$ 的有向路径数为（证明略）：
$$\sum_{a=0}^lf_T(a)f_T(l-a)-\sum_{c}\sum_{a=0}^lf_{T_c}(a)f_{T_c}(l-a)$$
注意到对每个 $l$ 计算 $\sum_{a=0}^lf_T(a)f_T(l-a)$ 是一个卷积的形式，可以用 FFT 优化到 $O(|T|\log |T|)$。这样就能在总共 $O(n\log^2 n)$ 的时间内对每个 $l$ 求出全树中长度为 $l$ 的有向路径数。这个做法比较慢，如果有更优秀的解法欢迎讨论。代码如下：
#include<cstdio>
#include<cstring>
#define ll long long
#define MOD 998244353
#define Fe(x) for(edge*e=first[x];e;e=e->next)if(!vis[e->to]&&e->to!=fa[x])
ll w[1<<16];
ll pow(ll a,int n=MOD-2){ll b=1;for(;n;n>>=1)n%2?b=b*a%MOD:1,a=a*a%MOD;return b;}
void DFT(int*a,int n,bool ty=0){
w[*w=1]=pow(3,(MOD-1)/n);
if(ty)w[1]=pow(w[1]);
for(int i=2;i<n;i++)w[i]=w[i-1]*w[1]%MOD;
for(int i=0,j=0,t;i<n;i++){
if(i<j)t=a[i],a[i]=a[j],a[j]=t;
for(t=n>>1;(j^=t)<t;t>>=1);
}
for(int i=1,m=1;m<n;i++,m<<=1)
for(int j=0;j<n;j+=1<<i)
for(int k=0,t;k<m;k++){
t=a[j+m+k]*w[(n>>i)*k]%MOD;
a[j+m+k]=(a[j+k]+MOD-t)%MOD;
a[j+k]=(a[j+k]+t)%MOD;
}
if(ty){
ll I=pow(n);
for(int i=0;i<n;i++)a[i]=a[i]*I%MOD;
}
}
struct edge{int to;edge*next;}E[60010],*ne=E,*first[30010];
int Q[30010],fa[30010],s[30010],A[30010],ans[1<<16];
bool vis[30010];
void link(int a,int b){*ne=(edge){b,first[a]};first[a]=ne++;}
void calc(int*h,int*t,int n,int k){
int N=1;while(N<=n<<1)N<<=1;
memset(A,0,N<<2);
for(int*i=h;i<t;i++)A[s[*i]]++;
DFT(A,N);
for(int i=0;i<N;i++)A[i]=1ll*A[i]*A[i]%MOD;
DFT(A,N,1);
for(int i=0;i<N;i++)ans[i]+=k*A[i];
}
void solve(int g){
int*h=Q,*t=Q+1;
for(g=fa[*h=g]=-1;h<t;s[*(h++)]=1)
Fe(*h)fa[*(t++)=e->to]=*h;
while(g<0){
bool f=t-Q-s[*(--h)]<=t-Q>>1;
Fe(*h)s[e->to]>t-Q>>1?f=0:1;
f?g=*h:1;
fa[*h]>-1?s[fa[*h]]+=s[*h]:1;
}
vis[*Q=g]=1;fa[g]=-1;s[g]=0;h=t=Q+1;
int n=0,m,*q;
Fe(g){
for(s[*(q=t++)=e->to]=1,fa[e->to]=g;h<t;h++)
Fe(*h)fa[*(t++)=e->to]=*h,s[e->to]=s[*h]+1;
calc(q,t,(m=s[t[-1]])>n?n=m:m,-1);
}
calc(Q,t,n,1);
Fe(g)solve(e->to);
}
int main(){
int n;scanf("%d",&n);
for(int i=1,a,b;i<n;i++)scanf("%d%d",&a,&b),link(a,b),link(b,a);
solve(0);
long double s=0;
for(int i=0;i<n;i++)s+=ans[i]/(i+1.0L);
printf("%.4lf",(double)s);
}9、UOJ #59
给定一个 $n$ 元一次同余方程组
$$\begin{cases} a_{0,0}x_0+a_{0,1}x_1+...+a_{0,n-1}x_{n-1}\equiv c_0\pmod b_0 \\ a_{1,0}x_0+a_{1,1}x_1+...+a_{1,n-1}x_{n-1}\equiv c_1\pmod b_1 \\ ... \\ a_{m-1,0}x_0+a_{m-1,1}x_1+...+a_{m-1,n-1}x_{n-1}\equiv c_{m-1}\pmod b_{m-1}\end{cases}$$
求一组解 $(x_1,x_2,...,x_n)$ 满足尽量多的方程。提交答案题，详细数据及评分方式见链接。
WC滚粗前最后刷的一道题。
既然是提交答案题，我们就需要先观察各个测试点的特征。
测试点1
该测试点满足 $n=1,m=5000$，所有 $b_i=1058400$。
做法很简单，由于只有一个变量 $x_1$，不妨记为 $x$，注意到如果 $a_ix\equiv c_i\pmod b_i$，那么 $a_i(x\bmod b_i)\equiv c_i\pmod b_i$，因此只需在 $\{0,1,...,1058400-1\}$ 中枚举 $x$，然后判断一下能满足多少个方程。
这样时间效率为 $1058400\times 5000$，可以跑出测试点1。事实上可以直接解每一个同余方程进一步优化时间效率。
测试点2
该测试点满足 $n=1,m=50$，所有 $b_i$ 为不超过 $2^31$ 的正整数。
这时候最优的 $x$ 可能很大，不能再直接枚举。
通过写程序验证，我们发现有 $13$ 个方程的 $\gcd(a_i,b_i)\not|c_i$，不可能被满足，因此把这些方程删掉。对于剩下的方程，可以将 $a_i,b_i,c_i$ 同时除以 $\gcd(a_i,b_i)$，然后将 $c_i$ 乘上 $a_i$ 在模 $b_i$ 意义下的逆元，在令 $a_i=1$，就能把方程化为 $x\equiv c_i\pmod b_i$ 的形式。
进一步通过程序验证发现，删掉这些方程之后，剩下的 $b_i$ 两两互质，因此一定存在一组 $x_i$ 同时满足这 $37$ 个方程。
可以使用中国剩余定理构造满足所有同余方程 $x\equiv c_i\pmod b_i(0\le i < m)$ 的一个合法解：记 $P_i=\prod_{0\le j < m,j\ne i}b_j$，即除 $b_i$ 外所有 $b_j$ 的乘积；构造 $m$ 个数 $x_0,x_1,...,x_{m-1}$，其中 $x_i=P_i\cdot(P_i^{-1}\bmod b_i)\cdot c_i$，这里 $a^{-1}\bmod b$ 表示 $a$ 在模 $b$ 下的逆元，那么
$$\begin{cases}x_i\equiv 0\pmod b_j,&i\ne j\\x_i\equiv c_j\pmod b_j,&i=j\end{cases}$$
因此 $x=\sum_{i=0}^{m-1}x_i$ 就是一个合法解。由于 $x$ 可能很大，超过 int 甚至 long long 范围，需要使用高精度。
测试点3
该测试点满足 $n=m=300$，所有 $b_i=1000000007$。
不难发现，这就相当于在模 $1000000007$ 意义下解 $n$ 元一次线性方程组，因为 $1000000007$ 是质数，所以所有模意义下非 $0$ 数都有逆元，因此可以直接高斯消元解决。
实测证明，该方程组在模 $1000000007$ 意义下有唯一解。这样就在 $300^3$ 的时间内高效地解决了该测试点。
测试点4
该测试点满足 $n=20,m=845$，所有 $b_i=1000000007$。
通过观察测试点，还能发现，前 $800$ 个方程以每 $40$ 个为一组，每组内的方程系数 $a_{i,j}$ 完全相同，常数项 $c_i$ 只有两种取值，每种出现 $20$ 次，并且这 $20$ 个组的方程的系数构成一个上三角矩阵；除了这 $20$ 组方程以外还有 $45$ 个方程。
容易发现，每组方程或者满足一半（$20$ 个）或者都不满足（$0$ 个），如果都满足一半，就能满足 $400$ 个方程；如果有 $3$ 组没有满足，那么最多满足 $340+45 < 400$ 个方程，因此最多有 $2$ 组不被满足，剩下的只要 $2^{20}$ 枚举每组方程满足哪一半即可，时间效率约为 $C_20^2\times 2^{18}\times 20\times 845$，需要很长时间才能得到答案。
事实上最优解满足每组方程都满足一半（因此下面的代码是面向数据的），本人并不知道是否有更好的方法判断这个条件成立。如果只枚举这种情况，那么时间效率约为 $2^{20}\times 20\times 845$。
测试点5
该测试点满足 $n=m=100$，所有 $b_i=223092870$。
看起来和测试点3差不多，但实际上是有区别的，$b_i$ 不是质数，所以消元时可能出现没有逆元而消不掉的情况。
去年在做这个点的时候不会处理，直接消元结果挂了，于是通过一些随机打乱调整消元顺序的方法强行消出解，过掉了，然而这个做法不靠谱就是了。
靠谱的做法是这样的：因为
$$223092870=2\times 3\times 5\times 7\times 11\times 13\times 17\times 19\times 23$$
所以由 $x\bmod 223092870=c$ 可以得到 $x\bmod 2=c\bmod 2$，$x\bmod 3=c\bmod 3$，…，$x\bmod 23=c\bmod 23$。同时利用中国剩余定理，由这 $9$ 个方程可以合并得到 $x\bmod 223092870=c$，也就是说把每个方程拆成模数为 $p_0=2,p_1=3,p_2=5,...,p_8=23$ 的 $9$ 个方程以后，方程组是等价的。
因此，把 $m$ 个方程拆成 $9m$ 个方程以后，枚举 $i=0,1,...,8$，取出所有模数是 $p_i$ 的方程，然后调用测试点3的程序求出一组解 $x_{i,0},x_{i,1},...,x_{i,n-1}$。最后对于每个 $j=0,1,...,n-1$，用测试点2用到的中国剩余定理合并所有的 $x_{i,j}(0\le i < 9)$ 得到 $x_j$。因为模数在 int 范围内，所以可以直接在模 $223092870$ 下计算，不需要高精度。
写个程序就能发现对于每个 $i$，都存在一组满足所有方程的解，因此合并之后的 $x_0,x_1,...,x_{n-1}$ 也能满足所有方程。这样的运行效率约为 $100^3\times 9$。
测试点6
该测试点满足 $n=m=50$，所有的 $b_i$ 为不超过 $2^31$ 的正整数。
有了之前的经验，把模数 $b_i$ 质因数分解，可以发现所有的 $b_i$ 分解之后都是若干个不超过 $200$ 的质数的乘积。
同样地，对于一个方程 $i$，分解 $b_i=p_0p_1...p_{k-1}$，其中 $p_j(j=0,1,...,k-1)$ 是质数，那么就可以对每个 $j=0,1,...,k-1$，把方程 $i$ 模 $p_j$（即所有系数 $a_{i,j}$ 和常数项 $c_i$ 同时模 $p_j$，模数为 $p_j$）得到 $k$ 个方程，显然拆完之后是等价的。
接着做法和测试点5是差不多的：对于每个 $200$ 以内的质数 $p$，把所有模数为 $p$ 的方程取出来求出模 $p$ 意义下的一组解，和测试点5一样，数据满足所有方程都能被满足，最后用中国剩余定理合并。
值得注意的是这里需要高精度，因为 $200$ 以内的质数乘积很大。
测试点7
该测试点满足 $n=50,m=200$，所有 $b_i=176400$。
同时观察发现这个测试点和测试点4很像——有大量重复的方程出现。这里，前 $50$ 个方程是完全相同的，后 $150$ 个方程中，对于每个 $j=0,1,...,n-1$ 有一组 $3$ 个方程 $i$ 满足 $a_{i,j}=1,\forall k\ne j,a_{i,k}=0$，并且这一组 $3$ 个方程的 $c_i$ 互不相同。
这种性质的测试点再一次启发我们求理论上界：最优情况下，前面 $50$ 个方程同时满足，后面的 $50$ 组方程每组都满足 $1$ 个，最多可以满足 $100$ 个。如果答案是 $100$ 个的话，显然每个 $x_j$ 要从 $j$ 这一组 $3$ 个方程中取一个 $c_i$ 作为 $x_j$，同时必须满足前面的 $50$ 个方程。
暴搜需要枚举 $3^{50}$ 种情况，不可能跑出来。注意到一个性质：模数 $176400$ 比较小，可以直接DP，比如可以这么做：记 $f(i,j)$ 为能否取前 $i$ 个 $x$ 的值使得 $a_{0,0}x_0+a_{0,1}x_1+...+a_{0,i-1}x_{i-1}\equiv j\pmod 176400$，用 $x_{i,0},x_{i,1},x_{i,2}$ 表示 $x_i$ 的三种可能取值，则
$$f(i,j)=\begin{cases}[j=0],&i=0\\f(i-1,(j-x_{i-1,0})\bmod 176400)\lor f(i-1,(j-x_{i-1,1})\bmod 176400)\lor f(i-1,(j-x_{i-1,2}),&i>0\bmod 176400)\end{cases}$$
当然也可以倒着定义，等等。根据DP推出的结果也就能得到方案。时间效率 $50\times 176400\times 3$。
测试点8
该测试点满足 $n=m=50$，所有的 $b_i$ 为不超过 $2^31$ 的正整数。
乍一看和测试点6做法一样，然而还是有些区别的，因为联立方程组以后高斯消元发现无解了。
不过，导致无解的方程很少，可以从 $m$ 开始倒着枚举答案 $a=m,m-1,m-2,...$，再枚举这 $m$ 个方程中大小为 $m-a$ 的子集，把这 $m-a$ 个方程删掉以后调用测试点6的程序。实验表明这个测试点的答案是 $49$，所以只要调不超过 $50$ 次测试点6的程序就能解决了。
测试点9
该测试点满足 $n=1,m=100$，所有 $a_i=1,b_i=19337$。
这个点最简单，和测试点1一样枚举就好了，时间效率 $100\times 19337$。更简单的做法是统计出现次数最多的 $c_i$ 就是答案，时间效率可以做到 $19337$ 或者 $100\times\log_2 100$。
测试点10
该测试点满足 $n=50,m=90$，所有的 $b_i$ 为不超过 $2^31$ 的正整数。
最难通过的一个测试点。
虽然 $b_i$ 还是可以像测试点6或者8那样分解，质因数不超过 $1000$，但是这个方程组不能同时满足，并且倒着枚举答案并不能枚举出来。
这个问题相当于从 $m$ 个方程中取出尽量多个方程，使得它们能被同时满足。如果直接枚举的话复杂度是 $O(2^m)$，不可能枚举出来。
用一些随机化乱搞可以得到很高的分数。我一开始使用的方法是：把 $m$ 个方程随机打乱，一开始 $S=\varnothing$，然后贪心地逐个方程加入集合 $S$，如果加入后 $S$ 不能满足，就不加入，多次随机取最优解。这样可以很容易地求出 $33$ 的答案，能得到9分。
之后，为了得到最后的1分，我花了一个晚上时间。
想过一种优化，构造无向图 $G=(V,E)$，其中 $V=\{0,1,...,m-1\}$，$(i,j)\in E$ 当且仅当方程 $i$ 和方程 $j$ 不能被同时满足。这样如果 $S$ 是一个合法解，那么 $S$ 必然是 $G$ 的一个独立集。
接着我把图 $G$ 构出来，结果写了个程序发现怎么 $E=\varnothing$？怀疑了一会儿感觉没什么救，就去看了题解，发现题解也是构了这个图，那一定是我写错了。然后就发现有个地方 for(int j=0;j<m;j++) 的 m 打成了 2。哎我这么这么菜。然后开始搜 $G$ 的独立集，每次枚举剩下的图中度数最大的点选不选，很快搜到了 $32$ 左右的解，这时输出答案结果过不了 checker，又怀疑了一会儿人生，最后手算了一下发现我不仅图又构错了，搜索还打错了= =b
问题在于回溯的时候撤销的顺序错了。改完以后搜出了 $32$，是对的，但是搜不动了。于是加了个优化：如果最大度数不超过 $2$，那么贪心地选度数最小的点。又搜了一段时间搜出了 $34$。
验证了一下这个 $34$ 的解发现是对的，于是就通过了。之后我继续搜，并没有搜出大于 $34$ 的解，因此这应该就是最优的了。不过这里我用的是猜想结合验证的方法，我不知道如何证明或证否 $G$ 的一个独立集必定是一组合法解。即：如果一个 $n$ 元一次同余方程组的任意两个方程都能同时被满足，那么这个方程组能被满足，这个性质我不会证明或证否。如果大家有什么好的思路欢迎提出。
代码如下，由于包含了10个点，代码巨长无比，大概 $6\texttt{KB}$：
#include <cstdio>
#include <cstring>
#define OP(i) freopen("sports"i".in","r",stdin);freopen("sports"i".out","w",stdout);fprintf(stderr,"Task "i"\n");read();
#define CP(i,j,k) memcpy(i,j,sizeof(k))
#define ll long long
#define BASE 1000000000
void swp(int&a,int&b){int t=a;a=b;b=t;}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
ll inv(int a,int p){return a==1?1:(1+p*(a-inv(p%a,a)))/a%p;}
struct bigint{
int a[1010],l;
bigint(int x=0){
*a=x%BASE;a[l=1]=0;x/=BASE;
for(;x;a[++l]=0)a[l]=x%BASE,x/=BASE;
}
void fix(){while(l>1&&!a[l-1])l--;}
bigint operator+(bigint b){
bigint r;int c=0;memset(r.a,0,(r.l=(l>b.l?l:b.l)+1)*4);
for(int i=0;i<r.l;i++)r.a[i]=(c+=(i<l?a[i]:0)+(i<b.l?b.a[i]:0))%BASE,c/=BASE;
r.fix();return r;
}
bigint operator*(bigint b){
bigint r;ll c;memset(r.a,0,(r.l=l+b.l)*4);
for(int i=0;i<l;i++)
for(int j=c=0;j<=b.l;j++)r.a[i+j]=(c+=r.a[i+j]+1ll*a[i]*b.a[j])%BASE,c/=BASE;
r.fix();return r;
}
int operator%(int b){
ll c=0;for(int i=l;i--;)c=(c*BASE+a[i])%b;
return c;
}
void print(){
printf("%d",a[l-1]);
for(int i=l-1;i--;)printf("%09d",a[i]);puts("");
}
};
int n,m,a[5010][310],b[5010],c[5010],x[5010];
void read(){
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++){
for(int j=0;j<n;j++)scanf("%d",a[i]+j);
scanf("%d%d",b+i,c+i);
}
}
void print(){
for(int i=0;i<n;i++)printf("%d\n",x[i]);
}
int check(){
int cnt=0;
for(int i=m,s;i--;){
for(int j=s=0;j<n;j++)s=(s+1ll*a[i][j]*x[j])%b[i];
if(s==c[i])cnt++;
}
return cnt;
}
bool eli(){
int p=*b,r=0,i=0,j,k;
for(;i<n;i++){
for(j=r;j<m&&!a[j][i];j++);
if(j==m)continue;
for(k=i;k<n;k++)swp(a[j][k],a[r][k]);swp(c[j],c[r]);
for(j=r+1;j<m;j++){
ll t=(p-a[j][i])*inv(a[r][i],p)%p;
for(k=i;k<n;k++)a[j][k]=(a[j][k]+a[r][k]*t)%p;
c[j]=(c[j]+c[r]*t)%p;
}
r++;
}
for(i=r;i<m;i++)if(c[i])return 0;
for(i=r;i--;){
for(k=0;!a[i][k];k++);x[k]=c[i];
for(int j=n;--j>k;)x[k]=(x[k]+(p-a[i][j])*1ll*x[j])%p;
x[k]=x[k]*inv(a[i][k],p)%p;
}
return 1;
}
void task1(){
int cnt,max=0,maxx;
for(*x=0;*x<*b;++*x)(cnt=check())>max?max=cnt,maxx=*x:1;
*x=maxx;print();
}
void task2(){
int A[50],B[50],cnt=0;
for(int i=0;i<m;i++)if(c[i]%gcd(*a[i],b[i])==0){
int g=gcd(*a[i],b[i]);
A[cnt]=c[i]/g*inv(*a[i]/g,b[i])%b[i];
B[cnt++]=b[i];
}
bigint ans=0,P;
for(int i=cnt;i--;){
P=1;for(int j=cnt;j--;)if(j!=i)P=P*B[j];
ans=ans+P*inv(P%B[i],B[i])*A[i];
}
ans.print();
}
void task3(){
eli();print();
}
void task4(){
int p=*b,B=40,cnt,max=0,xs[20];
for(int S=1<<n;S--;){
for(int i=n,l;i--;){
x[i]=c[l=i*B+(S>>i&1)];
for(int j=n;--j>i;)x[i]=(x[i]+(p-a[l][j])*1ll*x[j])%p;
x[i]=x[i]*inv(a[l][i],p)%p;
}
if((cnt=check())>max?max=cnt:0)CP(xs,x,xs);
}
CP(x,xs,xs);print();
}
void task5(){
int p=*b,q=p,pr[20],cnt=0,A[100][310],B[100],tx[20][100];
for(int i=2;1ll*i*i<=q;i++)q%i?1:q/=(pr[cnt++]=i);
q>1?pr[cnt++]=q:1;
CP(A,a,A);CP(B,c,B);
for(int t=cnt;t--;){
for(int i=m;i--;c[i]=B[i]%pr[t])
for(int j=n;j--;)a[i][j]=A[i][j]%pr[t];
*b=pr[t];eli();memcpy(tx[t],x,n*4);
}
for(int i=n,s;i--;x[i]=s)
for(int t=s=0;t<cnt;t++)s=(s+p/pr[t]*inv(p/pr[t]%pr[t],pr[t])%p*tx[t][i])%p;
print();
}
bool task6(bool op=1){
bool vis[1010]={0};
int M=m,pr[1010],cnt=0,A[90][310],B[90],C[90],tx[1010][90];
for(int i=0;i<m;i++){
int q=b[i];
for(int j=2;1ll*j*j<=q;j++)
if(q%j==0)q/=j,vis[j]=1;
if(q>1)vis[q]=1;
}
for(int i=0;i<1000;i++)if(vis[i])pr[cnt++]=i;
CP(A,a,A);CP(B,b,B);CP(C,c,C);
for(int t=cnt;t--;){
for(int i=m=0;i<M;i++)if(B[i]%pr[t]==0){
for(int j=n;j--;)a[m][j]=A[i][j]%pr[t];
c[m++]=C[i]%pr[t];
}
*b=pr[t];if(!eli())return!(CP(a,A,A),CP(b,B,B),CP(c,C,C),m=M);memcpy(tx[t],x,n*4);
}
if(op)for(int i=0;i<n;i++){
bigint S=0;
for(int t=0;t<cnt;t++){
bigint P=1;
for(int j=0;j<cnt;j++)if(j!=t)P=P*pr[j];
S=S+P*inv(P%pr[t],pr[t])*tx[t][i];
}
S.print();
}
CP(a,A,A);CP(b,B,B);CP(c,C,C);return m=M;
}
void task7(){
int p=*b;
static bool f[55][176400];
f[n][*c]=1;
for(int i=n;i--;)
for(int j=0;j<p;j++)
for(int k=0;k<3;k++)f[i][j]|=f[i+1][(j+c[n+3*i+k]*1ll*a[0][i])%p];
for(int i=0,j=0,t;i<n;i++)
for(int k=0;k<3;k++)if(f[i+1][t=(j+c[n+3*i+k]*1ll*a[0][i])%p]){x[i]=c[n+3*i+k];j=t;break;}
print();
}
void task8(){
for(int i=--m;i>=0;i--){
for(int j=0;j<n;j++)swp(a[i][j],a[m][j]);swp(b[i],b[m]);swp(c[i],c[m]);
if(task6())return;
}
}
void task9(){task1();}
struct Graph{
bool G[90][90];int vis[90],S[90],ans,ansS[90];
void make(){
int M=m;m=2;ans=0;
for(int i=0;i<M;G[i][i]=vis[i]=S[i]=0,i++){
for(int j=i+1;j<M;j++){
for(int k=0;k<n;k++)swp(a[i][k],a[0][k]),swp(a[j][k],a[1][k]);
swp(b[i],b[0]);swp(c[i],c[0]);swp(b[j],b[1]);swp(c[j],c[1]);
G[i][j]=G[j][i]=!task6(0);
swp(b[j],b[1]);swp(c[j],c[1]);swp(b[i],b[0]);swp(c[i],c[0]);
for(int k=0;k<n;k++)swp(a[j][k],a[1][k]),swp(a[i][k],a[0][k]);
}
}
m=M;
}
void dfs(int dep,int rest){
if(dep>ans)ans=dep,CP(ansS,S,S);
int e=dep+rest;
if(e<=ans)return;
int maxd=-1,maxi=-1,mind=1<<30,mini;
for(int i=m,d;i--;)if(!vis[i]){
for(int j=d=0;j<m;j++)d+=!vis[j]&&G[i][j];
if(d>maxd)maxd=d,maxi=i;
if(d<mind)mind=d,mini=i;
}
if(maxi>-1){
if(maxd<=2)maxi=mini;
vis[maxi]++?1:rest--;
for(int j=0;j<m;j++)if(G[maxi][j])vis[j]++?1:rest--;
S[maxi]=1;dfs(dep+1,rest);
for(int j=0;j<m;j++)if(G[maxi][j])--vis[j]?1:rest++;
if(maxd<=2||e<=ans){S[maxi]=0;vis[maxi]--;return;}
S[maxi]=0;dfs(dep,rest);vis[maxi]--;
}
}
}graph;
void task10(){
graph.make();graph.dfs(0,m);
int M=m;m=0;
for(int i=0;i<M;i++)if(graph.ansS[i]){
for(int j=0;j<n;j++)swp(a[i][j],a[m][j]);swp(b[i],b[m]);swp(c[i],c[m++]);
}
task6();
}
int main(){
OP("1");task1();
OP("2");task2();
OP("3");task3();
OP("4");task4();
OP("5");task5();
OP("6");task6();
OP("7");task7();
OP("8");task8();
OP("9");task9();
OP("10");task10();
}后话
WC前刷了这么多题，也改变不了我是个无实力的暴力选手的事实。
最后，WC交了几个暴力上去，提交答案题也完全切不动，就这么跪了。
实力的提升，并不是靠做几道题就能积累起来的。
鄂公网安备 42010202000505 号