CSES - HIIT Open 2016 - Results
Submission details
Task:Kaaleppi's puzzle
Sender:Ace of Spades
Submission time:2016-05-28 14:14:36 +0300
Language:C++
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.06 sdetails
#2ACCEPTED0.06 sdetails
#3ACCEPTED0.07 sdetails

Code

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int MN = 1111;
const int MOD = 1e9+7;
int ans[MN];
ll dp[3][MN][2]; //e, v

int main(void) {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(12);
    dp[1][0][0] = 1;
    ans[1] = 1;
    for(int i = 2; i <= 1111; ++i) {
        for(int j = 0; j < i; ++j) {
            dp[2][j+1][1] += 2*dp[1][j][0];
            dp[2][j+1][1] %= MOD;

            if(j > 0) {
                dp[2][j-1][0] += dp[1][j][0]*j;
                dp[2][j-1][0] %= MOD;
            }
            int q = i-2-j;
            dp[2][j][0] += q*dp[1][j][0];
            dp[2][j][0] %= MOD;
            if(j > 0) {
                dp[2][j][1] += dp[1][j][1];
                dp[2][j][1] %= MOD;


                int w = i-1-j;
                dp[2][j][0] += dp[1][j][1]*w;
                dp[2][j][0] %= MOD;

                dp[2][j+1][1] += dp[1][j][1];
                dp[2][j+1][1] %= MOD;

                dp[2][j-1][0] += dp[1][j][1] * (j-1);
                dp[2][j-1][0] %= MOD;
            }
        }
        for(int j = 0; j < MN; ++j) {
            for(int k = 0; k < 2; ++k) {
                dp[1][j][k] = dp[2][j][k];
                dp[2][j][k] = 0;
            }
        }
        ans[i] = dp[1][0][0];
    }
    int tt;
    cin>>tt;
    for(int i = 0; i < tt; ++i) {
        int q;
        cin>>q;
        cout<<ans[q]<<'\n';
    }
}

Test details

Test 1

Verdict: ACCEPTED

input
20
1
2
3
4
...

correct output
1
0
0
2
14
...

user output
1
0
0
2
14
...

Test 2

Verdict: ACCEPTED

input
20
981
982
983
984
...

correct output
436438246
92806357
21003215
151460560
326076265
...

user output
436438246
92806357
21003215
151460560
326076265
...

Test 3

Verdict: ACCEPTED

input
20
352
478
99
92
...

correct output
552481822
246955132
94569313
829032275
94621650
...

user output
552481822
246955132
94569313
829032275
94621650
...