fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define mp make_pair
  5. #define pb push_back
  6. #define MOD 1000000007LL
  7. #define F first
  8. #define S second
  9. #define ll long long
  10.  
  11. typedef pair<int, int> pii;
  12. typedef pair<ll, ll> pll;
  13.  
  14. ll gcd(ll a, ll b)
  15. {
  16.     if(a == 0LL)
  17.         return b;
  18.     return gcd(b, a%b);
  19. }
  20.  
  21. const int N = 2003;
  22. ll pw2_m[N], pw_m[N], ifact[N], fact[N];
  23. ll dp[N][N], pw_inv[N][N];
  24.  
  25. ll modx(ll base, ll ex)
  26. {
  27.     ll ans = 1LL, val = base;
  28.     while(ex > 0LL)
  29.     {
  30.         if(ex&1LL)
  31.             ans = (ans*val)%MOD;
  32.         val = (val*val)%MOD;
  33.         ex = ex>>1LL;
  34.     }
  35.     return ans;
  36. }
  37.  
  38. int main()
  39. {   
  40.     // clock_t clk;
  41.     // clk = clock();
  42.  
  43.     // freopen("in8.in", "r", stdin);
  44.     // freopen("out8.out", "w", stdout);
  45.  
  46.     int n, cnt;
  47.     ll m, temp;
  48.  
  49.     scanf("%d", &n);
  50.     scanf("%lld", &m);
  51.  
  52.     pw2_m[0] = pw_m[0] = fact[0] = ifact[0] = 1LL;
  53.     for(int i = 1; i<=n; i++)
  54.     {
  55.         pw_m[i] = (pw_m[i-1]*m)%MOD;
  56.         pw2_m[i] = (pw_m[i]*pw_m[i])%MOD;
  57.         fact[i] = (fact[i-1]*((ll)i))%MOD;
  58.         ifact[i] = modx(fact[i], MOD-2LL);
  59.  
  60.         pw_inv[i][0] = 1LL;
  61.         pw_inv[i][1] = modx(i, MOD-2LL);
  62.         for(int j = 1; j<=n; j++)
  63.             pw_inv[i][j] = (pw_inv[i][j-1]*pw_inv[i][1])%MOD;
  64.     }
  65.  
  66.     // dp[i][j] -> i numbers are selected and max permutation cycle is of length j
  67.     for(int i = 0; i<=n; i++)
  68.         dp[0][i] = 1LL;
  69.  
  70.     for(int i = 1; i<=n; i++)
  71.     {
  72.         for(int j = 1; j<=n; j++)
  73.         {
  74.             dp[i][j] = dp[i][j-1];
  75.             cnt = 0;
  76.             for(int k = j; k<=i; k+=j)
  77.             {
  78.                 cnt++;
  79.  
  80.                 temp = (dp[i-k][j-1]*pw_inv[j][cnt])%MOD;
  81.                 temp = (temp*ifact[cnt])%MOD;
  82.  
  83.                 if(j&1) // Odd permutation cycle
  84.                     temp = (temp*pw_m[cnt])%MOD;
  85.                 else
  86.                     temp = (temp*pw2_m[cnt])%MOD;
  87.  
  88.                 dp[i][j] = (dp[i][j] + temp)%MOD;
  89.             }
  90.         }
  91.     }
  92.  
  93.     printf("%lld\n", (dp[n][n]*fact[n])%MOD);
  94.  
  95.     // printf("%.9Lf\n", ((long double)(clock() - clk))/CLOCKS_PER_SEC);
  96.  
  97.     return 0;
  98. }
Success #stdin #stdout 0s 4488KB
comments (?)
stdin
copy 
3 2
stdout
copy 
36
https://ideone.com/N4GHKS
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!