~~从十二月份咕到三月份，然后再从第二周咕到第四周的~~校赛终于开始啦。

虽然是网络预赛，不过题目还是相当有意思的。

C 小张的魔法跳越

$n (\leq 10^{5})$ 个节点的树中，每条边有 unsigned int 的权值 $w$ ，令点对 $(i, j)$ 的最短路径权和为 $S (i, j)$ ，最短路径上所有边权异或和为 $X (i, j)$ ，求 $\sum_{i < j} S (i, j) \times K (i, j) (\mod 10^{9} + 7)$ 。

题解

对边权的每一位单独考虑，则就变成求每一位上异或和为 1 的点对之间的边权和。

类似树上背包的思想，令 $f (u, 0)$ 和 $f (u, 1)$ 表示对节点 $u$ 当前已经合并的子树中，路径异或和为 0 和 1 的路径的边权之和。更新时，只要用已经处理过的子树，和准备要加入的子树 $v$ 的 $f (v, 0)$ 和 $f (v, 1)$ 更新答案，再将 $f (v, 0)$ 和 $f (v, 1)$ 合并到 $f (u, 0)$ 和 $f (u, 1)$ 中即可。

总时间复杂度 $O (n)$ 。

代码

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;

const int N=100000+5;
const int MOD=1000000007;

typedef unsigned int ui;
typedef long long ll;

struct Adj{int v; ui w;};
vector<Adj> a[N];

int ans=0;
int f[N][2],cnt[N][2];		//节点i异或和为x时的边权和与数量

inline bool Judge(ui w,ui p){
    return (w&p)>0;
}

void DFS(int u,int pa,ui p){
    cnt[u][0]=1;
    cnt[u][1]=f[u][0]=f[u][1]=0;

    for(int i=0;i<a[u].size();i++){
        int v=a[u][i].v;
        ui w=a[u][i].w;
        
        if(v==pa)continue;
        DFS(v,u,p);
        int b=Judge(w,p);

        int f1 = (f[v][1^b] + (ll)w*cnt[v][1^b]) %MOD;
        int f2 = (f[v][0^b] + (ll)w*cnt[v][0^b]) %MOD;

        //0 1
        ans=( ans + (ll)f[u][0] * cnt[v][1^b] %MOD * p )%MOD;
        ans=( ans + (ll)f1 * cnt[u][0] %MOD * p )%MOD;
        
        //1 0
        ans=( ans + (ll)f[u][1] * cnt[v][0^b] %MOD * p )%MOD;
        ans=( ans + (ll)f2 * cnt[u][1] %MOD * p )%MOD;

        cnt[u][0]=(cnt[u][0]+cnt[v][0^b])%MOD;
        cnt[u][1]=(cnt[u][1]+cnt[v][1^b])%MOD;
        f[u][0]=(f[u][0]+f2)%MOD;
        f[u][1]=(f[u][1]+f1)%MOD;
    }
}

int main(){
    int nCase; scanf("%d",&nCase);
    
    while(nCase--){
        int n; scanf("%d",&n);	
        for(int i=1;i<=n;i++)
            a[i].clear();
        
        for(int i=1;i<n;i++){
            int u,v; ui w;
            scanf("%d%d%ud",&u,&v,&w);
            a[u].push_back((Adj){v,w});
            a[v].push_back((Adj){u,w});
        }

        ans=0;
        for(int i=0;i<32;i++)
            DFS(1,0,((ui)1)<<i);

        printf("%d\n",ans);
    }

    return 0;
}

E 禁忌的共鸣

有 $n (\leq 10^{5})$ 个数 $a_{i} (\leq 10^{5})$ ，任意两个数 $(i, j)$ 之间有一条 $(a_{i}, a_{j})$ 的边，求这个图的最大生成树。

题解

显然不能直接搞图出来然后跑 Kruskal。考虑 Kruskal 的贪心原则，从大到小枚举约数，然后将含有这个约数的点全部加入并查集即可。

很诡异的时间复杂度。据说约数个数是 $\sqrt{n} / \ln n$ 级别的，所以我提前处理好每个约数对应的 $a_{i}$ 的时间复杂度理论上是 $O (n^{3 / 2} / \ln n)$ 级别的。

