CSES - Putka Open 2015 – 1/6 - Results
Submission details
Task:Lähetit
Sender:
Submission time:2015-07-18 17:03:23 +0300
Language:C++
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
Test results
testverdicttimegroup
#1ACCEPTED0.09 s1details
#2ACCEPTED0.08 s1details
#30.09 s1details
#40.09 s1details
#5ACCEPTED0.08 s1details
#6ACCEPTED0.10 s2details
#7ACCEPTED0.08 s2details
#80.09 s2details
#90.08 s2details
#10ACCEPTED0.08 s2details
#11ACCEPTED0.09 s3details
#12ACCEPTED0.08 s3details
#130.08 s3details
#140.08 s3details
#15ACCEPTED0.09 s3details

Code

#include <iostream>
using namespace std;
typedef long long ll;
ll dp[128][128];
const int Z = 1e9+7;
int main() {
	int n,k;
	cin>>n>>k;
	if (k>n) {
		cout<<0<<'\n';
		return 0;
	}
	if (n==1||k==0) {
		cout<<1<<'\n';
		return 0;
	}
	dp[0][0]=1;
	dp[1][0]=1;
	dp[1][1]=2;
	for(int i=2; i<n; ++i) {
		dp[i][0]=dp[i+2][0];
		for(int j=0; j<=i; ++j) {
			dp[i][j] += dp[i-2][j];
			if (j>0) dp[i][j] += 2*(i-j+1)*dp[i-2][j-1];
			if (j>1) dp[i][j] += (i-j+2)*(i-j+1)*dp[i-2][j-2];
			dp[i][j]%=Z;
		}
	}
	for(int i=0; i<=n; ++i) dp[n][i]=(dp[n-2][i]+(i>0 ? (n-i+1)*dp[n-2][i-1] : 0))%Z;
	ll res=0;
	for(int i=0; i<=k; ++i) res+=dp[n-1][i]*dp[n][k-i],res%=Z;
	cout<<res<<'\n';
}

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
5 2

correct output
240

user output
240

Test 2

Group: 1

Verdict: ACCEPTED

input
5 4

correct output
2728

user output
2728

Test 3

Group: 1

Verdict:

input
5 6

correct output
1960

user output
0

Test 4

Group: 1

Verdict:

input
5 8

correct output
32

user output
0

Test 5

Group: 1

Verdict: ACCEPTED

input
5 10

correct output
0

user output
0

Test 6

Group: 2

Verdict: ACCEPTED

input
10 4

correct output
1809464

user output
1809464

Test 7

Group: 2

Verdict: ACCEPTED

input
10 8

correct output
209594075

user output
209594075

Test 8

Group: 2

Verdict:

input
10 12

correct output
811277399

user output
0

Test 9

Group: 2

Verdict:

input
10 16

correct output
17275136

user output
0

Test 10

Group: 2

Verdict: ACCEPTED

input
10 20

correct output
0

user output
0

Test 11

Group: 3

Verdict: ACCEPTED

input
100 40

correct output
126883191

user output
126883191

Test 12

Group: 3

Verdict: ACCEPTED

input
100 80

correct output
785497039

user output
785497039

Test 13

Group: 3

Verdict:

input
100 120

correct output
324216296

user output
0

Test 14

Group: 3

Verdict:

input
100 160

correct output
895190039

user output
0

Test 15

Group: 3

Verdict: ACCEPTED

input
100 200

correct output
0

user output
0