2019 ICPC南京赛区网络赛题解

Solved	A	B	C	D	E	F	G	H	I
9/9	O	O	Ø	Ø	Ø	O	Ø	O	Ø

O for passing during the contest
Ø for passing after the contest
! for attempted but failed
· for having not attempted yet

比赛链接

A The beautiful values of the palace

题目描述

按照从外到内螺旋构造出$n \times n$的矩阵$M$，给定$m$个点是需要被考虑的，其他元素不予考虑，$p$次询问，每次询问一个区间代表问这个区间所有元素的数位和的和是多少。$n\leq 10^6;m,p\leq 10^5$。

解题思路

首先可以$O(1)$地求出每一个点上的数值是多少，再将每个询问利用容斥分解为四块，用一个树状数组维护一下就行了。

AC代码

点击

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
#define N 100010
int bit[N];
int n,m,p;
ll cal(int a, int b)
{
    a--;b--;
    int ra = max(max(a, n - a + 1), max(b, n - b + 1));
    int la = n - ra + 1;
    ll res = 4ll * n*(la - 1) - 4ll * (la - 1)*(la - 1);
    if (a == ra)
    {
        return res + ra - b + 1;
    }
    if (b == ra)
    {
        return 4ll * n*(la)-4ll * (la)*(la)-(ra - a) + 1;
    }
    if (b == la)
    {
        return  res + (ra - a) + n - 2 * (la - 1);
    }
    return res + b - la + 2 * n - 4 * (la - 1) - 1;
}
int calc(int x,int y){
    ll tmp=cal(x,y);
    int now=0;
    while(tmp){
        now+=tmp%10;
        tmp/=10;
    }
    return now;
}
struct Point{
    int id,sign,x,y;
    bool operator<(const Point&p)const{
        return x<p.x||x==p.x&&y<p.y;
    }
}P[N<<2];
pair<int,int>poi[N];
int res[N],tot;
void add(int ind){
    int i,x=poi[ind].first,y=poi[ind].second,temp=calc(x,y);
    for(i=y;i<N;i+=i&(-i))bit[i]+=temp;
}
int query(int y){
    int i,ans=0;
    for(i=y;i;i-=i&(-i))ans+=bit[i];
    return ans;
}
int main(){
    int i,t;
    scanf("%d",&t);
    while(t--){
        tot=0;
        memset(res,0,sizeof(res));
        memset(bit,0,sizeof(bit));//bitclear
        scanf("%d%d%d",&n,&m,&p);
        for(i=0;i<m;i++){
            scanf("%d%d",&poi[i].first,&poi[i].second);
            poi[i].first++;poi[i].second++;
        }
        sort(poi,poi+m);
        for(i=0;i<p;i++){
            int x1,x2,y1,y2;
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            x1++;y1++;x2++;y2++;
            P[++tot]={i,1,x1-1,y1-1};
            P[++tot]={i,-1,x1-1,y2};
            P[++tot]={i,1,x2,y2};
            P[++tot]={i,-1,x2,y1-1};
        }
        sort(P+1,P+tot+1);
        int j=0;
        for(i=1;i<=tot;i++){
            while(j<m&&poi[j]<=make_pair(P[i].x,P[i].y))
                add(j),j++;
            res[P[i].id]+=P[i].sign*query(P[i].y);
        }
        for(i=0;i<p;i++)printf("%d\n",res[i]);
    }
    return 0;
}

B super_log

题目描述

求$a^{a^{a^{.^{.^{.}}}}}(b层)\space mod\space m$的值

解题思路

欧拉降幂，$a,m$互质或$b<\phi(m)$的时候$a^b\space mod\space m=a^{b\space mod\space \phi(m)}\space mod\space m$，$b\geq \phi(m)$时$a^b\space mod\space m=a^{b\space mod\space \phi(m)+\phi(m)}\space mod\space m$，用$double$估计一下到当前位置的$b$的大小区分这两种情况即可。另外欧拉函数会在迭代几次之后就变为$1$，可以特判一下剪枝，否则会$T$。

AC代码 - by qxforever & Potassium

点击

