NOI2019省选模拟赛第三场

明明没参加过却因为点进去结果狂掉\(rating\)……

\(A\) 集合

如果我们记

\[f_k=\sum_{i=1}^nT^i{n-i\choose k}
\]

那么答案显然就是\(f_{k-1}\)

然后就可以开始推倒了

\[\begin{aligned}
f_k
&=\sum_{i=1}^nT^i{n-i\choose k}\\
&=\sum_{i=1}^nT^i{n-i-1\choose k}+\sum_{i=1}^nT^i{n-i-1\choose k-1}\\
&={1\over T}\sum_{i=2}^nT^i{n-i\choose k}+{1\over T}\sum_{i=2}^nT^i{n-i\choose k-1}\\
&={1\over T}\left(f_k-T{n-1\choose k}+f_{k-1}-T{n-1\choose k-1}\right)\\
&={1\over T}\left(f_k+f_{k-1}-T{n\choose k}\right)\\
\end{aligned}
\]

然后整理一下就可以得到

\[f_k={f_{k-1}-T{n\choose k}\over T-1}
\]

边界条件为\(f_0\)，显然是个等比数列求和的形式，为

\[f_0={T(1-T^n)\over 1-T}
\]

直接递推就行了

顺便注意如果\(T=1\)那么答案显然是\(1\)

//minamoto

#include<bits/stdc++.h>

#define R register

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

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

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

using namespace std;

const int N=1e7+5,P=998244353;

inline int add(R int x,R int y){return x+y>=P?x+y-P:x+y;}

inline int dec(R int x,R int y){return x-y<0?x-y+P:x-y;}

inline int mul(R int x,R int y){return 1ll*x*y-1ll*x*y/P*P;}

int ksm(R int x,R int y){

	R int res=1;

	for(;y;y>>=1,x=mul(x,x))(y&1)?res=mul(res,x):0;

	return res;

}

int inv[N],f[N],res,n,k,T,iv;

int main(){

//	freopen("testdata.in","r",stdin);

	scanf("%d%d%d",&n,&k,&T);

	inv[0]=inv[1]=1;fp(i,2,k)inv[i]=mul(P-P/i,inv[P%i]);

	if(T==1)return puts("1"),0;

	res=1,iv=ksm(T-1,P-2),f[0]=1ll*T*(P-iv)%P*(P+1-ksm(T,n))%P;

	fp(i,1,k){

		res=1ll*res*inv[i]%P*(n-i+1)%P,

		f[i]=mul(dec(f[i-1],mul(T,res)),iv);

	}

	res=ksm(res,P-2);

	printf("%d\n",mul(f[k-1],res));

	return 0;

}

\(B\) 染色

点分是个啥我好像已经给忘了……

要求所有同色点对距离的最小值介于 \([L,R]\) 之间，我们可以用最小值大于等于\(L\)的答案减去最小值大于等于\(R+1\)的答案

那么考虑形如最小值大于等于\(k+1\)的答案怎么算，这个的意思就是要求对于\(u\)来说，所有到它的距离小于等于\(k\)的点的颜色要和它不同

首先有一个结论：如果我们按\(BFS\)序加入点，设当前加入的点为\(u\)，且对另外两个已经加入的点\(x,y\)，满足\(dis(u,x)\leq k\)且\(dis(u,y)\leq k\)，则有\(dis(x,y)\leq k\)

证明：如果\(u\)到\(x,y\)的两条路径上没有分叉点，那么显然成立

如果有分叉点，我们记分叉点为\(w\)，那么显然\(x,y\)中有一个点是在\(w\)的子树里的，不妨假设它为\(x\)。因为是按\(BFS\)序加入，所以\(x\)的深度小于\(u\)，那么\(dis(x,w)\leq dis(u,w)\)，所以\(dis(x,y)\leq dis(u,y)\leq k\)

那么我们按\(BFS\)序加入点，对于每个点\(u\)，要满足所有和它距离不超过\(k\)的点的颜色互不相同，它的颜色也和它们不同

假设和它距离不超过\(k\)的点有\(s\)个，那么显然它的方案数就是\(m-s\)，其中\(m\)为颜色总数

