fork download
copy 
  1. /*
  2. Permuation pair
  3. https://w...content-available-to-author-only...f.com/problems/PERMUTATION2?tab=statement
  4. */
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7. using ll = long long;
  8. const ll MOD = 1e9+7;
  9.  
  10. ll powerOf(ll n, ll r, ll m) {
  11.     ll res = 1;
  12.     ll base = n;
  13.     while(r>0) {
  14.         if(r%2==1) {
  15.             res = (res*base)%m;
  16.         }
  17.         base = (base*base)%m;
  18.         r /=2;
  19.     }
  20.     return res;
  21. }
  22.  
  23. vector<ll> fact, invfact;
  24. void preComputeFactorial(ll n, ll m)
  25. {
  26.     fact.resize(n + 1);
  27.     invfact.resize(n + 1);
  28.     fact[0] = 1;
  29.     for (ll i = 1; i <= n; i++)
  30.     {
  31.         fact[i] = (i * fact[i - 1]) % m;
  32.     }
  33.     invfact[n] = powerOf(fact[n], m - 2, m);
  34.     for (ll i = n - 1; i >= 0; i--)
  35.     {
  36.         invfact[i] = ((i + 1) * invfact[i + 1]) % m;
  37.     }
  38. }
  39.  
  40.  
  41. ll totalPairs(ll n, ll k) {
  42.     ll allPairs = 0;
  43.     if(k > ((2*n)-1)) {
  44.         allPairs = 0;
  45.     } else if(k>n) {
  46.         allPairs = (2*n -k +1)/2;
  47.     }else  if(k<=n){
  48.         allPairs = (k-1)/2;
  49.     }
  50.     return allPairs;
  51. }
  52.  
  53. ll nCr(ll n, ll r, ll m) {
  54. 	if(r>n) return 0;
  55. 	return (((fact[n] * invfact[r])%m)*invfact[n-r])%m;
  56. }
  57.  
  58. void solve() {
  59.     ll n, k;
  60.     cin >> n >> k;
  61.     ll allPairs = totalPairs(n, k);
  62.     bool pos = 1;
  63.     int ans = 0;
  64.     for (ll i = 1; i <= allPairs; i++) {
  65.         ll pie = (((nCr(allPairs, i, MOD) * fact[n-i] )% MOD) * powerOf(2, i, MOD)) % MOD;
  66.         if (pos) {
  67.             ans = (ans + pie) % MOD;
  68.         } else {
  69.             ans = (ans - pie + MOD) % MOD;
  70.         }
  71.         pos = 1-pos;
  72.     }
  73.     cout << ans << endl;
  74.     return;
  75. }
  76.  
  77. int main() {
  78. 	int t;
  79. 	cin>>t;
  80. 	ll n = 100005;
  81. 	preComputeFactorial(n, MOD);
  82. 	while(t--) {
  83. 	    solve();
  84. 	}
  85. 	return 0;
  86. }
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
10
3 3
5 4
7 4
8 10
9 16
10 19
10 20
30 40
100 120
1000 1000
stdout
copy 
4
48
1440
22560
80640
725760
0
422027771
488057398
656420449
https://ideone.com/si1Dfr
language:
C++14 (gcc 8.3)
created:
8 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!