A.count

本场比赛最难的题...

隔板法组合数容斥 xjb 搞搞就好了

//by Judge

#include<cstdio>

#include<iostream>

#define Rg register

#define fp(i,a,b) for(Rg int i=(a),I=(b)+1;i<I;++i)

#define fd(i,a,b) for(Rg int i=(a),I=(b)-1;i>I;--i)

#define ll long long

using namespace std;

const int mod=998244353;

const int M=1e7+3;

ll n; int m,k,mx,r,ans,fac[M],inv[M];

inline int mul(int x,int y){return 1ll*x*y%mod;}

inline void Pls(int& x,int y){if((x+=y)>=mod)x-=mod;}

inline int qpow(int x,int p=mod-2){ int s=1;

	for(;p;p>>=1,x=mul(x,x)) if(p&1) s=mul(s,x); return s;

}

inline int C(ll n,int m){

	if(n<mx) return mul(fac[n],mul(inv[m],inv[n-m]));

	Rg int s=inv[m]; fp(i,0,m-1) s=mul(s,(n-i)%mod); return s;

}

inline int f(int n){ if(n<0) return 0; int res=0,tp;

	fp(i,0,k) tp=mul(C(k,i),C(n-i*(m-1)+k-1,k-1)), // 选 i 个要放零头的，乘上其放置方案

		Pls(res,mul(i&1?mod-1:1,tp)); return res;

}

int main(){ scanf("%lld%d%d",&n,&m,&k);

	mx=k*m,r=n%m; if(!m) return !printf("0\n");

	fac[0]=1; fp(i,1,n) fac[i]=mul(fac[i-1],i);

	inv[n]=qpow(fac[n]); fd(i,n,1) inv[i-1]=mul(inv[i],i);

	fp(i,0,k) Pls(ans,mul(f(i*m+r-k),C((n-r)/m-i+k-1,k-1)));

	// 前面的 f ，求出零头放置方案（放到 k 个数上全都小于 m）

	// 后面的 C ，组合数解隔板法

	return !printf("%d\n",ans);

}

tree

很水的题 \(n^2\) 的复杂度，随便搜搜就好了

//by Judge

#include<cstdio>

#include<cstring>

#include<iostream>

#define Rg register

#define fp(i,a,b) for(Rg int i=(a),I=(b)+1;i<I;++i)

#define fd(i,a,b) for(Rg int i=(a),I=(b)-1;i>I;--i)

#define go(u) for(Rg int i=head[u],v=e[i].to;i;v=e[i=e[i].nxt].to)

#define open(S) freopen(S".in","r",stdin),freopen(S".out","w",stdout)

#define ll long long

using namespace std;

const int mod=998244353;

const int M=1e5+3;

typedef int arr[M];

#ifndef Judge

#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)

#endif

char buf[1<<21],*p1=buf,*p2=buf;

inline int Max(int x,int y){return x>y?x:y;}

inline int Min(int x,int y){return x<y?x:y;}

inline int mul(int x,int y){return 1ll*x*y%mod;}

inline void Pls(int& x,int y){if((x+=y)>=mod)x-=mod;}

inline int read(){ int x=0,f=1; char c=getchar();

	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;

	for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f;

} int n,x,y,root,ans,a[M]; int pat,head[M];

struct Edge{ int to,nxt; }e[M<<1];

inline void add(int u,int v){

	e[++pat]={v,head[u]},head[u]=pat;

	e[++pat]={u,head[v]},head[v]=pat;

}

void dfs(int u,int fa,int mn,int mx){

	if(u>=root) Pls(ans,mul(mn,mx));

	go(u) if(v^fa) dfs(v,u,Min(mn,a[v]),Max(mx,a[v]));

}

int main(){ n=read(); fp(i,1,n) a[i]=read();

	fp(i,2,n) x=read(),y=read(),add(x,y);

	fp(i,1,n) dfs(root=i,0,a[i],a[i]); return !printf("%d\n",ans);

}

distance

n·q ，水题，注意别炸精度就好了

//by Judge

#include<cstdio>

#include<cstring>

#include<iostream>

#define Rg register

#define fp(i,a,b) for(Rg int i=(a),I=(b)+1;i<I;++i)

#define fd(i,a,b) for(Rg int i=(a),I=(b)-1;i>I;--i)

#define go(u) for(Rg int i=head[u],v=e[i].to;i;v=e[i=e[i].nxt].to)

#define ll long long

using namespace std;

const int M=2003;

typedef int arr[M];

#ifndef Judge

#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)

#endif

char buf[1<<21],*p1=buf,*p2=buf;

inline void cmax(ll& x,ll y){if(x<y)x=y;}

inline int Min(ll x,ll y){return x<y?x:y;}

inline int read(){ int x=0,f=1; char c=getchar();

	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;

	for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f;

} char sr[1<<21],z[20];int CCF=-1,Z;

inline void Ot(){fwrite(sr,1,CCF+1,stdout),CCF=-1;}

inline void print(ll x,char chr='\n'){

	if(CCF>1<<20)Ot();if(x<0)sr[++CCF]=45,x=-x;

	while(z[++Z]=x%10+48,x/=10);

	while(sr[++CCF]=z[Z],--Z);sr[++CCF]=chr;

} int n,q,root; ll ans,dis[M][M];

int pat,head[M];

struct Edge{ int to,val,nxt; }e[M<<1];

inline void add(int u,int v,int w){

	e[++pat]={v,w,head[u]},head[u]=pat;

	e[++pat]={u,w,head[v]},head[v]=pat;

}

void dfs(int u,int fa,ll d){ dis[root][u]=d;

	go(u) if(v^fa) dfs(v,u,d+e[i].val);

}

int main(){ n=read(),q=read(); Rg int x,y,z;

	fp(i,2,n) x=read(),y=read(),z=read(),add(x,y,z);

	fp(i,1,n) dfs(root=i,0,0);

	while(q--){ x=read(),y=read(),ans=0;

		fp(i,1,n) cmax(ans,Min(dis[x][i],dis[y][i])); print(ans);

	} return Ot(),0;

}

巴特西

CSP-S全国模拟赛第二场【nan】

A.count

tree

distance

最新文章

热门文章

巴特西

CSP-S全国模拟赛第二场 【nan】

A.count

tree

distance

最新文章

热门文章

CSP-S全国模拟赛第二场【nan】