fork download 
  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)2e6+3, MAX = (int)2e6;
  14. int k, T, mod;
  15. int C[5005][5005];
  16. ll F1[N], F2[N];
  17. vector<int> Prime;
  18. bool p[N];
  19.  
  20. void Solve1(){
  21.    C[0][0] = 1;
  22.    FOR(i, 1, 5000){
  23.       C[i][0] = 0;
  24.       C[0][i] = 1;
  25.    }
  26.    FOR(i, 1, 5000)
  27.     FOR(j, 1, 5000){
  28.        if (i > j) C[i][j] = 0;
  29.        if (i == j) C[i][j] = 1;
  30.        if (i < j){
  31.           C[i][j] = C[i][j-1] + C[i-1][j-1];
  32.           if (C[i][j] >= mod) C[i][j] -= mod;
  33.        }
  34.     }
  35.    while(T--){
  36.       int n, c;
  37.       cin >> n >> c;
  38.       cout << C[c][n+c] - 1 << " ";
  39.    }
  40. }
  41.  
  42. ll Get1(ll a, ll b){
  43.   if (a > b) return 0;
  44.   return (F1[b]*F2[a]%mod*F2[b-a]%mod);
  45. }
  46.  
  47. ll Get2(ll a, ll b){
  48.   a %= mod;
  49.   if (a > b) return 0;
  50.   ll res = F2[a];
  51.   FOR(i, 0, a-1) res = res*(b-i)%mod;
  52.   return res;
  53. }
  54.  
  55. ll Mu(ll a, ll b){
  56.    if (b == 0) return 1;
  57.    ll res = 1;
  58.    a %= mod;
  59.    while(b != 0){
  60.        if (b&1){
  61.           res *= a;
  62.           res %= mod;
  63.        }
  64.        a *= a;
  65.        a %= mod;
  66.        b = (b >> 1);
  67.    }
  68.    return res;
  69. }
  70.  
  71. void Solve2(){
  72.   F1[0] = 1;
  73.   FOR(i, 1, MAX) F1[i] = F1[i-1]*i%mod;
  74.   F2[MAX] = Mu(F1[MAX], mod - 2);
  75.   for(int i = MAX; i >= 1; i--) F2[i-1] = F2[i]*i%mod;
  76.   while(T--){
  77.         ll n, c;
  78.         cin >> n >> c;
  79.         ll res = -1;
  80.         if (k == 3) res += Get1(c, n+c);
  81.         else res += Get2(c, n+c);
  82.         if (res < 0) res += mod;
  83.         cout << res << " ";
  84.    }
  85. }
  86.  
  87. int Tinh(ll p, ll H){
  88.   int res = 0;
  89.   ll Tam = p;
  90.   while(Tam <= H){
  91.       res += H/Tam;
  92.       Tam *= p;
  93.   }
  94.   return res;
  95. }
  96.  
  97. void Solve3(){
  98.    for(int i = 2; i*i <= MAX; i++)
  99.      if (!p[i])
  100.       for(int j = i*i; j <= MAX; j += i) p[j] = 1;
  101.    FOR(i, 2, MAX)
  102.     if (!p[i]) Prime.pb(i);
  103.    while(T--){
  104.       int n, c;
  105.       cin >> n >> c;
  106.       ll res = 1;
  107.       for(int p : Prime){
  108.          if (p > n+c) break;
  109.          int d = Tinh(p, n+c) - Tinh(p, c) - Tinh(p, n);
  110.          res = res*Mu(p, d)%mod;
  111.       }
  112.      --res;
  113.      while(res < 0) res += mod;
  114.      cout << res << el;
  115.    }
  116. }
  117.  
  118. int main()
  119. {
  120.     ios_base::sync_with_stdio(false);
  121.     cin.tie(NULL);    cout.tie(NULL);
  122.     freopen("walls.inp", "r", stdin);
  123.     freopen("walls.out", "w", stdout);
  124.     cin >> k >> T >> mod;
  125.     if (k == 1 || k == 2) Solve1();
  126.      else if (k == 3 || k == 4) Solve2();
  127.        else Solve3();
  128.     return 0;
  129. }
  130.  
Success #stdin #stdout 0.01s 6400KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/h6tCtI
language:
C++14 (clang 8.0)
created:
23 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!