跟 Potassium（点我跳转）讨论了一下，他是先枚举了约数 $p$ ，然后判断是否存在 $i \times p = a_{i}$ 。这样的话复杂度是有保证的 $\sum_{i = 1}^{n} n / i = O (n \log n)$ 级别。

~~果然还是不能什么都用 vector~~

代码

#include<iostream>
#include<ctime>
#include<vector>
using namespace std;

typedef long long ll;

const int N=100000+5;
vector<int> fac[N];		//maxsize: 128
vector<int> edg[N];		//含有同一因子的边
int n;

void FindFac(){
    for(int i=1;i<N;i++)
        for(int j=i;j<N;j+=i)
            fac[j].push_back(i);
}

int pa[N];

int FindPa(int x){
    return pa[x]==x?x:pa[x]=FindPa(pa[x]);
}

ll Kruskal(){
    ll ans=0; int cnt=0;
    for(int i=N-1;i>0;i--){
        if(edg[i].size()>1){
            for(int j=1;j<edg[i].size();j++){
                int u=edg[i][0],v=edg[i][j];
                int paU=FindPa(u),paV=FindPa(v);
                if(paU!=paV){
                    ans+=i; cnt++;
                    pa[paU]=paV;
                    if(cnt==n-1)return ans;
                }
            }
        }
    }
}

void Init(){
    for(int i=1;i<=n;i++)
        pa[i]=i;
    for(int i=1;i<N;i++)
        edg[i].clear();
}

int main(){
    FindFac();
    
    int nCase; scanf("%d",&nCase);
    while(nCase--){
        scanf("%d",&n);
        Init();

        for(int i=1,a;i<=n;i++){
            scanf("%d",&a);
            for(int j=0;j<fac[a].size();j++)
                edg[fac[a][j]].push_back(i);
        }
        
        printf("%lld\n",Kruskal());
    }

    return 0;
}

F zzh 与同余方程

令 $m \in S (i)$ 为 $i$ 相关的同余方程的解：

$(i + 1)^{i + 1} \equiv (i + 1)^{i} (\mod m)$

多次询问，求 $\sum_{i = 1}^{n} | S (i) | (\mod 998244353)$ ，其中 $n \leq 10^{7}$ 。

题解

题目本质是要求 $m ∣ i (i + 1)^{i}$ 的所有 m，也就是 $i (i + 1)^{i}$ 的因数个数。注意到当 $(i, i + 1) = 1$ ，因此只要分别处理出每个数 $i$ 有多少个不同的质因数和每个质因数的数目 $k_{i}$ 即可。

由约数个数公式可知，对 $p = \prod p_{i}^{k_{i}}$ ，有约数个数 $D (p) = \prod (k_{i} + 1)$ ， $D (p^{q}) = \prod (k_{i} * q + 1)$ 。因此只要筛出所有素数，然后用素数筛掉它的倍数计算每个 $p$ 的 $k_{i}$ 即可。

时间复杂度：一个数的质因数分解中最多有 $\log_{2} n$ 个数，每个数 $p$ 都会被每个质因数一直筛到 1，因此时间复杂度是 $O (n \log n)$ 的。

代码

#include<cstdio>
#include<iostream>
#include<vector>
#include<ctime>
using namespace std;

typedef long long ll;

const int N=10000000+5,MOD=998244353;
int ans[N];
bool notPri[N];
int pri[N];

void Euler(){
    for(int i=2;i<N;i++){
        if(!notPri[i])
            pri[++pri[0]]=i;
        for(int j=1;j<=pri[0]&&i*pri[j]<N;j++){
            notPri[i*pri[j]]=1;
            if(i%pri[j]==0)break;
        }
    }
}

void FindFac(){
    for(int i=1;i<N;i++)ans[i]=1;

    for(int i=1;i<=pri[0];i++){
        for(int j=pri[i];j<N;j+=pri[i]){
            int cnt=0,tmp=j;
            while(tmp%pri[i]==0){
                tmp/=pri[i];
                cnt++;
            }
            ans[j-1]=1LL*ans[j-1]*(1LL*cnt*(j-1)%MOD+1)%MOD;
            ans[j]=1LL*ans[j]*(cnt+1)%MOD;
        }
    }
}

