Advertisement
Guest User

Untitled

a guest
Dec 17th, 2021
245
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.26 KB | None | 0 0
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3.  
  4. #define ar array
  5.  
  6. const int mod = 1e9 + 7;
  7.  
  8. int pre[5][5] = {
  9.     {0, 2, 2, 2, 2},
  10.     {0, 16, 16, 24, 24},
  11.     {0, 288, 384, 480, 576},
  12.     {0, 9216, 13824, 23040, 26112},
  13.     {0, 460800, 829440, 1428480, 2088960}
  14. };
  15.  
  16. int bp(int a, int b){
  17.     int rr = 1;
  18.     while(b){
  19.         if(b&1) rr = rr * 1ll * a % mod;
  20.         a = a * 1ll * a % mod, b >>= 1;
  21.     } return rr;
  22. }
  23.  
  24. signed main(){
  25.     ios::sync_with_stdio(0); cin.tie(0);
  26.    
  27.     int n, m; cin>>n>>m;
  28.     vector<int> a(m);
  29.     for(int i=0;i<2*n;i++){
  30.         a[i % m]++;
  31.     }
  32.    
  33.     vector<int> dp(2 * n + 1);
  34.     vector<int> f(2 * n + 1), inv(2 * n + 1);
  35.     f[0] = inv[0] = 1;
  36.     for(int i=1;i<=2 * n;i++){
  37.         f[i] = f[i-1] * 1ll * i % mod;
  38.         inv[i] = bp(f[i], mod - 2);
  39.     }
  40.     auto C = [&](int n, int k){
  41.         return f[n] * 1ll * inv[k] % mod * inv[n - k] % mod;
  42.     };
  43.     reverse(a.begin(), a.end());
  44.     dp[a[0]] = 1;
  45.     int sum = a[0];
  46.  
  47.     for(int i=1;i<m;i++){
  48.         vector<int> nw(2 * n + 1);
  49.         for(int j=0;j<=a[i];j++){
  50.             for(int l=j;l<=sum;l++){
  51.                 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;
  52.             }
  53.         } dp = nw;
  54.         sum += a[i];
  55.     }
  56.    
  57.     int res = dp[0];
  58.     for(int i=0;i<n;i++) res = res * 2ll % mod;
  59.     res = res * 1ll * f[n] % mod;
  60.     cout<<res<<"\n";
  61. }
  62.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement