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 = 100005;
  22. ll fact[N], ifact[N];
  23.  
  24. ll modx(ll base, ll ex)
  25. {
  26.     ll ans = 1LL, val = base;
  27.     while(ex > 0LL)
  28.     {
  29.         if(ex&1LL)
  30.             ans = (ans*val)%MOD;
  31.         val = (val*val)%MOD;
  32.         ex = ex>>1LL;
  33.     }
  34.     return ans;
  35. }
  36.  
  37. ll C(ll n, ll r)
  38. {
  39.     if(r < 0LL)
  40.         return 0LL;
  41.  
  42.     ll ans = fact[n];
  43.     ans = (ans*ifact[n-r])%MOD;
  44.     ans = (ans*ifact[r])%MOD;
  45.     return ans;
  46. }
  47.  
  48. void pre()
  49. {
  50.     fact[0] = 1LL;
  51.     ifact[0] = 1LL;
  52.     for(int i = 1; i<N; i++)
  53.     {
  54.         fact[i] = (fact[i-1]*((ll)i))%MOD;
  55.         ifact[i] = modx(fact[i], MOD-2LL);
  56.     }
  57.     return;
  58. }
  59.  
  60. int main()
  61. {
  62.     ios::sync_with_stdio(false);
  63.     cin.tie(0);
  64.  
  65.     // clock_t clk;
  66.     // clk = clock();
  67.  
  68.     // freopen("/Users/hm_98/Downloads/Input/t10.txt", "r", stdin);
  69.     // freopen("/Users/hm_98/Downloads/Output1/o10.txt", "w", stdout);
  70.  
  71.     pre();
  72.  
  73.     int t;
  74.     cin >> t;
  75.  
  76.     assert(t <= 20 && t >= 1);
  77.  
  78.     int n, k;
  79.     while(t--)
  80.     {
  81.         cin >> n >> k;
  82.  
  83.         assert(n >= 1 && n <= 100000);
  84.         assert(k >= 0 && k <= 100000);
  85.  
  86.         n = n/2;
  87.         ll total = (C(2*n, n) - C(2*n, n-1) + MOD)%MOD;
  88.  
  89.         if(k > (n/2))
  90.         {
  91.             cout << "1\n";
  92.             continue;
  93.         }
  94.  
  95.         ll ans = 0LL, temp;
  96.         for(int i = 0; i<=k; i++)
  97.         {
  98.             temp = (C(n, i) - C(n, i-1) + MOD)%MOD;
  99.             temp = (temp*temp)%MOD;
  100.             ans = (ans + temp)%MOD;
  101.         }
  102.         ans = (ans*modx(total, MOD-2LL))%MOD;
  103.         cout << ans << "\n";
  104.     }
  105.  
  106.     // clk = clock() - clk;
  107.     // cout << "Time: " << ((double)clk)/CLOCKS_PER_SEC << "\n";
  108.  
  109.     return 0;
  110. }
Runtime error #stdin #stdout #stderr 0.02s 4604KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
prog: prog.cpp:76: int main(): Assertion `t <= 20 && t >= 1' failed.
https://ideone.com/drkxpB
language:
C++14 (gcc 8.3)
created:
7 years 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!