fork download
copy 
  1. //#pragma GCC optimize("O3")
  2. //#pragma GCC optimize("unroll-loops")
  3. //#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
  4.  
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7.  
  8. #define ll long long
  9. #define el '\n'
  10. #define MASK(i) (1 << (i))
  11. #define BIT(x,i) (((x) >> (i))&1)
  12. #define HSR ios_base::sync_with_stdio(false); cin.tie(0);
  13. #define file "walls"
  14. int delta,t;
  15. ll MOD;
  16. namespace sub12{
  17.     const int maxn = (int)5003;
  18.     const int maxL = 2*maxn;
  19.     int C[maxL][maxn];
  20.     void prepare(){
  21.         C[0][0] = 1;
  22.         for (int i=1;i<maxL;i++){
  23.             C[i][0] = 1;
  24.             int Lim = min(i,maxn-1);
  25.             C[i][Lim] = 1;
  26.             for (int j=1;j<Lim;j++) C[i][j] = (C[i-1][j-1]+C[i-1][j])%MOD;
  27.         }
  28.     }
  29.     void solve(){
  30.         prepare();
  31.         while(t--){
  32.             int n,k;
  33.             cin >> n >> k;
  34.             cout << ((C[n+k][k]-1)+MOD)%MOD << " ";
  35.         }
  36.     }
  37. }
  38. namespace sub3{
  39.     const int maxn = (int)2e6 + 3;
  40.     ll fact[maxn], inv_fact[maxn];
  41.     ll pw_mod(ll base, ll pw){
  42.         ll res = 1;
  43.         ll mul = base;
  44.         while(pw){
  45.             if (pw&1) res = (res*mul)%MOD;
  46.             mul = (mul*mul)%MOD;
  47.             pw/=2;
  48.         }
  49.         return res;
  50.     }
  51.     void prepare(){
  52.         fact[0] = 1;
  53.         for (int i=1;i<maxn;i++) fact[i] = (fact[i-1]*i)%MOD;
  54.         inv_fact[maxn-1] = pw_mod(fact[maxn-1],MOD-2);
  55.         for (int i=maxn-2;i>=0;i--) inv_fact[i] = (inv_fact[i+1]*(i+1))%MOD;
  56.     }
  57.     ll C(int n, int k){
  58.         ll tmp = (fact[n]*inv_fact[k])%MOD;
  59.         tmp = (tmp*inv_fact[n-k])%MOD;
  60.         return tmp;
  61.     }
  62.     void solve(){
  63.         prepare();
  64.         while(t--){
  65.             int n,k;
  66.             cin >> n >> k;
  67.             cout << ((C(n+k,k)-1)+MOD)%MOD << " ";
  68.         }
  69.     }
  70. }
  71. namespace sub4{
  72.     const int maxn = (int)1e6 + 3;
  73.     ll fact[maxn], inv_fact[maxn];
  74.     ll pw_mod(ll base, ll pw){
  75.         ll res = 1;
  76.         ll mul = base;
  77.         while(pw){
  78.             if (pw&1) res = (res*mul)%MOD;
  79.             mul = (mul*mul)%MOD;
  80.             pw/=2;
  81.         }
  82.         return res;
  83.     }
  84.     void prepare(){
  85.         fact[0] = 1;
  86.         for (int i=1;i<maxn;i++) fact[i] = (fact[i-1]*i)%MOD;
  87.         inv_fact[maxn-1] = pw_mod(fact[maxn-1],MOD-2);
  88.         for (int i=maxn-2;i>=0;i--) inv_fact[i] = (inv_fact[i+1]*(i+1))%MOD;
  89.     }
  90.     ll C(ll n, ll k){
  91.         ll tmp = 1;
  92.         for (ll i=n;i>=n-k+1;i--) tmp = (tmp*(i%MOD))%MOD;
  93.         tmp = (tmp*inv_fact[k])%MOD;
  94.         return tmp;
  95.     }
  96.     void solve(){
  97.         prepare();
  98.         while(t--){
  99.             ll n,k;
  100.             cin >> n >> k;
  101.             cout << ((C(n+k,k)-1)+MOD)%MOD << " ";
  102.         }
  103.     }
  104. }
  105. namespace sub5{
  106.     const int maxn = (int)2e6 + 2;
  107.     bool isPrime[maxn];
  108.     vector<ll> Prime;
  109.     void sieve(){
  110.         for (int i=2;i<maxn;i++) isPrime[i] = true;
  111.         for (int i=2;1ll*i*i<maxn;i++){
  112.             if (isPrime[i]){
  113.                 for (int j=i*i;j<maxn;j+=i) isPrime[j] = false;
  114.             }
  115.         }
  116.     }
  117.     ll pw_mod(ll base, ll pw){
  118.         ll res = 1;
  119.         ll mul = base;
  120.         while(pw){
  121.             if (pw&1) res = (res*mul)%MOD;
  122.             mul = (mul*mul)%MOD;
  123.             pw/=2;
  124.         }
  125.         return res;
  126.     }
  127.     void prepare(){
  128.         for (int i=2;i<maxn;i++){
  129.             if (isPrime[i]) Prime.push_back(i);
  130.         }
  131.     }
  132.     ll getExp(ll n, ll p){
  133.         ll res = 0;
  134.         ll pw = p;
  135.         while(pw <= n){
  136.             res += n/pw;
  137.             pw *= p;
  138.         }
  139.         return res;
  140.     }
  141.     ll C(ll n, ll k){
  142.         if (k > n) return 0;
  143.         ll res = 1;
  144.         for (ll cur_p:Prime){
  145.             if (cur_p > n) break;
  146.             ll pw = getExp(n,cur_p)-getExp(k,cur_p)-getExp(n-k,cur_p);
  147.             res = (res*pw_mod(cur_p,pw))%MOD;
  148.         }
  149.         return res;
  150.     }
  151.     void solve(){
  152.         sieve();
  153.         prepare();
  154.         while(t--){
  155.             ll n,k;
  156.             cin >> n >> k;
  157.             cout << ((C(n+k,k)-1)+MOD)%MOD << " ";
  158.         }
  159.     }
  160. }
  161. int main(){
  162.     HSR
  163.     freopen(file".inp","r",stdin);
  164.     freopen(file".out","w",stdout);
  165.     cin >> delta >> t >> MOD;
  166.     bool isOneTwo = false, isThree = false, isFour = false, isFive = false;
  167.     if ((delta == 1) || (delta == 2)) isOneTwo = true;
  168.     if (delta == 3) isThree = true;
  169.     if (delta == 4) isFour = true;
  170.     if (delta == 5) isFive = true;
  171.     if (isOneTwo) sub12::solve();
  172.     if (isThree) sub3::solve();
  173.     if (isFour) sub4::solve();
  174.     if (isFive) sub5::solve();
  175.     return 0;
  176. }
  177.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/3hthK9
language:
C++14 (clang 8.0)
created:
3 days 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!