Submission #509639

#	Time	Username	Problem	Language	Result	Execution time	Memory
509639		socpite	NoM (RMI21_nom)	C++14	100 / 100	327 ms	251780 KiB

Main

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

#define f first
#define s second

const int maxn = 4e3+5;
const int mod = 1e9+7;

typedef long long ll;

int n, m;

ll dp[maxn][maxn][2];
int pos[maxn];

ll f(int i, int j, int k){
    if(i == n)return k==0;
    else if(dp[i][j][k] != -1)return dp[i][j][k];
    else{
        int gap = pos[i]-i;
        dp[i][j][k] = 0;
        int p2 = n/2 - j - (i-j)/2;
        if(p2)dp[i][j][k]+=f(i+1, j+1, k)*p2*2%mod;
        if(j)dp[i][j][k]+=f(i+1, j-1, k)*j%mod;
        if(gap >= 2)dp[i][j][k]+=f(i+2, j, k^1)*p2*2%mod*(gap-1)%mod;
        dp[i][j][k]%=mod;
        //cout << i << " " << j << " " << k << " " << dp[i][j][k] << endl;
        return dp[i][j][k];
    }
}

int main(){
    memset(dp, -1, sizeof(dp));
    cin >> n >> m;
    n*=2;
    int crr = 0;
    for(int i = 0; i < m-n%m; i++){
        int st = crr+n/m;
        for(int j = 0; j < n/m; j++)pos[crr++]=st;
    }
    for(int i = 0; i < n%m; i++){
        int st = crr+n/m+1;
        for(int j = 0; j < n/m+1; j++)pos[crr++]=st;
    }
    ll ans = f(0, 0, 0)- f(0, 0, 1);
    if(ans < 0)ans+=mod;
    cout << ans;
}

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 13 / 13
• Subtask 4: 18 / 18
• Subtask 5: 48 / 48