#include <bits/stdc++.h>

using namespace std;
const int maxn = 1e7+23;
int phi[maxn],prime[maxn],cnt;
bool mark[maxn];
int T,a,b,m;
int md[maxn];
int qpow(int a,int b,int mod)
{
    int ans=1,base=a;
    while(b){
        if(b&1) ans=(1ll*ans*base)%mod;
        base=(1ll*base*base)%mod;
        b>>=1;
    }
    return ans%mod;
}

void getphi()
{
    phi[1]=1;cnt=0;
    for(int i=2;i<maxn;i++){
        if(!mark[i]){
            prime[cnt++]=i;
            phi[i]=i-1;
        }
        for(int j=0;j<cnt;j++){
            if(1LL*i*prime[j]>=maxn) break;
            mark[i*prime[j]]=1;
            if(i%prime[j]==0){
                phi[i*prime[j]]=phi[i]*prime[j];break;
            }
            else phi[i*prime[j]]=phi[i]*(prime[j]-1);
        }
    }
}

int main()
{
    getphi();
    cin >>T;
    while(T--){
        scanf("%d%d%d",&a,&b,&m);
        if(b==0) {printf("%d\n",1%m);continue;}
        md[0]=m;
        for(int i=1;i<=b;i++){
            md[i]=phi[md[i-1]];
            if(md[i]==1){
                b=i;
                break;
            }
        }
        int ans=a,flag=0;
        double now=a;
        for(int i=b-1;i>=1;i--){
        	if(now>1e7)flag=1;
            if(now>=md[i]||flag)ans=qpow(a,ans%md[i]+md[i],md[i-1]);
            else ans=qpow(a,ans,md[i-1]);
        	now=pow(a,now);
        }
        printf("%d\n",ans%m);
    }
}

C Tsy’s number 5

题目描述

给定$n\leq 10^5$，求$\sum_{i=1}^{n}\sum_{j=1}^{n}\phi(i)\phi(j)2^{\phi(i)\phi(j)}$。

解题思路

首先$\phi$函数出现在指数上很难处理，考虑枚举$\phi(i)$和$\phi(j)$。于是不妨设$f[x]$表示$\phi(i)=x$的$i$的个数，然后化一下式子：

$\sum_{i=1}^{n}\sum_{j=1}^{n}\phi(i)\phi(j)2^{\phi(i)\phi(j)}$

$=\sum_{i=1}^{n}\sum_{j=1}^{n}ijf[i]f[j]2^{ij}$

两个常见套路：将上界变为$i$，$2^{ij}=2^{\frac{-(i-j)^2+i^2+j^2}2}$

$=\sum_{i=1}^{n}\sum_{j=1}^{n}if[i]2^{\frac{i^2}2}\cdot jf[j]2^{\frac{j^2}2}\cdot 2^{\frac{-(i-j)^2}2}$

$=2\sum_{i=1}^{n}if[i]2^{\frac{i^2}2}\sum_{j=1}^{i}jf[j]2^{\frac{j^2}2}\cdot 2^{\frac{-(i-j)^2}2}-\sum_{i=1}^{n}i^2f[i]^22^{i^2}$

设$C[i]=\sum_{j=1}^{i}jf[j]2^{\frac{j^2}2}\cdot 2^{\frac{-(i-j)^2}2}$，很显然这是一个卷积的形式，可以通过$NTT$或者拆系数$FFT$来做，预处理一下$2^{\frac 12}\space mod\space 998244353$的值（二次剩余）以及它的$i^2$次幂即可。

代码中注释掉的部分替换掉拆系数$FFT$就是$NTT$，不过似乎比拆系数要慢一些（$200ms$）。

AC代码

