CSES - Putka Open 2015 – 1/6 - Results
Submission details
Task:Lähetit
Sender:
Submission time:2015-07-19 23:14:07 +0300
Language:C++
Status:READY
Result:88
Feedback
groupverdictscore
#10
#2ACCEPTED23
#3ACCEPTED65
Test results
testverdicttimegroup
#10.09 s1details
#20.07 s1details
#3ACCEPTED0.09 s1details
#4ACCEPTED0.08 s1details
#5ACCEPTED0.09 s1details
#6ACCEPTED0.08 s2details
#7ACCEPTED0.09 s2details
#8ACCEPTED0.08 s2details
#9ACCEPTED0.08 s2details
#10ACCEPTED0.09 s2details
#11ACCEPTED0.09 s3details
#12ACCEPTED0.09 s3details
#13ACCEPTED0.08 s3details
#14ACCEPTED0.08 s3details
#15ACCEPTED0.08 s3details

Code

#include <iostream>
using namespace std;
long long M=1000000007;
int n, k;

long long b[201][55];
long long w[201][55];


int main(){
  cin >> n >> k;
  if (k>2*n-1) cout << 0 << endl;
  else{
    for (int i=0; i<=n/2; ++i){b[0][i]=1; w[0][i]=1;}
    
    for (int a=1; a<n; ++a){
      //black
      for (int d=1; d<=(n+1)/2; ++d){
        int c=d*2-1;
        if (2*d!=n+1){
          b[a][d]=b[a][d-1]+b[a-1][d-1]*2*(c-a+1);
          if (a>1) b[a][d]+=b[a-2][d-1]*(c-a+2)*(c-a+1);
        }else{
          b[a][d]=b[a][d-1]+b[a-1][d-1]*(c-a+1);
        }
        b[a][d]%=M;
      }
      //white
      for (int d=1; d<=n/2; ++d){
        int c=d*2;
        if (2*d!=n){
          w[a][d]=w[a][d-1]+w[a-1][d-1]*2*(c-a+1);
          if (a>1) w[a][d]+=w[a-2][d-1]*(c-a+2)*(c-a+1);
        }else{
          w[a][d]=w[a][d-1]+w[a-1][d-1]*(c-a+1);
        }
        w[a][d]%=M;
      }
    }
    long long a=0;
    for (int i=0; i<=k; ++i){
      a+=w[i][n/2]*b[k-i][(n+1)/2];
      a%=M;
    }
    cout << a << endl;
  }
}

Test details

Test 1

Group: 1

Verdict:

input
5 2

correct output
240

user output
202

Test 2

Group: 1

Verdict:

input
5 4

correct output
2728

user output
2724

Test 3

Group: 1

Verdict: ACCEPTED

input
5 6

correct output
1960

user output
1960

Test 4

Group: 1

Verdict: ACCEPTED

input
5 8

correct output
32

user output
32

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: ACCEPTED

input
10 12

correct output
811277399

user output
811277399

Test 9

Group: 2

Verdict: ACCEPTED

input
10 16

correct output
17275136

user output
17275136

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: ACCEPTED

input
100 120

correct output
324216296

user output
324216296

Test 14

Group: 3

Verdict: ACCEPTED

input
100 160

correct output
895190039

user output
895190039

Test 15

Group: 3

Verdict: ACCEPTED

input
100 200

correct output
0

user output
0