UOJ Logo WrongAnswer的博客

博客

WC前的刷题记录

2017-02-03 20:53:53 By WrongAnswer

就要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$ 个点共线。详细题意及数据规模见题目链接。

http://uoj.ac/problem/54

这题是我去年就思考过的一个问题。$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)$ 满足尽量多的方程。提交答案题,详细数据及评分方式见链接。

http://uoj.ac/problem/59

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交了几个暴力上去,提交答案题也完全切不动,就这么跪了。

实力的提升,并不是靠做几道题就能积累起来的。

返回顶部

评论

150137
Orz Wa爷爷好大啊 第一题其实是一道经典题目,我没记错的话在 51nod 上有一个专题叫序列求和,他应该是 V3

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。