fork download
copy 
  1. #include<bits/stdc++.h>
  2. // #include<ext/pb_ds/assoc_container.hpp>
  3. // #include<ext/pb_ds/tree_policy.hpp>
  4. using  namespace std;
  5. // using namespace __gnu_pbds;
  6.  
  7. //------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
  8. //Give shorthand names to data types using typedef.
  9. typedef long long ll;
  10. typedef unsigned long long ull;
  11. typedef long double ld;
  12. typedef pair<int, int>  pii;
  13. typedef vector<int> vi;
  14. typedef vector<vi> vvi;
  15. typedef vector<pii> vpii;
  16. typedef vector<vpii> vvpii;
  17. typedef pair<ll, ll> pll;
  18. typedef vector<ll>  vll;
  19. typedef vector<vll> vvll;
  20. typedef vector<pll> vpll;
  21. typedef vector<vpll> vvpll;
  22. typedef pair<ll,pair<ll,ll>> triplet;
  23. // #define ordered_set tree<pair<int,int>, null_type, less<pair<int,int>>, rb_tree_tag, tree_order_statistics_node_update>
  24.  
  25. //------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
  26. #define fo(i,n) for(int i=0;i<n;i++)
  27. #define fo1(i,n) for(int i=1;i<=n;i++)
  28. #define Fo(i,n) for(int i=n-1;i>=0;i--)
  29. #define Fo1(i,n) for(int i=n;i>=1;i--)
  30. #define rep(i,a,b) for(int i=a;i<=b;i++)
  31. #define rep2(i,a,b) for(int i=a;i>=b;i--)
  32.  
  33. #define pb push_back
  34. #define eb emplace_back
  35. #define F first
  36. #define S second
  37. #define all(x) (x).begin(), (x).end()
  38. #define set_bits __builtin_popcountll
  39.  
  40. #define PI 3.1415926535897932384626
  41.  
  42. #define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
  43. mt19937 rnd((unsigned int) chrono::steady_clock::now().time_since_epoch().count());
  44.  
  45. const int MOD = 1e9+7;
  46. const int MOD1 = 998244353;
  47. const int MOD3 = 1610612741;
  48. /* Alternate Prime nos where probability of collision is less for hashing for MOD3:
  49.     long long:
  50.     1000000000039
  51.     2000000000003
  52.     3000000000013
  53.     4000000000039
  54.     int:
  55.     1610612741(currently used).
  56. */
  57. const ll INF = 1e18+9;
  58. const ll NINF = -1e18-9;
  59.  
  60.  
  61. #define deb(x) cerr << #x <<" "; _print(x); cerr << endl;
  62.  
  63. template <class T> void _print(T x){cerr<<x;}
  64. template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.F); cerr << ","; _print(p.S); cerr << "}";}
  65. template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
  66. template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
  67. template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
  68. template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
  69.  
  70. vi primes;
  71. vi spf;
  72. vector<bool> prime;
  73.  
  74. //------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
  75. ll gcd(ll a, ll b) {if (b > a) {return gcd(b, a);} if (b == 0) {return a;} return gcd(b, a % b);}
  76. ll mpow(ll base, ll exp , ll mod) { base %= mod; ll result = 1; while (exp > 0) { if (exp & 1) result = (result * base) % mod; base = (base * base) % mod; exp >>= 1;} return result;}
  77. //Use when 'a' and 'b' are less than mod,but their addition can go beyond mod.
  78. ll mAdd(ll a, ll b , ll mod) {return (a + b >= mod ? a + b - mod : a + b);}
  79. void extendgcd(ll a, ll b, ll*v) {if (b == 0) {v[0] = 1; v[1] = 0; v[2] = a; return ;} extendgcd(b, a % b, v); ll x = v[1]; v[1] = v[0] - v[1] * (a / b); v[0] = x; return;} //pass an arry of size1 3
  80. ll mminv(ll a, ll b) {ll arr[3]; extendgcd(a, b, arr); return arr[0];} //for non prime b
  81. ll mminvprime(ll a, ll b) {return mpow(a, b - 2, b);}
  82. bool revsort(ll a, ll b) {return a > b;}
  83. void swap(ll &x, ll &y) {int temp = x; x = y; y = temp;}
  84. ll combination(ll n, ll r, ll m, ll *fact, ll *ifact) {ll val1 = fact[n]; ll val2 = ifact[n - r]; ll val3 = ifact[r]; return (((val1 * val2) % m) * val3) % m;}
  85. void google(int t) {cout << "Case #" << t << ": ";}
  86. ll mod_add(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a + b) % m) + m) % m;}
  87. ll mod_mul(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a * b) % m) + m) % m;}
  88. ll mod_sub(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a - b) % m) + m) % m;}
  89. ll mod_div(ll a, ll b, ll m) {a = a % m; b = b % m; return (mod_mul(a, mminvprime(b, m), m) + m) % m;}  //only for prime m
  90. ll phin(ll n) {ll number = n; if (n % 2 == 0) {number /= 2; while (n % 2 == 0) n /= 2;} for (ll i = 3; i <= sqrt(n); i += 2) {if (n % i == 0) {while (n % i == 0)n /= i; number = (number / i * (i - 1));}} if (n > 1)number = (number / n * (n - 1)) ; return number;} 
  91. vector<long long> computeHash(string &s) {ll str_len=s.length(); ll p_pow[str_len]; ll p=123; p_pow[0]=1; for(int i=1;i<str_len;i++) p_pow[i]=(p_pow[i-1]*p)%MOD3; vector<long long> hash(str_len+1); hash[0]=0; for(int i=1;i<=str_len;i++) hash[i] = ( hash[i-1] + ((s[i-1]-'a'+1)*p_pow[i-1]) %MOD3 )%MOD3; return hash; }
  92. vector<int> makeZarray(string s) {int n = s.length(); vector<int> z(n); int l=0,r=0; for(int i=1;i<n;i++) {if(i<=r) z[i] = min(z[i-l],r-i+1); while(i+z[i]<n && s[z[i]]==s[i+z[i]]) z[i]++; if(i+z[i]-1 > r) l=i , r=i+z[i]-1; } return z; }
  93. //O(nloglogn)
  94. void sieve(int n) {prime.assign(n+1,true); prime[0]=0; prime[1]=0; for (int i = 2; i <= n; i++)if (prime[i] == 1) {primes.eb(i); for (ll j = (ll)i * i; j <= n; j += i) {if(prime[j]) prime[j]=0;} } }
  95. //O(nloglogn) Max value of n=1e6.
  96. void find_spf(int n) {n = max(n,1); spf.assign(n+1,0); prime.assign(n+1,true); prime[0] = prime[1] = false; int i; for(i=2; i<=n; i++) {if(prime[i]) {primes.eb(i); spf[i]=i; for(ll j=(ll)i*i; j<=n; j+=i) {if(prime[j]) {prime[j]=false; spf[j]=i; } } } } }
  97. //O(log2n) time at max. Before running this , Run sieve(if n larger than 1e6) or find_spf() if n<=1e6,both  upto sqrt(n).
  98. vpll prime_factorize(ll n) { vpll result; if(n < spf.size()) {while(n!=1) {ll fact = spf[n]; ll exp=0; do {n/=fact; exp++; } while(n%fact==0); result.eb(fact,exp); } return result; } else {for(auto p : primes) { if(p*p > n) break; if(n % p==0) {result.emplace_back(p, 0); do {n /= p; result.back().second++; } while (n % p == 0); } } if(n>1) result.eb(n,1); return result; } }
  99. ll sumprimeExp(ll n) {vpll prime_factors = prime_factorize(n); ll ans=0; for(auto p : prime_factors) {ans+=p.second; } return ans; }
  100. //---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
  101.  
  102. ll n;
  103.  
  104. ll helperEven(ll k,ll sum){
  105.     if(k==0) return 1;
  106.  
  107.     ll val1 = (sum*helperEven(k-1,sum))%MOD;
  108.     ll val2 = mpow(2,n*(k-1),MOD);
  109.  
  110.     return (val1 + val2)%MOD;
  111. }
  112.  
  113. ll helperOdd(ll k,ll sum){
  114.     if(k==0) return 1;
  115.  
  116.     ll val1 = (sum*helperEven(k-1,sum))%MOD;
  117.  
  118.     return val1;
  119. }
  120.  
  121. int32_t main()
  122. {
  123.     fast_io;
  124.     int t; 
  125.     cin>>t;
  126.  
  127.     ll Max = 2*1e5 + 1;
  128.  
  129.     ll fact[Max],ifact[Max];
  130.     fact[0]=1; ifact[0]=1;
  131.  
  132.     for(ll i=1;i<=Max-1;i++){
  133.         fact[i] = (fact[i-1]*i)%MOD;
  134.         ifact[i] = mminvprime(fact[i],MOD);
  135.     }
  136.  
  137.     while(t--)
  138.     {
  139.         ll k; cin>>n>>k;
  140.  
  141.         ll sum = 0;
  142.         if(n%2==0){
  143.             for(ll i=0;i<=n-2;i+=2){
  144.                 sum = (sum + combination(n,i,MOD,fact,ifact))%MOD;
  145.             }
  146.  
  147.             cout<<helperEven(k,sum);
  148.         }   
  149.         else{
  150.             for(ll i=0;i<=n-1;i+=2){
  151.                 sum = (sum + combination(n,i,MOD,fact,ifact))%MOD;    
  152.             }   
  153.             cout<<helperOdd(k,(sum+1)%MOD);
  154.         }       
  155.         cout<<endl;
  156.     }
  157. }
Success #stdin #stdout 0.09s 13040KB
comments (?)
stdin
copy 
5
200000 200000
24567 23423
1 200000
200000 1
200000 0
stdout
copy 
226490044
67238033
616024518
87947641
1
https://ideone.com/RZAe22
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
secret

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!