所以要怎么求和它距离不超过\(k\)的点的个数呢……点分树就可以了……点分树怎么写我已经忘光了所以请看代码自行理解

//minamoto

#include<bits/stdc++.h>

#define R register

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

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

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

template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}

template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}

using namespace std;

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

inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}

int read(){

    R int res,f=1;R char ch;

    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);

    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');

    return res*f;

}

const int N=2e5+5,M=4e6+5,L=5e7+5,P=1e9+7;

inline int add(R int x,R int y){return x+y>=P?x+y-P:x+y;}

inline int dec(R int x,R int y){return x-y<0?x-y+P:x-y;}

inline int mul(R int x,R int y){return 1ll*x*y-1ll*x*y/P*P;}

struct eg{int v,nx;}e[N<<1];int head[N],tot;

inline void Add(R int u,R int v){e[++tot]={v,head[u]},head[u]=tot;}

int pool[L],*p=pool;

struct Bit{

	int n,*c;

	inline void upd(R int x){for(;x<=n;x+=x&-x)++c[x];}

	inline int query(R int x){int res=0;cmin(x,n);for(;x;x-=x&-x)res+=c[x];return res;}

}f[M];int cur;

struct Eg{int nx,dis,sgn;Bit *bi;}E[M];int Head[N],tc;

int sz[N],mx[N],dep[N],vis[N],q[N],fa[N];

int size,rt,n,m,l,r,res1,res2;

void findrt(int u,int fa){

	sz[u]=1,mx[u]=0;

	go(u)if(v!=fa&&!vis[v])findrt(v,u),sz[u]+=sz[v],cmax(mx[u],sz[v]);

	cmax(mx[u],size-sz[u]);

	if(mx[u]<mx[rt])rt=u;

}

void dfs(int u,int sgn,int d){

	int h=1,t=0;

	dep[u]=d,fa[u]=0,q[++t]=u;

	while(h<=t){

		u=q[h++];

		go(u)if(!vis[v]&&v!=fa[u])q[++t]=v,fa[v]=u,dep[v]=dep[u]+1;

		E[++tc]={Head[u],dep[u],sgn,&f[cur]},Head[u]=tc;

	}

	f[cur].c=p,f[cur].n=dep[q[t]]+1,p+=f[cur++].n;

}

void solve(int u){

	vis[u]=1;dfs(u,1,0);

	int s=size;

	go(u)if(!vis[v]){

		dfs(v,-1,1);

		rt=0,size=(sz[v]<sz[u])?sz[v]:s-sz[u],findrt(v,u);

		solve(rt);

	}

}

int main(){

//	freopen("testdata.in","r",stdin);

	n=read(),m=read(),l=read(),r=read();

	for(R int i=1,u,v;i<n;++i)u=read(),v=read(),Add(u,v),Add(v,u);

	mx[0]=n+1,rt=0,size=n,findrt(1,0),solve(rt);

	res1=res2=1,memset(vis,0,4*(n+1));

	int h=1,t=0;q[++t]=1,vis[1]=1;

	while(h<=t){

		int u=q[h++],s1=0,s2=0;

		for(int i=Head[u];i;i=E[i].nx){

			if(E[i].dis<l)s1+=E[i].bi->query(l-E[i].dis)*E[i].sgn;

			if(E[i].dis<r+1)s2+=E[i].bi->query(r+1-E[i].dis)*E[i].sgn;

			E[i].bi->upd(E[i].dis+1);

		}

		res1=mul(res1,m-s1),res2=mul(res2,m-s2);

		go(u)if(!vis[v])q[++t]=v,vis[v]=1;

	}

	printf("%d\n",dec(res1,res2));

	return 0;

}

\(C\) 高尔夫

听说这是个数据结构题而且\(std\)有\(5kb\)

算了咕咕了

巴特西

NOI2019省选模拟赛第三场

\(A\) 集合

\(B\) 染色

\(C\) 高尔夫

最新文章

热门文章

巴特西

NOI2019省选模拟赛 第三场

\(A\) 集合

\(B\) 染色

\(C\) 高尔夫

最新文章

热门文章

NOI2019省选模拟赛第三场