点击

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
#define M 262144
int qp(ll a,int p,int mod){
    ll ans=1;
    for(;p;p>>=1,a=a*a%mod)if(p&1)ans=ans*a%mod;
    return ans;
}/*
const int G=3;
int R[M+5],mod,lim,mx;
int A[M+5],B[M+5],C[M+5];
void NTT(int* a,int f){
	int i,j,k;
	for(i=0;i<lim;i++)if(i<R[i])swap(a[i],a[R[i]]);
	for(i=1;i<lim;i<<=1){
		int gn=qp(G,(mod-1)/(i<<1),mod);
		for(j=0;j<lim;j+=(i<<1)){
			int g=1;
			for(k=0;k<i;k++,g=1ll*g*gn%mod){
				int x=a[j+k],y=1ll*g*a[j+k+i]%mod;
				a[j+k]=(x+y)%mod;a[j+k+i]=(x-y+mod)%mod;
			}
		}
	}
	if(f==1)return;
	int nv=qp(lim,mod-2,mod);reverse(a+1,a+lim);
	for(i=0;i<lim;i++)a[i]=1ll*a[i]*nv%mod;
}
void fft_prepare(){
	int i;
	for(i=0;i<lim;i++)R[i]=R[i>>1]>>1|((i&1)<<(mx-1));
}
void conv(int *x,int *y,int *z){
	NTT(x,1);NTT(y,1);
	for(int i=0;i<lim;i++)z[i]=1LL*x[i]*y[i]%mod;
	NTT(z,-1);
}*/
struct comp{
    double x,y;
    comp():x(0),y(0){}
    comp(const double &_x,const double &_y):x(_x),y(_y){}
};
comp operator+(const comp &a,const comp &b){return comp(a.x+b.x,a.y+b.y);}
comp operator-(const comp &a,const comp &b){return comp(a.x-b.x,a.y-b.y);}
comp operator*(const comp &a,const comp &b){return comp(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}
comp conj(const comp &a){return comp(a.x,-a.y);}
double PI=acos(-1);
comp w[M+5];
int rev[M+5];
int A[M+5],B[M+5],C[M+5],lim,mx,mod=998244353;
void fft(comp *a,int n){
    int i,j,k,lyc;
    for(i=0;i<n;i++)if(i<rev[i]) swap(a[i],a[rev[i]]);
    for(i=2,lyc=n>>1;i<=n;i<<=1,lyc>>=1)
        for(j=0;j<n;j+=i){
            comp *l=a+j,*r=a+j+(i>>1),*p=w;
            for(k=0;k<(i>>1);k++){
                comp tmp=*r**p;
                *r=*l-tmp,*l=*l+tmp;
                ++l,++r,p+=lyc;
            }
        }
}
void fft_prepare(){
    int i;
    for(i=0;i<lim;i++)rev[i]=rev[i>>1]>>1|((i&1)<<(mx-1));
    for(i=0;i<lim;i++)w[i]=comp(cos(2*PI*i/lim),sin(2*PI*i/lim));
}
comp a[M+5],b[M+5],ta[M+5],tb[M+5];
void conv(int *x,int *y,int *z){//from x,y to z
    int i,j;
    //for(i=0;i<lim;i++)(x[i]+=mod)%=mod,(y[i]+=mod)%=mod;
    for(i=0;i<lim;i++){
        ta[i]=comp(x[i]&32767,x[i]>>15);
        tb[i]=comp(y[i]&32767,y[i]>>15);
    }
    fft(ta,lim);fft(tb,lim);
    for(i=0;i<lim;i++){
        j=(lim-i)%lim;
        comp da,db,dc,dd;
  		da=(ta[i]+conj(ta[j]))*comp(0.5,0);
        db=(ta[i]-conj(ta[j]))*comp(0,-0.5);
        dc=(tb[i]+conj(tb[j]))*comp(0.5,0);
        dd=(tb[i]-conj(tb[j]))*comp(0,-0.5);
        a[j]=da*dc+da*dd*comp(0,1);
        b[j]=db*dc+db*dd*comp(0,1);
    }
    fft(a,lim);fft(b,lim);
    for(i=0;i<lim;i++){
        ll da,db,dc,dd;
        da=(ll)(a[i].x/lim+0.5)%mod;
        db=(ll)(a[i].y/lim+0.5)%mod;
        dc=(ll)(b[i].x/lim+0.5)%mod;
        dd=(ll)(b[i].y/lim+0.5)%mod;
        z[i]=((da+((db+dc)<<15)+(dd<<30))%mod+mod)%mod;
    }
}
int f[M+5];
int phi[M+5],np[M+5],pri[M+5],tot;
void sieve(){
    phi[1]=1;
    int i,j;np[0]=np[1]=1;
    for(i=2;i<M;i++){
        if(!np[i])pri[tot++]=i,phi[i]=i-1;
        for(j=0;j<tot;j++){
            if(pri[j]*i>=M)break;
            np[i*pri[j]]=1;
            if(i%pri[j]==0){
                phi[i*pri[j]]=phi[i]*pri[j];
                break;
            }else phi[i*pri[j]]=phi[i]*phi[pri[j]];
        }
    }
}
int sqrt2=116195171;//2的二次剩余
int ini[M],ini2[M];//sqrt2^{i^2},inv
void calc(int x){
    static int AA[M+5];
    int i;
    memset(f,0,sizeof(f));
    for(i=1;i<=x;i++)f[phi[i]]++;
    /*ll tmp=0;
	for(int i=1;i<=x;i++)
		for(int j=1;j<=x;j++)
			(tmp+=1LL*phi[i]*phi[j]%mod*qp(2,phi[i]*phi[j]%(mod-1),mod)%mod)%=mod;
	printf("%lld\n",tmp);*/
    int tmp;
    mx=0;for(tmp=1;tmp<=2*x+2;tmp<<=1)mx++;
    lim=tmp;
    for(i=0;i<=x;i++)AA[i]=A[i]=1LL*i*f[i]%mod*ini[i]%mod;
    for(;i<=lim;i++)AA[i]=A[i]=0;
    for(i=0;i<=x;i++)B[i]=ini2[i];
    for(;i<=lim;i++)B[i]=0;
    fft_prepare();
    conv(AA,B,C);//0-index
    ll res=0;
    for(i=1;i<=x;i++)(res+=1LL*A[i]*C[i]%mod*2%mod-1LL*i*i%mod*f[i]%mod*f[i]%mod*ini[i]%mod*ini[i]%mod+mod)%=mod;
    printf("%lld\n",res);
}
void init(){
    int i;
    for(i=0;i<M;i++)ini[i]=qp(sqrt2,1LL*i*i%(mod-1),mod),ini2[i]=qp(ini[i],mod-2,mod);
}
int main(){
    int t,n;
    sieve();
    init();
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        calc(n);
    }
    return 0;
}

