QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#94431#6137. Sub-cycle GraphxuzhihaodedieTL 29ms4868kbC++141.4kb2023-04-05 22:35:372023-04-05 22:35:40

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-05 22:35:40]
  • 评测
  • 测评结果:TL
  • 用时:29ms
  • 内存:4868kb
  • [2023-04-05 22:35:37]
  • 提交

answer

// Problem: E. Living Sequence
// Contest: Codeforces - Codeforces Round 863 (Div. 3)
// URL: https://codeforces.com/contest/1811/problem/E
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
const int N=1e5+10;
int fact[N],infact[N];
int qpow(int a,int b) {
	if(b==0) return 1;
	if(b&1) return a*qpow(a,b-1)%mod;
	else {
		int mul=qpow(a,b/2)%mod;
		return mul*mul%mod;
	}
}
void init() {
	fact[0]=infact[0]=1;
	for(int i=1;i<N;i++) {
		fact[i]=fact[i-1]*i%mod;
		infact[i]=qpow(fact[i],mod-2)%mod;
	}
}
int c(int n,int m) {
	if(n<m) return 0;
	if(n<0||m<0) return 0;
	return fact[n]*infact[n-m]%mod*infact[m]%mod;
}
void solve() {
	int n,m;
	cin>>n>>m;
	if(m>n) {
		cout<<0<<endl;
		return ;
	}
	if(m==0) {
		cout<<1<<endl;
		return ;
	}
	if(m==n) {
		if(n<=2) {
			cout<<0<<endl;
		} else {
			cout<<fact[n-1]*qpow(2,mod-2)%mod;
		}
		return ;
	}
	int ans=0;
	for(int t=0;t<=n-m;t++) {
		//if(n-m-t<0) continue;
		int res=c(n,t)*c(n-t,2*(n-m-t))%mod*c(m-1,n-m-t-1)%mod;
		int ret=fact[2*(n-m-t)]%mod*infact[n-m-t]%mod*qpow(qpow(2,n-m-t),mod-2)%mod;
		ans=(ans+ret*res%mod*fact[max(0ll,2*m+t-n)]%mod)%mod;
	}
	cout<<ans<<endl;
}
signed main() {
	int T=1;
	init();
	cin>>T;
	while(T--) {
		solve();
	}
}

详细

Test #1:

score: 100
Accepted
time: 29ms
memory: 4868kb

input:

3
4 2
4 3
5 3

output:

15
12
90

result:

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

Test #2:

score: -100
Time Limit Exceeded

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
11
6
15
12
31
10
45
90
60
121
15
105
375
630
360
601
21
210
1155
3465
5040
2520
3601
28
378
2940
13545
35280
45360
20160
25201
36
630
6552
42525
170100
393120
453600
181440
201601
45
990
13230
114345
643545
2286900
4762800
4989600
1814400
1814401
55
1485
24750
273735
2047815
10239075
32848200
...

result: