QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#153149#6803. A Math ProblemLFCodeAC ✓390ms1712kbC++142.0kb2023-08-29 14:51:032023-08-29 14:51:03

Judging History

你现在查看的是最新测评结果

  • [2023-08-29 14:51:03]
  • 评测
  • 测评结果:AC
  • 用时:390ms
  • 内存:1712kb
  • [2023-08-29 14:51:03]
  • 提交

answer

#include<cstdio>
#define int long long
const int N=7,M=16,MOD=1e9+7;
int fac[N],ifac[N],s[N],vis[1<<M],f[M+1][M+1];
int Max(int a,int b){return a>b?a:b;}
int Min(int a,int b){return a<b?a:b;}
int Add(int &a,int b){return(a+=b)>=MOD?a-=MOD:a;}
int vAdd(int a,int b){return(a+=b)>=MOD?a-=MOD:a;}
int Sub(int &a,int b){return(a-=b)<0?a+=MOD:a;}
int vSub(int a,int b){return(a-=b)<0?a+=MOD:a;}
int Mul(int a,int b){return 1ll*a*b%MOD;}
int qpow(int a,int b){
	int ret=1;
	while(b){if(b&1)ret=Mul(ret,a);a=Mul(a,a);b>>=1;}
	return ret;
}
int read(){
	char ch=getchar();int nn=0,ssss=1;
	while(ch<'0'||ch>'9'){if(ch=='-')ssss*=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){nn=nn*10+(ch-'0');ch=getchar();}
	return nn*ssss;
}
bool prework(){
	fac[0]=1;for(int i=1;i<=6;i++)fac[i]=fac[i-1]*i;
	ifac[0]=1;for(int i=1;i<=6;i++)ifac[i]=qpow(fac[i],MOD-2);
	for(int i=1;i<=4;i++){
		int len=(1<<i);
		for(int j=0;j<(1<<len);j++){
			int cnt=0;
			s[0]=s[1]=s[2]=s[3]=0;
			for(int k=0;k<len;k++){
				if(!((j>>k)&1))continue;
				cnt++;
				for(int l=0;l<i;l++)if((k>>l)&1)s[l]|=1<<(cnt-1);
			}
			vis[(1<<cnt)-1]=vis[0]=1;
			for(int k=0;k<i;k++)vis[s[k]]++;
			bool flag=true;
			for(int x=0;x<i;x++){
				for(int y=x;y<i;y++)
					if(vis[s[x]|s[y]]!=1||vis[s[x]&s[y]]!=1){
						flag=false;
						break;
					}
				if(!flag)break;
			}
			vis[(1<<cnt)-1]=vis[0]=0;
			for(int k=0;k<i;k++)vis[s[k]]=0;
			f[cnt][i]+=flag;
		}
	}
	return true;
}
int C(int n,int m){int ret=1;for(int i=0;i<m;i++)ret=Mul(ret,n-i);return Mul(ret,ifac[m]);}
int calc(int n,int m){
	int ret=0;
	for(int i=0;i<m;i++)
		if(!(i&1))Add(ret,Mul(C(m,m-i),qpow(m-i,n)));
		else Sub(ret,Mul(C(m,m-i),qpow(m-i,n)));
	return ret;
}
bool solve(){
	int n=read();int m=read();int ans=0;
	if(m==2){puts("2");return true;}
	for(int i=1;i<=Min(n,1<<(m-2));i++)Add(ans,Mul(f[i][m-2],calc(n,i)));
	printf("%d\n",Mul(m*(m-1),ans));
	return true;
}
signed main(){
	prework();
	int T=read();
	while(T--)solve();
}

詳細信息

Test #1:

score: 100
Accepted
time: 4ms
memory: 1712kb

input:

9
2 2
2 3
3 3
3 4
4 4
4 5
5 5
5 6
6 6

output:

2
12
36
216
1032
7200
46800
453600
3369600

result:

ok 9 lines

Test #2:

score: 0
Accepted
time: 390ms
memory: 1700kb

input:

100000
2 2
2 3
3 3
3 4
4 4
4 5
5 5
5 6
6 6
68 3
1 6
25 6
59 5
65 4
46 2
28 3
92 3
43 2
37 4
5 3
54 4
83 4
17 3
96 5
27 4
39 3
13 6
100 4
95 2
12 5
34 4
65 5
12 3
69 5
45 4
58 4
60 4
42 5
79 6
36 3
43 2
7 5
43 2
49 6
6 3
30 2
51 2
2 3
49 5
24 6
55 6
41 3
77 3
9 3
40 6
24 3
39 4
83 5
42 6
16 5
59 6
31...

output:

2
12
36
216
1032
7200
46800
453600
3369600
905024371
0
322554998
502631271
394073985
2
610612717
452571193
2
399090507
180
439852597
873753978
786420
264505384
285295014
534860230
507878995
682724278
2
823421593
198087375
380858652
24564
261280150
166988729
814718007
562199150
685262393
202425164
31...

result:

ok 100000 lines