D Robots

题目描述

给定一个有向无环图，机器人从$1$开始走，每天等概率走向当前节点的后继或留在原地，第$i$天消耗代价为$i$，问到$n$点的代价之和的期望。

解题思路

设$f[i][j]$表示$j$时刻，机器人在$i$点的概率，那么显然有$q_i=\sum_{j=0}^{\infty} \times j\times (j+1)\times f[i][j]$，$\frac{q_n}2$即为所求。

设$a_i=\frac 1{oud[i]+1}$，记$u$为$i$前驱为$u\rightarrow i$，对于不为$n$的点$i$，有转移$f[i][j]=a_if[i][j-1]+\sum_{u\rightarrow i}a_uf[u][j-1]$，对于点$n$，有$f[i][j]=\sum_{u\rightarrow i}a_uf[u][j-1]$。

以不为$n$的点为例：

$q_i=\sum_{j=0}^{\infty}j(j+1)f[i][j]=\sum_{j=1}^{\infty}j(j+1)(a_if[i][j-1]+\sum_{u\rightarrow i}a_uf[u][j-1])$

$=\sum_{j=0}^{\infty}(j+1)(j+2)a_if[i][j]+\sum_{u\rightarrow i}\sum_{j=0}^{\infty}(j+1)(j+2)a_uf[u][j]$

$=\sum_{j=0}^{\infty}j(j+1)a_if[i][j]+\sum_{u\rightarrow i}\sum_{j=0}^{\infty}j(j+1)a_uf[u][j]+\sum_{j=0}^{\infty}(2j+2)(a_if[i][j]+\sum_{u\rightarrow i}a_uf[u][j])$

