QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#91057#6137. Sub-cycle GraphyyyyxhRE 3ms2200kbC++171.2kb2023-03-26 22:18:052023-03-26 22:18:06

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-26 22:18:06]
  • 评测
  • 测评结果:RE
  • 用时:3ms
  • 内存:2200kb
  • [2023-03-26 22:18:05]
  • 提交

answer

#include <cstdio>
using namespace std;
template<typename T>
T read(){
	char c=getchar();T x=0;
	while(c<48||c>57) c=getchar();
	do x=(x<<1)+(x<<3)+(c^48),c=getchar();
	while(c>=48&&c<=57);
	return x;
}
typedef long long ll;
const int P=1000000007;
int qp(int a,int b=P-2){
	int res=1;
	while(b){
		if(b&1) res=(ll)res*a%P;
		a=(ll)a*a%P;b>>=1;
	}
	return res;
}
int fac[100003],fiv[100003];
int comb(int a,int b){
	return (ll)fac[a]*fiv[b]%P*fiv[a-b]%P;
}
void inc(int &x,int v){if((x+=v)>=P) x-=P;}
void dec(int &x,int v){if((x-=v)<0) x+=P;}
int main(){
	int tc=read<int>();
	fac[0]=1;
	for(int i=1;i<=100000;++i) fac[i]=(ll)fac[i-1]*i%P;
	fiv[100000]=qp(fac[100000]);
	for(int i=100000;i;--i) fiv[i-1]=(ll)fiv[i]*i%P;
	while(tc--){
		int n=read<int>();
		ll m=read<ll>();
		if(m>n){puts("0");continue;}
		if(m==n){printf("%d\n",fac[n-1]);continue;}
		m=n-m;
		int pw=1,res=0;
		for(int i=0;i<=m;++i){
			if((m^i)&1) dec(res,(ll)comb(m,i)*pw%P*comb(n-m+i-1,m-1)%P);
			else inc(res,(ll)comb(m,i)*pw%P*comb(n-m+i-1,m-1)%P);
			inc(pw,pw);
		}
		res=(ll)res*fiv[m]%P*fac[n]%P*qp((P+1)>>1,m)%P;
		printf("%d\n",res);
	}
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 3ms
memory: 2200kb

input:

3
4 2
4 3
5 3

output:

15
12
90

result:

ok 3 number(s): "15 12 90"

Test #2:

score: -100
Runtime Error

input:

17446
3 0
3 1
3 2
3 3
4 0
4 1
4 2
4 3
4 4
5 0
5 1
5 2
5 3
5 4
5 5
6 0
6 1
6 2
6 3
6 4
6 5
6 6
7 0
7 1
7 2
7 3
7 4
7 5
7 6
7 7
8 0
8 1
8 2
8 3
8 4
8 5
8 6
8 7
8 8
9 0
9 1
9 2
9 3
9 4
9 5
9 6
9 7
9 8
9 9
10 0
10 1
10 2
10 3
10 4
10 5
10 6
10 7
10 8
10 9
10 10
11 0
11 1
11 2
11 3
11 4
11 5
11 6
11 7
11...

output:

1
3
3
2
1
6
15
12
6
1
10
45
90
60
24
1
15
105
375
630
360
120
1
21
210
1155
3465
5040
2520
720
293849209
28
378
2940
13545
35280
45360
20160
5040
852231769
334709860
630
6552
42525
170100
393120
453600
181440
40320
337404719
203419777
990
13230
114345
643545
2286900
4762800
4989600
1814400
362880
24...

result: