fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; ++i)
  3. #define fi first
  4. #define se second
  5. #define el "\n"
  6. #define pb push_back
  7. #define sz(a) (int)a.size()
  8. #define FILL(a, x) memset(a, x, sizeof(a))
  9.  
  10. using namespace std;
  11. typedef long long ll;
  12. typedef pair<int, int> ii;
  13. const int N = (int)1e6+3, MAX = (int)1e6;
  14. ll F1[N], F2[N];
  15. int mod, T;
  16. int C[2005][2005];
  17. bool p[N];
  18. vector<int> Prime;
  19.  
  20. ll Mu(ll a, ll b){
  21.    if (b == 0) return 1;
  22.    ll res = 1;
  23.    a %= mod;
  24.    while(b != 0){
  25.       if (b&1){
  26.          res *= a;
  27.          res %= mod;
  28.       }
  29.       a *= a;
  30.       a %= mod;
  31.       b = (b >> 1);
  32.    }
  33.    return res;
  34. }
  35.  
  36. void Build(){
  37.   F1[0] = 1;
  38.   FOR(i, 1, MAX) F1[i] = F1[i-1]*i%mod;
  39.   F2[MAX] = Mu(F1[MAX], mod - 2);
  40.   for(int i = MAX; i >= 1; i--) F2[i-1] = F2[i]*i%mod;
  41.   C[0][0] = 1;
  42.   FOR(i, 1, 2000){
  43.     C[0][i] = 1;
  44.     C[i][0] = 0;
  45.   }
  46.   FOR(i, 1, 2000)
  47.    FOR(j, 1, 2000){
  48.       if (i > j) C[i][j] = 0;
  49.       if (i == j) C[i][j] = 1;
  50.       if (i < j){
  51.         C[i][j] = C[i][j-1] + C[i-1][j-1];
  52.         if (C[i][j] >= mod) C[i][j] -= mod;
  53.       }
  54.    }
  55. }
  56.  
  57. ll Get1(int k, int n){
  58.   return (F1[n]*F2[k]%mod*F2[n-k]%mod)%mod;
  59. }
  60.  
  61. ll Get2(ll k, ll n){
  62.    n %= mod;
  63.    if (k > n) return 0;
  64.    ll res = F2[k];
  65.    FOR(i, 0, k-1) res = res*(n-i)%mod;
  66.    return res;
  67. }
  68.  
  69. void Solve1(){
  70.    Build();
  71.    while(T--){
  72.       ll n , m, k, res;
  73.       cin >> n >> m >> k;
  74.       if (n <= 2000){
  75.          res = C[k][n-1];
  76.       } else if (n <= 1e6) res = Get1(k, n-1);
  77.          else res = Get2(k, n-1);
  78.       res = (res*m)%mod;
  79.       res = res*Mu(m-1, k)%mod;
  80.       while(res < 0) res += mod;
  81.       cout << res << el;
  82.    }
  83. }
  84.  
  85. void Sieve(){
  86.    for(int i = 2; i*i <= MAX; i++)
  87.      if (!p[i])
  88.       for(int j = i*i; j <= MAX; j += i) p[j] = 1;
  89.    FOR(i, 2, MAX)
  90.     if (!p[i]) Prime.pb(i);
  91. }
  92.  
  93. int Tinh(int p, ll H){
  94.    int res = 0;
  95.    ll Tam = p;
  96.    while(Tam <= H){
  97.       res += H/Tam;
  98.       Tam *= p;
  99.    }
  100.    return res;
  101. }
  102.  
  103. void Solve2(){
  104.    Sieve();
  105.    while(T--){
  106.       ll n, m, k;
  107.       cin >> n >> m >> k;
  108.       ll res = 1;
  109.       for(int p : Prime){
  110.          if (p > n) break;
  111.          ll d = Tinh(p, n-1) - Tinh(p, k) - Tinh(p, n-k-1);
  112.          if (d > 0) res = res*Mu(p, d)%mod;
  113.       }
  114.       res = res*m%mod;
  115.       res = res*Mu(m-1, k)%mod;
  116.       cout << res << el;
  117.    }
  118. }
  119.  
  120. int main()
  121. {
  122.     ios_base::sync_with_stdio(false);
  123.     cin.tie(NULL);    cout.tie(NULL);
  124.     freopen("flowers.inp", "r", stdin);
  125.     freopen("flowers.out", "w", stdout);
  126.     cin >> T >> mod;
  127.     if (mod == 998244353) Solve1();
  128.      else Solve2();
  129.     return 0;
  130. }
  131.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/GaKnEV
language:
C++14 (clang 8.0)
created:
11 hours ago
visibility:
public

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!