Lähetit

#include <iostream>
typedef long long ll;
const ll MOD = 1e9+7;
using namespace std;
ll dp[101][101];
ll dp2[101][101];
int main() {
    int n,k;
    cin>>n>>k;
    if(n%2 == 0) { 
        dp[1][0] = 1;
        dp[1][1] = 2;
        for(int i = 3; i < n; i += 2) {
            for(int j = 0; j <= i-2; ++j) {
                int left = i-j;
                dp[i][j] += dp[i-2][j];
                dp[i][j] %= MOD;
                dp[i][j+1] += dp[i-2][j]*left*2;
                dp[i][j+1] %= MOD;
                dp[i][j+2] += dp[i-2][j] * left %MOD  * (left-1);
                dp[i][j+2] %= MOD;
            }
        }
        ll ans = 0;
        for(int i = 0; i <= k; ++i) {
            ans += dp[n-1][i] * dp[n-1][k-i];
            ans %= MOD;
        }
        cout<<ans<<'\n';
    }
    else {
        dp[1][0] = 1;
        dp[1][1] = 2;
        for(int i = 3; i < n; i += 2) {
            for(int j = 0; j <= i-2; ++j) {
                int left = i-j;
                dp[i][j] += dp[i-2][j];
                dp[i][j] %= MOD;
                dp[i][j+1] += dp[i-2][j]*left*2;
                dp[i][j+1] %= MOD;
                dp[i][j+2] += dp[i-2][j] * left %MOD  * (left-1);
                dp[i][j+2] %= MOD;
            }
        }
        for(int j = 0; j <= n-2; ++j) {
            int left = n-j;
            dp[n-1][j] += dp[n-2][j];
            dp[n-1][j] %= MOD;
            dp[n-1][j+1] += dp[n-2][j]*left;
            dp[n-1][j+1] %= MOD;
        }
        dp2[1][0] = 1;
        dp2[1][1] = 4;
        dp2[1][2] = 2;
        for(int i = 3; i < n; i += 2) {
            for(int j = 0; j <= i-1; ++j) {
                int left = i+1-j;
                dp2[i][j] += dp2[i-2][j];
                dp2[i][j] %= MOD;
                dp2[i][j+1] += dp2[i-2][j]*left*2;
                dp2[i][j+1] %= MOD;
                dp2[i][j+2] += dp2[i-2][j] * left %MOD  * (left-1);
                dp2[i][j+2] %= MOD;
            }
        }
        ll ans = 0;
        for(int i = 0; i <= k; ++i) {
            ans += dp[n-1][i] * dp2[n-2][k-i];
            ans %= MOD;
        }
        cout<<ans<<'\n';
    }
}

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: ACCEPTED

Test 4

Group: 1

Verdict: ACCEPTED

Test 5

Group: 1

Verdict: ACCEPTED

Test 6

Group: 2

Verdict: ACCEPTED

Test 7

Group: 2

Verdict: ACCEPTED

Test 8

Group: 2

Verdict: ACCEPTED

Test 9

Group: 2

Verdict: ACCEPTED

Test 10

Group: 2

Verdict: ACCEPTED

Test 11

Group: 3

Verdict: ACCEPTED

Test 12

Group: 3

Verdict: ACCEPTED

Test 13

Group: 3

Verdict: ACCEPTED

Test 14

Group: 3

Verdict: ACCEPTED

Test 15

Group: 3

Verdict: ACCEPTED