$=a_iq_i+\sum_{u\rightarrow i}a_uq_u+2a_it_i+2a_is_i+\sum_{u\rightarrow i}2a_ut_u+2a_us_u$

其中$t,s$为类似$q$定义的数组，$t_i=\sum_{j=0}^{\infty}jf[i][j],s_i=\sum_{j=0}^{\infty}f[i][j]$，可以类似$q$地推出式子。我们发现这是一个按拓扑序$dp$的问题，每次更新一下即可。

AC代码

点击

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
#define N 100010
double a[N],p[N],t[N],s[N];
int ind[N],oud[N];
struct Edge{
    int e,n;
}e[N<<1];
int hd[N],cnt;
void add(int a,int b){e[++cnt].e=b;e[cnt].n=hd[a];hd[a]=cnt;}
queue<int>Q;
int main(){
    int i,T,n,m,u,v;
    scanf("%d",&T);
    while(T--){
        cnt=0;
        memset(hd,0,sizeof(hd));
        memset(ind,0,sizeof(ind));
        memset(oud,0,sizeof(oud));
        scanf("%d%d",&n,&m);
        for(i=0;i<m;i++){
            scanf("%d%d",&u,&v);
            add(u,v);
            oud[u]++;ind[v]++;
        }
        for(i=1;i<=n;i++){
            p[i]=s[i]=t[i]=0;
            a[i]=1.0/(oud[i]+1);
        }
        Q.push(1);
        p[1]=-2*a[1]/pow(a[1]-1,3);
        t[1]=a[1]/pow(a[1]-1,2);
        s[1]=1/(1-a[1]);
        while(!Q.empty()){
            int now=Q.front();Q.pop();
            for(i=hd[now];i;i=e[i].n){
                int q=e[i].e;
                if(!--ind[q])Q.push(q);
                if(q==n){
                    s[q]+=a[now]*s[now];
                    t[q]+=a[now]*(s[now]+t[now]);
                    p[q]+=a[now]*(p[now]+2*t[now]+2*s[now]);
                }else{
                    double deltaS=a[now]*s[now]/(1-a[q]);
                    double deltaT=a[now]*(s[now]+t[now])/(1-a[q])+deltaS*a[q]/(1-a[q]);
                    double deltaP=a[now]*(p[now]+2*t[now]+2*s[now])/(1-a[q]);
                    deltaP+=a[q]*(2*deltaS+2*deltaT)/(1-a[q]);
                    s[q]+=deltaS;
                    t[q]+=deltaT;
                    p[q]+=deltaP;
                }
            }
        }
        printf("%.2f\n",p[n]/2);
    }
    return 0;
}

还有一种更简便也更巧妙的做法：

设$t[i]$表示到点$i$的时间期望，有$t[i]=(a_i(t[i]+1)+a_i\sum_{i\rightarrow u}(t[u]+1))$（$u$是$i$的后继，从后向前递推）

再设$e[i]$表示到点$i$的花费的期望，有$e[i]=(a_i(e[i]+0)+a_i\sum_{i\rightarrow u}(e[u]+t[u]))$。

如何理解这两个式子？

你知道时间的期望了

那转移的时候的cost就是每个点的时间的期望

第一个式子转移的cost相当于1

——qxforever

没了。

AC代码 - by qxforever

点击

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;
//typedef long long ll;
int T,n,m,u,v;
const int maxn = 1e5+23;
vector<int> g[maxn];
double dp[maxn],f[maxn];
int vis[maxn],out[maxn];
void dfs(int now)
{
    vis[now]=1;
    if(now==n) return;
    for(auto i:g[now]){
        if(!vis[i]){
            dfs(i);
        }
        dp[now]+=dp[i];
        f[now]+=f[i]+dp[i];
    }
    int deg=g[now].size();
    double d=1.0/(1.0+deg);
    dp[now]=(d*(dp[now])+1)/(1-d);
    f[now]=(d*(f[now]+dp[now])+1)/(1-d);
}



int main()
{
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++){
            dp[i]=f[i]=0;
            g[i].resize(0);
            vis[i]=0;
        }
        for(int i=0;i<m;i++){
            scanf("%d%d",&u,&v);
            //out[v]++;
            g[u].push_back(v);
        }
        dfs(1);
        //for(int i=1;i<=n;i++) printf("%.2f ",dp[i]);
        printf("%.2f\n",f[1]);
    }
}

E K Sum

题目描述
给定$1\leq n\leq 10^9,2\leq k\leq 10^{10^5}$，求$\sum_{i=2}^{k}f_n(i)$，其中$f_n(i)=\sum_{l_1=1}^{n}\sum_{l_2=1}^{n}…\sum_{l_i=1}^{n}(gcd(l_1,l_2,…,l_i))^2$。

解题思路
一个套路，先枚举$gcd$：

$f_n(i)=\sum_{g=1}^{n}\sum_{l_1=1}^{n}\sum_{l_2=1}^{n}…\sum_{l_i=1}^{n}g^2[gcd(l_1,l_2,…,l_n)=g]$

$=\sum_{g=1}^{n}\sum_{l_1=1}^{\lfloor\frac ng\rfloor}\sum_{l_2=1}^{\lfloor\frac ng\rfloor}…\sum_{l_i=1}^{\lfloor\frac ng\rfloor}g^2[gcd(l_1,l_2,…,l_n)=1]$

对于$p(x)=\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=x]$，有

$q(d)=\sum_{d|x}p(x)$

$=\sum_{i=1}^{n}\sum_{j=1}^{m}[d|gcd(i,j)]$

$=\sum_{i=1}^{n}\sum_{j=1}^{m}[d|i][d|j]$

$=\lfloor\frac nd\rfloor\lfloor\frac md\rfloor$

莫比乌斯反演可得$p(x)=\sum_{x|d}\mu(\frac dx)q(d)=\sum_{x|d}\mu(\frac dx)\lfloor\frac nd\rfloor\lfloor\frac md\rfloor$

同理，对于$f_n(i)$，类似的可以得出

$f_n(i)=\sum_{g=1}^{n}g^2\sum_{1|d}\mu(d)\lfloor\frac{\frac ng}d\rfloor^i$

$=\sum_{g=1}^{n}g^2\sum_{d=1}^{\lfloor\frac ng\rfloor}\mu(d)\lfloor\frac n{gd}\rfloor^i$

改变枚举对象为$l=gd$，范围为$1-n$，$g$只需满足$g|l$：

$=\sum_{l=1}^{n}\lfloor\frac n{l}\rfloor^i\sum_{g|l}g^2\mu(\frac lg)$

第一个求和号里是一个等比数列$G$，对于$k$可以欧拉降幂求解，于是我们如果能快速知道第二个求和号里的前缀和，就可以用数论分块快速求解。

观察到第二个求和号里是$idid\mu$的形式，卷上一个$I$之后就变成了$id*id$，这很容易求和，杜教筛筛一下即可。

AC代码
点击
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
#define N 5000000
int np[N+10],p[N+10],tot,n;
ll q[N+10];
int mod=1000000007;
int qp(ll a,int p,int mod){
    ll ans=1;
    for(;p;p>>=1,a=a*a%mod)if(p&1)ans=ans*a%mod;
    return ans;
}
void sieve(){
    q[1]=np[0]=np[1]=1;
    register int i,j;
    for(i=2;i<N;i++){
        if(!np[i])p[tot++]=i,q[i]=(1ll*i*i-1)%mod;
        for(j=0;j<tot;j++){
            if(p[j]*i>=N)break;
            np[p[j]*i]=1;
            if(i%p[j]==0){
                q[i*p[j]]=1ll*q[i]*p[j]%mod*p[j]%mod;
                break;
            }else q[i*p[j]]=q[i]*q[p[j]]%mod;
        }
    }
    for(i=1;i<N;i++)(q[i]+=q[i-1])%=mod;
}
unordered_map<int,ll>ansq;
inline ll getsQ(ll n){//S=sum of f
    if(n<N)return q[n];
    if(ansq[n])return ansq[n];
    ll ans=n*(n+1)%mod*(2*n%mod+1)%mod*qp(6,mod-2,mod)%mod;//sum of f*g
    register ll l,r;
    for(l=2;l<=n;l=r+1){
        r=n/(n/l);
        (ans-=(r-l+1)*getsQ(n/l))%=mod;//sum of g(r-l),times S(n/l)
    }
    return ansq[n]=(ans+mod)%mod;
}
inline pair<int,int> read(){
    register int x1=0,x2=0;register char c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')x1=(1LL*x1*10+c-48)%mod,x2=(1LL*x2*10+c-48)%(mod-1),c=getchar();
    return make_pair(x1,x2);
}
inline ll getsG(int x,int k,int pk){
    if(x==1)return (k-1+mod)%mod;
    return 1LL*x*x%mod*qp(x-1,mod-2,mod)%mod*(qp(x,pk-1,mod)+mod-1)%mod;
}
int main(){
    int t,l,r,n,k;
    sieve();
    t=read().first;
    while(t--){
        ll res=0;
        n=read().first;
        pair<int,int>tmp=read();
        k=tmp.first;int pk=tmp.second;
        for(l=1;l<=n;l=r+1){
            r=n/((n/l));
            ll t1=getsG(n/l,k,pk);
            ll t2=getsQ(r)-getsQ(l-1)+mod;
            (res+=t1*t2%mod)%=mod;
        }
        printf("%lld\n",res);
    }
    return 0;
}

F Greedy Sequence

题目描述

按要求造一个数列。

解题思路

签到题，线段树动态加点查询区间最大值即可。

AC代码

点击

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
#define N 200010
int mx[N<<2],L[N<<2],R[N<<2];
int pos[N],a[N];
void build(int p,int l,int r){
    L[p]=l;R[p]=r;mx[p]=0;
    if(l==r)return;
    build(p<<1,l,(l+r)>>1);
    build(p<<1|1,((l+r)>>1)+1,r);
}
int query(int p,int l,int r){
    if(L[p]>=l&&r>=R[p])return mx[p];
    if(L[p]>r||R[p]<l)return 0;
    return max(query(p<<1,l,r),query(p<<1|1,l,r));
}
void modify(int p,int pos,int x){
    if(L[p]>pos||R[p]<pos)return;
    if(L[p]==R[p]){
        mx[p]=x;
        return;
    }
    modify(p<<1,pos,x);
    modify(p<<1|1,pos,x);
    mx[p]=max(mx[p<<1],mx[p<<1|1]);
}
int ans[N];
int main(){
    int i,t,n,k;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&k);
        for(i=1;i<=n;i++)scanf("%d",&a[i]),pos[a[i]]=i;
        build(1,1,n);
        ans[0]=0;
        for(i=1;i<=n;i++){
            ans[i]=ans[query(1,max(1,pos[i]-k),min(n,pos[i]+k))]+1;
            modify(1,pos[i],i);
            printf("%d%c",ans[i],i==n?'\n':' ');
        }
    }
    return 0;
}

G Quadrilateral

题目描述
给定$a,b,c,d$的范围，求有多少对$a,b,c,d$能构成一个四边形。

解题思路
枚举$d$，先考虑$abc$的范围都能表示成$[1,x]$的情况，即$a\in[1,r_1],b\in[1,r_2],c\in[1,r_3]$

这时，合法的四边形即为所有情况减去$x+y+z\leq w$形式的四元组个数。

当$d$为最大边时，可以表示成$[1,r_1]+[1,r_2]\leq [d-r_3,d-1]$；当$a$为最大边（$b,c$同理）时，可以表示成$[1,r_2]+[1,r_3]\leq [1-d,r_1-d]$。而这都可以转化为类似$[1,x_1]+[1,x_2]\leq [1,x_3]$的三元组个数容斥求解。

纵坐标表示和，横坐标表示$b$的取值，可以列出一张表，对这张表进行容斥即可求出$[1,x_1]+[1,x_2]\leq [1,x_3]$的个数。

