Submission #19700025


Source Code Expand

Copy
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define N 21
const int mod=1e9+7;
typedef long long ll;
inline ll read(){
	ll x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=(x<<1)+(x<<3)+c-'0';
		c=getchar();
	}
	return x*f;
}
int n,m,fac[N*N],ifac[N*N],x[N*N],y[N*N],all;
int qpow(int a,int b){
	int ans=1;
	while(b){
		if(b&1)ans=1LL*ans*a%mod;
		a=1LL*a*a%mod;
		b>>=1;
	}
	return ans;
}
void init(int n){
	fac[0]=1;
	for(int i=1;i<=n;++i){
		fac[i]=1LL*fac[i-1]*i%mod;
	}
	ifac[n]=qpow(fac[n],mod-2);
	for(int i=n-1;i>=0;--i){
		ifac[i]=1LL*ifac[i+1]*(i+1)%mod;
	}
}
struct state{
	int n,b,c,s; //���г��ȣ�������������и������������еĺ���λ��֮�� 
}dp[1<<N];
struct Union_Set{
	int f[N];
	void init(int n){
		for(int i=1;i<=n;++i){
			f[i]=i;
		}
	}
	inline int getf(int x){
		return f[x]==x?x:f[x]=getf(f[x]);
	}
	void Merge(int x,int y){
		int fx=getf(x),fy=getf(y);
		if(fx==fy)return;
		f[fy]=fx;
	}
}S;
int main(){
	n=read(),m=read(),all=(1<<n-1)-1;
	init(m+1);
	for(int i=1;i<=m;++i){
		x[i]=read(),y[i]=read();
	}
	for(int i=0;i<=all;++i){
		S.init(n);
		dp[i].b=n-1,dp[i].n=m;
		for(int j=1;j<n;++j){
			if((i>>j-1)&1){
				S.Merge(x[j],y[j]);
				--dp[i].b,--dp[i].n;
			}
		}
		for(int j=n;j<=m;++j){
			if(S.getf(x[j])==S.getf(y[j])){
				--dp[i].n;
			}
		}
	}
	dp[all].c=1;
	for(int i=all-1;i>=0;--i){
		for(int j=1;j<=n;++j){
			if((i>>j-1)&1)continue;
			int t=i|(1<<j-1);
			int k=dp[i].n-dp[t].n-1;
			int c=1LL*dp[t].c*fac[dp[t].n+k]%mod*ifac[dp[t].n]%mod;
			int s=(1LL*dp[t].s*fac[dp[t].n+k+1]%mod*ifac[dp[t].n+1]%mod+1LL*dp[i].b*c)%mod;
			dp[i].c=(dp[i].c+c)%mod;
			dp[i].s=(dp[i].s+s)%mod;
		}
	}
	printf("%d\n",dp[0].s);
	return 0;
}



Submission Info

Submission Time
Task F - Edge Ordering
User luogu_bot3
Language C++ (GCC 9.2.1)
Score 1200
Code Size 1934 Byte
Status AC
Exec Time 882 ms
Memory 11872 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:61:29: warning: suggest parentheses around ‘-’ inside ‘<<’ [-Wparentheses]
   61 |  n=read(),m=read(),all=(1<<n-1)-1;
      |                            ~^~
./Main.cpp:70:12: warning: suggest parentheses around ‘-’ inside ‘>>’ [-Wparentheses]
   70 |    if((i>>j-1)&1){
      |           ~^~
./Main.cpp:84:12: warning: suggest parentheses around ‘-’ inside ‘>>’ [-Wparentheses]
   84 |    if((i>>j-1)&1)continue;
      |           ~^~
./Main.cpp:85:17: warning: suggest parentheses around ‘-’ inside ‘<<’ [-Wparentheses]
   85 |    int t=i|(1<<j-1);
      |                ~^~

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1200 / 1200
Status
AC × 3
AC × 34
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All hand_01.txt, path_01.txt, path_02.txt, path_03.txt, path_04.txt, path_05.txt, rand_01.txt, rand_02.txt, rand_03.txt, rand_04.txt, rand_05.txt, rand_06.txt, rand_07.txt, rand_08.txt, rand_09.txt, rand_10.txt, rand_11.txt, rand_12.txt, rand_13.txt, rand_14.txt, rand_15.txt, rand_16.txt, rand_17.txt, rand_18.txt, rand_19.txt, rand_20.txt, sample_01.txt, sample_02.txt, sample_03.txt, star_01.txt, star_02.txt, star_03.txt, star_04.txt, star_05.txt
Case Name Status Exec Time Memory
hand_01.txt AC 5 ms 3456 KB
path_01.txt AC 821 ms 11764 KB
path_02.txt AC 263 ms 11868 KB
path_03.txt AC 382 ms 11704 KB
path_04.txt AC 6 ms 3664 KB
path_05.txt AC 47 ms 5652 KB
rand_01.txt AC 845 ms 11832 KB
rand_02.txt AC 872 ms 11648 KB
rand_03.txt AC 848 ms 11724 KB
rand_04.txt AC 323 ms 11872 KB
rand_05.txt AC 157 ms 11840 KB
rand_06.txt AC 259 ms 11832 KB
rand_07.txt AC 6 ms 3648 KB
rand_08.txt AC 64 ms 5580 KB
rand_09.txt AC 2 ms 3748 KB
rand_10.txt AC 3 ms 3552 KB
rand_11.txt AC 882 ms 11752 KB
rand_12.txt AC 882 ms 11836 KB
rand_13.txt AC 844 ms 11840 KB
rand_14.txt AC 848 ms 11700 KB
rand_15.txt AC 860 ms 11868 KB
rand_16.txt AC 872 ms 11800 KB
rand_17.txt AC 855 ms 11752 KB
rand_18.txt AC 880 ms 11724 KB
rand_19.txt AC 856 ms 11868 KB
rand_20.txt AC 850 ms 11700 KB
sample_01.txt AC 2 ms 3636 KB
sample_02.txt AC 2 ms 3512 KB
sample_03.txt AC 17 ms 4004 KB
star_01.txt AC 812 ms 11748 KB
star_02.txt AC 249 ms 11724 KB
star_03.txt AC 387 ms 11648 KB
star_04.txt AC 3 ms 3548 KB
star_05.txt AC 46 ms 5724 KB