CSES - Datatähti 2025 alku - Results
Submission details
Task:Kortit II
Sender:maweiyin24562
Submission time:2024-11-02 17:57:46 +0200
Language:C++ (C++11)
Status:READY
Result:34
Feedback
groupverdictscore
#1ACCEPTED3
#2ACCEPTED5
#3ACCEPTED26
#40
#50
Test results
testverdicttimegroup
#1ACCEPTED0.03 s1, 2, 3, 4, 5details
#2ACCEPTED0.03 s2, 3, 4, 5details
#3ACCEPTED0.03 s3, 4, 5details
#40.04 s4, 5details
#5--5details
#6--5details

Code

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MOD=1000000007;
const ll N=2009;

ll C(ll m,ll n){
	ll res=1;
	for(ll i=1,j=m;i<=m-n;i++,j--){
		res*=j;
		res/=i;
		res%=MOD;
	}
	return res;
}
ll P(ll n,ll m){
	ll res=1;
	for(ll i=n;i>n-m;i--){
		res*=i;
		res%=MOD;
	}
	return res;
}
void M(ll&a,ll b){
	a=a*b%MOD;
}

ll ans=1;
ll base[N];
ll dp[N][N];

void query(ll n,ll a,ll b){
	if(a<b)swap(a,b);
	ll c=a+b;
	for(ll i=a;i<=c;i++){
		ll sum=0;
		for(ll j=0;j<i-a;j++){
			sum+=base[j]*C(i,j+a);
			sum%=MOD;
		}
		base[i-a]=dp[i][a]+2*MOD-sum;
		base[i-a]%=MOD;
	}
	M(ans,base[b]);M(ans,P(n,n));
	cout<<ans%MOD<<endl;
}

int main(){
	for(int i=1;i<=2005;i++){
        dp[i][0]=1;
        dp[i][i]=0;
        for(int j=1;j<i;j++){
        	dp[i][j]+=((j+1)*dp[i-1][j]+(i-j)*dp[i-1][j-1]);
        	dp[i][j]%=MOD;
		}
    }
	ll Q;
	cin>>Q;
	while(Q--){
		ans=1;
		memset(base,0,sizeof(base));
		ll n,a,b;
		cin>>n>>a>>b;
		ll c=a+b;
		if(a==0&&b==0){
			cout<<P(n,n)%MOD<<endl;
			continue;
		}
		else if(c>n){
			cout<<0<<endl;
			continue;
		}
		else if(c<n){
			M(ans,C(n,c));
		}
		query(n,a,b);
	}
	return 0;
}

Test details

Test 1

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

input
54
4 4 0
3 1 3
3 2 2
4 0 4
...

correct output
0
0
0
0
0
...

user output
0
0
0
0
0
...

Test 2

Group: 2, 3, 4, 5

Verdict: ACCEPTED

input
284
6 1 0
5 0 2
7 1 5
7 7 5
...

correct output
0
0
35280
0
36720
...

user output
0
0
35280
0
36720
...

Test 3

Group: 3, 4, 5

Verdict: ACCEPTED

input
841
19 3 12
19 19 13
19 7 13
20 11 15
...

correct output
40291066
0
0
0
0
...

user output
40291066
0
0
0
0
...

Test 4

Group: 4, 5

Verdict:

input
1000
15 12 6
7 1 6
44 4 26
6 6 5
...

correct output
0
5040
494558320
0
340694548
...

user output
0
5040
507327269
0
717810679
...

Test 5

Group: 5

Verdict:

input
1000
892 638 599
966 429 655
1353 576 1140
1403 381 910
...

correct output
0
0
0
249098285
0
...

user output
(empty)

Test 6

Group: 5

Verdict:

input
1000
2000 1107 508
2000 1372 249
2000 588 65
2000 1739 78
...

correct output
750840601
678722180
744501884
159164549
868115056
...

user output
(empty)