void Process(){
    for(int i=1;i<N;i++){
        ans[i]=(ans[i]+ans[i-1])%MOD;
    }
}

int main(){
    Euler();
    FindFac();
    Process();

    int nCase; scanf("%d",&nCase);
    while(nCase--){
        int x; scanf("%d",&x);
        printf("%d\n",ans[x]);
    }

    return 0;
}

G 小 z 刷题

给定 $n (\leq 10^{5})$ 个数对 $(a_{i}, p_{i})$ 表示一个连续的序列，一个数对表示数列的一部分，该部分由 $p_{i}$ 个 $a_{i}$ 构成。令 $S (x)$ 表示该序列中长度为 $x$ 的上升子序列个数，求 $\sum x^{k} \times S (x) (\mod 10^{9} + 7)$ ，其中 $k \leq 20$ 。

题解

很优美的一道题目。

假设已经知道前 $n$ 个数中满足 $a_{i} < a_{n + 1}$ 的 $\sum x^{k} \times S (x)$ ，考虑加入下一个数 $a_{n + 1}$ 。显然在原有答案末尾加入 $p_{n + 1}$ 个 $a_{n + 1}$ 后可以对答案做出贡献。下式进行二项式展开：

$\begin{aligned} \sum_{x} p_{n + 1} \times (x + 1)^{k} \times S (x) & = \sum_{x} p_{n + 1} \times \sum_{i = 1}^{k} (\binom{k}{i}) x^{i} \times S (x) \\ = \sum_{i = 1}^{k} (\binom{k}{i}) p_{n + 1} \sum_{x} x^{i} \times S (x) \end{aligned}$

即对新加入的结果，可以由满足 $a_{i} < a_{n + 1}$ 部分的 $\sum x^{t} \times S (x), t = 0, 1, 2, \dots, k$ 结果计算出来。因此离散化之后可以用树状数组维护 $t$ 次方下的答案并更新。

总时间复杂度 $O (n \log n + n k^{2})$ 。

代码

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long ll;

const int N=100000+5,MOD=1000000007,K=20+2;

struct BITree{
    int t[N];
    BITree(){
        Clear();
    }
    void Clear(){
        memset(t,0,sizeof(t));
    }
    int Lowbit(int x){
        return x&(-x);
    }
    void Add(int x,int v){
        for(;x<N;x+=Lowbit(x))
            t[x]=(t[x]+v)%MOD;
    }
    int Query(int x){
        int ret=0;
        for(;x;x-=Lowbit(x))
            ret=(ret+t[x])%MOD;
        return ret;
    }
};

BITree b[K];
int v[N],p[N],pos[N];		//val*p个
int c[K][K];
int n,k;

void InitComb(){
    for(int i=0;i<K;i++){
        c[0][i]=1;
        for(int j=1;j<=i;j++)
            c[j][i]=(c[j][i-1]+c[j-1][i-1])%MOD;
    }
}

int main(){
    InitComb();

    int nCase; scanf("%d",&nCase);
    while(nCase--){
        int n,k; scanf("%d%d",&n,&k);
        for(int i=1;i<=n;i++){
            scanf("%d%d",&v[i],&p[i]);
            pos[i]=v[i];
        }
        sort(pos+1,pos+n+1);

        for(int i=0;i<=k;i++)
            b[i].Clear();
        
        int ans=0;
        for(int i=1;i<=n;i++){
            int idx=lower_bound(pos+1,pos+n+1,v[i])-pos;
            int tmpSum[K];
            for(int j=0;j<=k;j++)
                tmpSum[j]=b[j].Query(idx-1);
            
            for(int j=0;j<=k;j++){
                int tmpAns=1;
                for(int l=0;l<=j;l++)
                    tmpAns=(tmpAns+1LL*tmpSum[l]*c[l][j])%MOD;
                
                tmpAns=1LL*tmpAns*p[i]%MOD;
                b[j].Add(idx,tmpAns);
                
                if(j==k)ans=(ans+tmpAns)%MOD;
            }
        }

        printf("%d\n",ans);
    }

    return 0;
}