AC代码
点击
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int x[10];
ll t(ll x){
    if(x<0)return 0;
    return x*(x+1)/2*(x+2)/3;
}
ll f(ll a,ll b,ll r){
    r--;
    a=min(a,r);b=min(b,r);
    return t(r)-t(r-a)-t(r-b)+t(r-a-b);
}
ll calc(int d,int a,int b,int c){
    ll t=1LL*a*b*c;
    t-=f(a,b,d-1)-f(a,b,d-c-1)+f(b,c,a-d)+f(c,a,b-d)+f(a,b,c-d);
    return t;
}
int main(){
    int i,T;
    scanf("%d",&T);
    while(T--){
        for(i=1;i<=8;i++)scanf("%d",&x[i]);
        ll res=0;
        for(i=x[7];i<=x[8];i++){
            res+=calc(i,x[2],x[4],x[6]);
            res-=calc(i,x[2],x[4],x[5]-1);
            res-=calc(i,x[2],x[3]-1,x[6]);
            res+=calc(i,x[2],x[3]-1,x[5]-1);
            res-=calc(i,x[1]-1,x[4],x[6]);
            res+=calc(i,x[1]-1,x[4],x[5]-1);
            res+=calc(i,x[1]-1,x[3]-1,x[6]);
            res-=calc(i,x[1]-1,x[3]-1,x[5]-1);
        }
        printf("%lld\n",res);
    }
    return 0;
}

H Holy Grail

题目描述

给一个有向无负环的图，依次加六个边使得每次边加入后不能有负环且边权尽量小。

解题思路

签到题，$floyd$即可水过，每次加边$O(n^2)$松弛。

AC代码

点击

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
#define N 520
ll dis[N][N];
int main(){
    int i,j,k,t,n,m;
    scanf("%d",&t);
    while(t--){
        memset(dis,0x3f,sizeof(dis));
        scanf("%d%d",&n,&m);
        for(i=0;i<=n;i++)dis[i][i]=0;
        for(i=0;i<m;i++){
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            dis[u][v]=min(dis[u][v],(ll)w);
        }
        for(k=0;k<=n;k++)
            for(i=0;i<=n;i++)
                for(j=0;j<=n;j++)
                    if(dis[i][j]>dis[i][k]+dis[k][j])
                        dis[i][j]=dis[i][k]+dis[k][j];
        for(k=0;k<6;k++){
            int u,v;
            scanf("%d%d",&u,&v);
            printf("%d\n",-dis[v][u]);
            dis[u][v]=min(dis[u][v],-dis[v][u]);
            for(i=0;i<=n;i++)
                for(j=0;j<=n;j++)
                    if(dis[i][j]>dis[i][u]+dis[u][v]+dis[v][j])
                        dis[i][j]=dis[i][u]+dis[u][v]+dis[v][j];
        }
    }
    return 0;
}

I Washing clothes

题目描述
有$n$ 个人在不同时刻到达洗衣服的地点。每个人可以选择花费$y$时间手洗，也可选择花费$x$时间机洗，但洗衣机只有一台。对于每一个$x\in[1,y]$，求出最后一个洗完衣服的人最早在什么时候能够洗完衣服。

解题思路
设$p=\frac yx$，于是倒数第$p+1$个人即使手洗也一定比后$p$个人全部依次机洗结束的早，于是只考虑后$p$个人的情况即可。

保证最后的几个人都不间断使用机洗必然是不劣的，于是对于倒数$p$个人中的每个人，算出从这个人开始一直不间断使用洗衣机的最大时间，再与倒数$p+1$个人的手洗时间取一个$max$即可。复杂度是调和级数$O(y\log y)$。

AC代码
点击
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int n,y,t[1000010];
int main(){
    int i,j;
    while(~scanf("%d%d",&n,&y)){
        for(i=1;i<=n;i++)scanf("%d",&t[i]);
        sort(t+1,t+n+1);
        for(i=1;i<=y;i++){
            int p=min(n,y/i),res=0;
            if(p<n)res=max(res,t[n-p]+y);
            for(j=n-p+1;j<=n;j++)res=max(res,t[j]+(n-j+1)*i);
            printf("%d%c",res,i==y?'\n':' ');
        }
    }
    return 0;
}