Submission #499258

#	Time	Username	Problem	Language	Result	Execution time	Memory
499258		amunduzbaev	NoM (RMI21_nom)	C++14	100 / 100	177 ms	368 KiB

Main

#include "bits/stdc++.h"
using namespace std;
 
#define ar array
 
const int mod = 1e9 + 7;
 
int pre[5][5] = {
    {0, 2, 2, 2, 2},
    {0, 16, 16, 24, 24},
    {0, 288, 384, 480, 576},
    {0, 9216, 13824, 23040, 26112},
    {0, 460800, 829440, 1428480, 2088960}
};
 
int bp(int a, int b){
    int rr = 1;
    while(b){
        if(b&1) rr = rr * 1ll * a % mod;
        a = a * 1ll * a % mod, b >>= 1; 
    } return rr;
}
 
signed main(){
    ios::sync_with_stdio(0); cin.tie(0);
    
    int n, m; cin>>n>>m;
    vector<int> a(m);
    for(int i=0;i<2*n;i++){
        a[i % m]++;
    }
    
    vector<int> dp(2 * n + 1);
    vector<int> f(2 * n + 1), inv(2 * n + 1);
    f[0] = inv[0] = 1;
    for(int i=1;i<=2 * n;i++){
        f[i] = f[i-1] * 1ll * i % mod;
        inv[i] = bp(f[i], mod - 2);
    }
    auto C = [&](int n, int k){
        return f[n] * 1ll * inv[k] % mod * inv[n - k] % mod;
    };
    reverse(a.begin(), a.end());
    dp[a[0]] = 1;
    int sum = a[0];
 
    for(int i=1;i<m;i++){
        vector<int> nw(2 * n + 1);
        for(int j=0;j<=a[i];j++){
            for(int l=j;l<=sum;l++){
                nw[l + a[i] - j * 2] = (nw[l + a[i] - 2 * j] + dp[l] * 1ll * f[j] % mod * C(a[i], j) % mod * C(l, j)) % mod;
            }
        } dp = nw;
        sum += a[i];
    }
    
    int res = dp[0];
    for(int i=0;i<n;i++) res = res * 2ll % mod;
    res = res * 1ll * f[n] % mod;
    cout<<res<<"\n";
}
 

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