Submission #966968

#	Time	Username	Problem	Language	Result	Execution time	Memory
966968		AlperenT_	NoM (RMI21_nom)	C++14	100 / 100	184 ms	39676 KiB

Main

#include <bits/stdc++.h>

#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define S second 
#define ld long double
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define int long long 
#define PII pair<pii , pii>
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= (b);i++)
#define per(i , a , b) for(int i=a;i >= (b);i--)
#define deb(x) cout <<#x << " : " << x << "\n" ;
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 4000+10 + 10,  inf = 1e9+10 , mod = 1e9 + 7 ;
int f[maxn], inv[maxn] , dp[maxn][maxn] ;

int po(int a, int b){
    if(b==0)return 1 ;
    int v =po(a,b/2) ; 
    v = v*v % mod ;
    if(b&1) v= v*a % mod ;
    return v ;
}
int c(int n , int k){
    if(n < k || k < 0)return 0 ;
    return f[n]*inv[k]%mod*inv[n-k]%mod ;
}
int t[maxn] ;
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
    f[0] = 1;
    rep(i , 1,maxn-1)f[i] = f[i-1] *i % mod ;
    inv[maxn-1] = po(f[maxn-1] , mod-2) ;
    per(i , maxn-2 ,0){
        inv[i] = inv[i+1] * (i+1) % mod ;
    }
    int n , m;
    cin >> n >> m ;
    rep(i , 1, 2*n){
        t[(i-1)%m]++;
    }
    dp[0][0] = 1;
    rep(i , 1 ,m){
        rep(j ,0 ,n){
            rep(k , 0 , min(t[i-1] , j)){
                dp[i][j-k+(t[i-1] - k)] = (dp[i][j-k+(t[i-1]-k)] + dp[i-1][j] * c(t[i-1] , k)%mod * f[k]%mod * c(j , k)%mod)%mod ;
            }
        }
    }
    int ans = dp[m][0] * po(2,n)%mod *f[n]%mod;
    cout << ans<< "\n"; 
    return 0 ;
}
/*


*/

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