I Ange 的 DNA 自动机

定义矩阵：

$\begin{aligned} A & = [\begin{array}{c} 1 & 0 \\ 0 & 1 \end{array}] \\ T & = [\begin{array}{c} 1 & 0 \\ 0 & - 1 \end{array}] \\ C & = [\begin{array}{c} - 1 & 0 \\ 0 & 1 \end{array}] \\ G & = [\begin{array}{c} - 1 & 0 \\ 0 & - 1 \end{array}] \end{aligned}$

给定长度为 $n (\leq 10^{6})$ 的字符串 $S = {s_{1}, s_{2}, \dots, s_{n}}$ 。定义一次操作 $S \to T ：$

$t_{i} = s_{i} \times s_{(i mod n) + 1}$

求经过 $k (\leq 10^{9})$ 次这样操作后的字符串 $T$ 。

题解

~~经过很显然的手推~~可以发现，令 $A, T, G, C$ 分别代表 $0, 1, 2, 3$ ，并定义乘法为异或操作的情况下，计算方法和原式等价。

假设 $f (k, i)$ 表示操作 $k$ 次后的串的第 $i$ 个数，则~~再一次经过很显然的手推~~可以发现有如下关系：

$f (k, i) = f (k - 2^{t}, i) \otimes f (k - 2^{t}, i + 2^{t})$

其中 $\otimes$ 表示异或操作， $t$ 是满足 $k - 2^{t} > 0$ 的最大 $t$ （也就是 $k$ 在二进制下的最高位）。这个递归是 $O (\log k)$ 级别的，因此总时间复杂度 $O (n \log k)$ 。

中间传 vector 太多导致第一次 T 掉了。还是要看场合使用啊。

代码

#include<iostream>
#include<cstdio>
#include<vector>
#include<ctime>
using namespace std;

const int N=1000000+5,K=32;
char ch[K][N];
int n;

int Highbit(int x){
    for(int i=30;i>=0;i--)
        if(x&(1<<i))return 1<<i;
    return 0;
}

char* NextXOR(int t,int dep){		//a是原数组
    if(t==0)return ch[0];
    int valHB=Highbit(t);

    char* pre=NextXOR(t-valHB,dep+1);
    char* ret=ch[dep];

    for(int i=0;i<n;i++)
        ret[i]=(pre[i]^pre[(i+valHB)%n]);

    return ret;
}

int main(){
    int nCase; scanf("%d",&nCase);
    while(nCase--){
        int k; scanf("%d%d\n",&n,&k);
        
        char* arr=ch[0];
        for(int i=0;i<n;i++){
            char c; scanf("%c",&c);
            if(c=='A'){
                arr[i]=0;
            }else if(c=='T'){
                arr[i]=1;
            }else if(c=='G'){
                arr[i]=2;
            }else if(c=='C'){
                arr[i]=3;
            }
        }
        
        char* ret=NextXOR(k,1);

        for(int i=0;i<n;i++){
            if(ret[i]==0)
                printf("A");
            else if(ret[i]==1)
                printf("T");
            else if(ret[i]==2)
                printf("G");
            else if(ret[i]==3)
                printf("C");
        }
        
        printf("\n");
    }

    return 0;
}

总结

是一套很有意思的题目~~和一位很菜的参赛者~~。

有两处错误都是因为中途爆了 long long 而 WA 掉了，并且一开始都没有找出原因来。深刻反省深刻反省。只要有 long long 和相乘的地方，都需要思考到底会不会爆 long long。

有一个比较隐式的爆法是， $x$ 每次都有可能变为 $⌊ \frac{x}{p} ⌋$ ，其中 $1 \leq p \leq 20$ 。 $p = 1$ 的情况下相当于 $x$ 每次都增加一倍，这个时候就会爆掉了。

明天的线下赛也要加油啊。

Nikkukun's Blog

BUAA Campus Programming Contest 2018 预赛

C 小张的魔法跳越

题解

代码

E 禁忌的共鸣

题解

代码

F zzh 与同余方程

题解

代码

G 小 z 刷题

题解

代码

I Ange 的 DNA 自动机

题解

代码

总结