BZOJ 4484: [Jsoi2015]最小表示(拓扑排序+bitset)

解题思路

　　\(bitset\)维护连通性，给每个点开个\(bitset\)，第\(i\)位为\(1\)则表示与第\(i\)位联通。算答案时显然要枚举每条边，而枚举边的顺序需要贪心，一个点先到达的点一定做出的贡献最大，那么就可以先求出拓扑序，然后每个点的儿子按照拓扑序排序。之后倒序枚举每个点确定答案。

代码

#include<bits/stdc++.h>

using namespace std;

const int MOD=1004535809;

const int N=1000005;

typedef long long LL;

int n,k,m,fac[N],inv[N],ans;

inline int fast_pow(int x,int y){

	int ret=1;

	for(;y;y>>=1){

		if(y&1) ret=(LL)ret*x%MOD;

		x=(LL)x*x%MOD;

	}

	return ret;

}

inline int C(int x,int y){

	return (LL)fac[x]*inv[y]%MOD*inv[x-y]%MOD;

}	

int main(){

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

	fac[0]=fac[1]=1;

	for(int i=2;i<=n;i++) fac[i]=(LL)fac[i-1]*i%MOD;

	inv[n]=fast_pow(fac[n],MOD-2);

	for(int i=n-1;~i;i--) inv[i]=(LL)inv[i+1]*(i+1)%MOD;

	for(int i=m;i<=n;i+=k)

		ans=(ans+C(n,i))%MOD;

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

	return 0;

}

巴特西

BZOJ 4484: [Jsoi2015]最小表示(拓扑排序+bitset)

解题思路

代码

最新文章

热门文章