The Preliminary Contest for ICPC Asia Nanjing 2019

2019/09/02 18:59
阅读数 225

A. The beautiful values of the palace

求出每个点的权值, 然后树状数组扫描线

#include <iostream>
#include <sstream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <cstring>
#include <bitset>
#include <functional>
#include <random>
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define PER(i,a,n) for(int i=n;i>=a;--i)
#define hr putchar(10)
#define pb push_back
#define lc (o<<1)
#define rc (lc|1)
#define mid ((l+r)>>1)
#define ls lc,l,mid
#define rs rc,mid+1,r
#define x first
#define y second
#define io std::ios::sync_with_stdio(false)
#define endl '\n'
#define DB(a) ({REP(__i,1,n) cout<<a[__i]<<' ';hr;})
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int P = 1e9+7, INF = 0x3f3f3f3f;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll qpow(ll a,ll n) {ll r=1%P;for (a%=P;n;a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;}
ll inv(ll x){return x<=1?1:inv(P%x)*(P-P/x)%P;}
inline int rd() {int x=0;char p=getchar();while(p<'0'||p>'9')p=getchar();while(p>='0'&&p<='9')x=x*10+p-'0',p=getchar();return x;}
//head



const int N = 1e6+50;
int n,m,p,cnt;
ll f[N][5],b[N];
pii pos[N][5];

int type(int x, int y) {
	int a=min(abs(x-1),abs(x-n));
	int b=min(abs(y-1),abs(y-n));
	return min(a,b)+1;
}
ll get(int x, int y) {
	int d = type(x,y);
	if (d==n/2+1) return (ll)n*n;
	if (x==pos[d][1].x) {
		return f[d][1]+pos[d][1].y-y;
	}
	if (y==pos[d][2].y) {
		return f[d][2]-x+pos[d][2].x;
	}
	if (x==pos[d][3].x) {
		return f[d][3]+y-pos[d][3].y;
	}
	return f[d][4]+x-pos[d][4].x;
}
int solve(int x, int y) {
	ll t = get(x,y);
	int ret = 0;
	while (t) ret+=t%10,t/=10;
	return ret;
}

struct _ {
	int h,w,type;
	void pr() {
	printf("h=%d,w=%d,type=%d\n",h,w,type);
	}
};
vector<_> e[N],ee[N];
void add(int x, int y, int v, int id) {
	e[x].pb({y,id,v});
}
ll ans[N];
ll cc[N];

ll query(int x) {
	ll ret = 0;
	for (; x; x^=x&-x) ret += cc[x];
	return ret;
}

void add(int x, int v) {
	for (; x<=n; x+=x&-x) cc[x]+=v;
}

void work() {
	cnt = 0;
	f[1][1] = 1;
	f[1][2] = n;
	f[1][3] = 2*n-1;
	f[1][4] = 3*n-2;
	pos[1][1] = pii(n,n);
	pos[1][2] = pii(n,1);
	pos[1][3] = pii(1,1);
	pos[1][4] = pii(1,n);
	int now = n-1;
	REP(d,2,n/2) {
		REP(j,1,4) pos[d][j]=pos[d-1][j];
		--pos[d][1].x,--pos[d][1].y;
		--pos[d][2].x,++pos[d][2].y;
		++pos[d][3].x,++pos[d][3].y;
		++pos[d][4].x,--pos[d][4].y;
		f[d][1] = f[d-1][4]+now;
		now -= 2;
		f[d][2] = f[d][1]+now;
		f[d][3] = f[d][2]+now;
		f[d][4] = f[d][3]+now;
	}
	REP(i,0,n+1) e[i].clear(),cc[i]=0,ee[i].clear();
	REP(i,1,m) {
		int x, y;
		scanf("%d%d", &x, &y);
		ee[x].pb({y,solve(x,y),-2});
	}
	REP(i,1,p) {
		int x1,y1,x2,y2;
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		--x1,--y1;
		add(x2,y2,1,i);
		add(x2,y1,-1,i);
		add(x1,y2,-1,i);
		add(x1,y1,1,i);
		ans[i] =0;
	}
	REP(i,1,n) { 
		for(auto t:ee[i]) add(t.h,t.w);
		for(auto t:e[i]) {
			ans[t.w] += t.type*query(t.h);
		}
	}
	REP(i,1,p) printf("%lld\n",ans[i]);
}

int main() {
	int t;
	scanf("%d", &t);
	while (t--) scanf("%d%d%d",&n,&m,&p),work();
}

  

B. super_log

答案是a^a^a^...^a, 一共$b$个$a$, 可以用拓展欧拉定理 

#include <iostream>
#include <algorithm>
#include <math.h>
#include <cstdio>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <string.h>
#include <queue>
#define PER(i,a,n) for(int i=n;i>=a;--i)
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define hr cout<<'\n'
#define pb push_back
#define mid ((l+r)>>1)
#define lc (o<<1)
#define rc (lc|1)
#define ls lc,l,mid
#define rs rc,mid+1,r
#define x first
#define y second
#define io std::ios::sync_with_stdio(false);
#define endl '\n'
using namespace std;
#define mod(a,b) a<b?a:a%b+b
typedef long long ll;
typedef pair<int,int> pii;
int P = 1e9+7;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll qpow(ll a,ll n,ll P) {
	ll r=1;
	for (;n;a=mod(a*a,P),n>>=1) if(n&1)r=mod(r*a,P);
	return r;
}
const int N = 1e6+10;
int f[N], n, m;
map<int,int> dp;
int phi(int x) {
	if (dp.count(x)) return dp[x];
	int mx = sqrt(x+0.5), r = x, t = x;
	REP(i,2,mx) if (x%i==0) {
		r = r/i*(i-1);
		while (x%i==0) x/=i;
	}
	if (x>1) r=r/x*(x-1);
	return dp[t]=r;
}
int query(int a, int n, int m) {
	if (n==1||m==1) return mod(a,m);
	return qpow(a,query(a,n-1,phi(m)),m);
}
void work() {
	int a,b,m;
	scanf("%d%d%d", &a, &b, &m);
	if (b==0) return printf("%d\n",1%m),void();
	dp.clear();
	printf("%d\n",query(a,b,m)%m);
}
int main() {
	int t;
	scanf("%d", &t);
	while (t--) work();
}

 

C. Tsy's number 5

设$f_i=\sum\limits_{k=1}^n[\varphi(k)=i]$, 然后原式就等于$\sum\limits_{i=1}^n\sum\limits_{j=1}^n f_if_jij2^{ij}$

可以化为求$\sum\limits_{j=1}^i jf_j 2^{ij}={\sqrt{2}}^{i^2}\sum\limits_{j=1}^ijf_j {\sqrt{2}}^{j^2-(i-j)^2}$

设$a_i = if_i{\sqrt{2}}^{i^2}$, $b_i= {\sqrt{2}}^{-i^2}$, $NTT$求一下$a*b$即可

#include <iostream>
#include <sstream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <cstring>
#include <bitset>
#include <functional>
#include <random>
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define PER(i,a,n) for(int i=n;i>=a;--i)
#define hr putchar(10)
#define pb push_back
#define lc (o<<1)
#define rc (lc|1)
#define mid ((l+r)>>1)
#define ls lc,l,mid
#define rs rc,mid+1,r
#define x first
#define y second
#define io std::ios::sync_with_stdio(false)
#define endl '\n'
#define DB(a) ({REP(__i,1,n) cout<<a[__i]<<' ';hr;})
using namespace std;
typedef long long ll;
typedef int* poly;
const int P = 998244353, G = 3, Gi = 332748118, sqr = 116195171;
ll qpow(ll a,ll n) {ll r=1%P;for (a%=P;n;a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;}

const int N = 1e6+10;
int n,phi[N],f[N];
int A[N],B[N],R[N],l,lim;
void init(int n) {
	for (lim=1,l=0; lim<=n; lim<<=1,++l) ;
	REP(i,0,lim-1) R[i]=(R[i>>1]>>1)|((i&1)<<(l-1));
}
void NTT(poly J, int tp=1) {
	REP(i,0,lim-1) if (i<R[i]) swap(J[i],J[R[i]]);
	for (int j=1; j<lim; j<<=1) {
		ll T = qpow(tp==1?G:Gi,(P-1)/(j<<1));
		for (int k=0; k<lim; k+=j<<1) {
			ll t = 1;
			for (int l=0; l<j; ++l,t=t*T%P) {
				int y = t*J[k+j+l]%P;
				J[k+j+l] = (J[k+l]-y)%P;
				J[k+l] = (J[k+l]+y)%P;
			}
		}
	}
	if (tp==-1) {
		ll inv = qpow(lim, P-2);
		REP(i,0,lim-1) J[i]=(ll)inv*J[i]%P;
	}
}
poly mul(poly a, poly b) {
	init((n+1)*2);
	REP(i,0,lim-1) A[i]=B[i]=0;
	REP(i,0,n) A[i]=a[i],B[i]=b[i];
	NTT(A),NTT(B);
	poly c(new int[lim]);
	REP(i,0,lim-1) c[i]=(ll)A[i]*B[i]%P;
	NTT(c,-1);
	return c;
}

void work() {
	scanf("%d", &n);
	REP(i,1,n) f[i] = 0;
	REP(i,1,n) ++f[phi[i]];
	poly a(new int[n+1]),b(new int[n+1]);
	REP(i,0,n) { 
		a[i] = (ll)i*f[i]%P*qpow(sqr,(ll)i*i%(P-1))%P;
		b[i] = qpow(sqr,P-1-(ll)i*i%(P-1));
	}
	poly g = mul(a,b);
	int ans = 0;
	REP(i,1,n) ans = (ans+(ll)i*f[i]%P*qpow(sqr,(ll)i*i%(P-1))%P*g[i])%P;
	ans = ans*2%P;
	REP(i,1,n) ans = (ans-(ll)i*i%P*f[i]%P*f[i]%P*qpow(2,(ll)i*i%(P-1)))%P;
	if (ans<0) ans += P;
	printf("%d\n", ans);
}

int main() {
	REP(i,1,N-1) phi[i] = i;
	REP(i,2,N-1) if (phi[i]==i) {
		for (int j=i, t=i-1; j<N; j+=i) {
			phi[j] = phi[j]/j*t;
		}
	}
	int t;
	scanf("%d", &t);
	while (t--) work();
}

 

D. Robots

假设点$x$到$n$期望天数为${dp}_x$, $x$到$n$期望花费为${ans}_x$, 那么有

$${dp}_x=\frac{\sum{dp}_y+{dp}_x}{{deg}_x+1}+1$$

$${ans}_x=\frac{\sum{ans}_y+{ans}_x}{{deg}_x+1}+{dp}_x$$

第二个式子就是把费用提前计算. 因为是有向无环图, 可以建反向图, 然后拓排求出. 最终答案为${ans}_1$

#include <iostream>
#include <sstream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <cstring>
#include <bitset>
#include <functional>
#include <random>
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define PER(i,a,n) for(int i=n;i>=a;--i)
#define hr putchar(10)
#define pb push_back
#define lc (o<<1)
#define rc (lc|1)
#define mid ((l+r)>>1)
#define ls lc,l,mid
#define rs rc,mid+1,r
#define x first
#define y second
#define io std::ios::sync_with_stdio(false)
#define endl '\n'
#define DB(a) ({REP(__i,1,n) cout<<a[__i]<<' ';hr;})
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int P = 1e9+7, INF = 0x3f3f3f3f;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll qpow(ll a,ll n) {ll r=1%P;for (a%=P;n;a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;}
ll inv(ll x){return x<=1?1:inv(P%x)*(P-P/x)%P;}
inline int rd() {int x=0;char p=getchar();while(p<'0'||p>'9')p=getchar();while(p>='0'&&p<='9')x=x*10+p-'0',p=getchar();return x;}
//head



const int N = 1e5+10;
int n, m, deg[N], tot[N];
vector<int> g[N];
double dp[N], ans[N];
queue<int> q;

void work() {
	scanf("%d%d",&n,&m);
	REP(i,0,n+1) g[i].clear(), deg[i] = tot[i] = dp[i] = ans[i] = 0;
	REP(i,1,m) {
		int u, v;
		scanf("%d%d",&u,&v);
		g[v].pb(u), ++deg[u], ++tot[u];
	}
	q.push(n);
	while (q.size()) {
		int u = q.front(); q.pop();
		if (u!=n) {
			dp[u] = (dp[u]+1+tot[u])/tot[u];
			ans[u] = (ans[u]+dp[u]+1+tot[u])/tot[u];
		}
		for (auto v:g[u]) {
			dp[v] += dp[u];
			ans[v] += ans[u]+dp[u];
			if (!--deg[v]) { 
				q.push(v);
			}
		}
	}
	printf("%.2lf\n",ans[1]);
}
int main() {
	int t;
	scanf("%d", &t);
	while (t--) work();
}

 

E. K sum

枚举$gcd$, 莫比乌斯反演一下可以得到$f_n(k)=\sum\limits_{i=1}^n i^2 \sum\limits_{d=1}^{\lfloor\frac{n}{i}\rfloor}\mu(d)\lfloor\frac{n}{id}\rfloor ^k$

比赛的时候推到这里就不会了, 这种题还是做的太少了.

然后可以枚举$id$, 就有$f_n(k)=\sum\limits_{i=1}^n\lfloor\frac{n}{i}\rfloor^k\sum\limits_{d|i}\mu(d)(\frac{i}{d})^2$

再交换一下求和次序, 就得到$\sum\limits_{i=2}^k f_n(i)=\sum\limits_{j=1}^n(\sum\limits_{i=2}^k\lfloor\frac{n}{j}\rfloor^i)(\sum\limits_{d|j}\mu(d)(\frac{j}{d})^2)$

左边是等比数列可以$O(log)$求和, 特判下公比为一的情况. 右边是$\mu * Id^2$, 可以用杜教筛求和.

#include <iostream>
#include <sstream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <cstring>
#include <bitset>
#include <functional>
#include <random>
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define PER(i,a,n) for(int i=n;i>=a;--i)
#define hr putchar(10)
#define pb push_back
#define lc (o<<1)
#define rc (lc|1)
#define mid ((l+r)>>1)
#define ls lc,l,mid
#define rs rc,mid+1,r
#define x first
#define y second
#define io std::ios::sync_with_stdio(false)
#define endl '\n'
#define DB(a) ({REP(__i,1,n) cout<<a[__i]<<' ';hr;})
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int P = 1e9+7, INF = 0x3f3f3f3f;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll qpow(ll a,ll n) {ll r=1%P;for (a%=P;n;a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;}
ll inv(ll x){return x<=1?1:inv(P%x)*(P-P/x)%P;}
inline int rd() {int x=0;char p=getchar();while(p<'0'||p>'9')p=getchar();while(p>='0'&&p<='9')x=x*10+p-'0',p=getchar();return x;}
//head


const int N = 1e5+10;
const int inv6 = 166666668;
const int N2 = 5e6+10;
int cnt,f[N2],p[N2],vis[N2];
map<int,int> S2;
int n, k;
char s[N];

void init() {
    f[1] = 1;
    REP(i,2,N2-1) {
        if (!vis[i]) p[++cnt]=i,f[i] = ((ll)i*i-1)%P;
        for (int j=1,t;j<=cnt&&i*p[j]<N2; ++j) {
            vis[t=i*p[j]] = 1;
            if (i%p[j]==0) {f[t]=(ll)f[i]*p[j]%P*p[j]%P;break;}
            f[t] = (ll)f[i]*f[p[j]]%P;
        }
    }
	REP(i,2,N2-1) f[i] = (f[i]+f[i-1])%P;
}
int g(int n) {return 1;}
int sum_g(int n) {return n;}
int sum_fg(int n) {return (ll)n*(n+1)%P*(2*n+1)%P*inv6%P;}

int sum(int n) {
    if (n<N2) return f[n];
    if (S2.count(n)) return S2[n];
    int ans = sum_fg(n), mx = sqrt(n);
    REP(i,2,mx) ans=(ans-(ll)g(i)*sum(n/i))%P;
    for (int i=mx+1,j,k=n/i; i<=n; i=j+1,--k) {
        j = n/k;
        ans = (ans-(ll)(sum_g(j)-sum_g(i-1))*sum(k))%P;
    }
    return S2[n]=ans;
}

void work() {
	scanf("%d%s", &n, s+1);
	int len = strlen(s+1);
	int k_minus = 0, k_plus = 0;
	REP(i,1,len) { 
		k_minus = (k_minus*10ll+s[i]-'0')%P;
		k_plus = (k_plus*10ll+s[i]-'0')%(P-1);
	}
	k_plus = (k_plus+1)%(P-1);
	k_minus = (k_minus-1)%P;
	int ans = 0;
	for (int i=1,j; i<=n; i=j+1) { 
		int t = n/i;
		j = n/t;
		int ret;
		if (t==1) ret = k_minus;
		else ret = (qpow(t,k_plus)-(ll)t*t)%P*inv(t-1)%P;
		ans = (ans+(ll)(sum(j)-sum(i-1))*ret)%P;
	}
	if (ans<0) ans += P;
	printf("%d\n", ans);
}

int main() {
	init();
	int t;
	scanf("%d", &t);
	while (t--) work();
}

 

F. Greedy Sequence

先滑窗求出每个点后继, 然后$dp$求出每个点开头的最长路就行了.

#include <iostream>
#include <sstream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <cstring>
#include <bitset>
#include <functional>
#include <random>
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define PER(i,a,n) for(int i=n;i>=a;--i)
#define hr putchar(10)
#define pb push_back
#define lc (o<<1)
#define rc (lc|1)
#define mid ((l+r)>>1)
#define ls lc,l,mid
#define rs rc,mid+1,r
#define x first
#define y second
#define io std::ios::sync_with_stdio(false)
#define endl '\n'
#define DB(a) ({REP(__i,1,n) cout<<a[__i]<<' ';hr;})
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int P = 1e9+7, INF = 0x3f3f3f3f;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll qpow(ll a,ll n) {ll r=1%P;for (a%=P;n;a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;}
ll inv(ll x){return x<=1?1:inv(P%x)*(P-P/x)%P;}
inline int rd() {int x=0;char p=getchar();while(p<'0'||p>'9')p=getchar();while(p>='0'&&p<='9')x=x*10+p-'0',p=getchar();return x;}
//head



const int N = 1e5+10;
int n, k, a[N], nxt[N], dp[N];

int dfs(int x) {
	if (dp[x]!=-1) return dp[x];
	if (nxt[x]==-1) return dp[x]=1;
	return dp[x]=dfs(nxt[x])+1;
}
void work() {
	scanf("%d%d", &n, &k);
	k = min(k, n-1);
	REP(i,1,n) scanf("%d", a+i);
	set<pii> s;
	REP(i,1,k+1) s.insert(pii(a[i],i));
	REP(i,1,n) dp[i] = nxt[i] = -1;
	REP(i,1,n) {
		auto t = s.lower_bound(pii(a[i],i));
		if (t!=s.begin()) nxt[a[i]] = a[(--t)->y];
		if (i-k>=1) s.erase(pii(a[i-k],i-k));
		if (i+k+1<=n) s.insert(pii(a[i+k+1],i+k+1));
	}
	REP(i,1,n) printf("%d%c",dfs(i)," \n"[i==n]);
}

int main() {
	int t;
	scanf("%d", &t);
	while (t--) work();
}

 

 

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部