fork(9) download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cctype>
  4. #include <string>
  5. #include <cmath>
  6. #include <vector>
  7. #include <algorithm>
  8. #include <stack>
  9. #include <queue>
  10. #include <deque>
  11. #include <map>
  12. #include <set>
  13. #include <sstream>
  14. #include <fstream>
  15. #include <ctime>
  16. #include <cassert>
  17. #include <string.h>
  18.  
  19. using namespace std;
  20.  
  21. typedef long long LL;
  22. #define MAXN 100000+5
  23.  
  24. int n;
  25. LL k;
  26.  
  27. LL fact[MAXN];
  28. LL f[MAXN], g[MAXN];
  29.  
  30. #define MOD 1000000007
  31.  
  32. LL pwr(LL x, int n) {
  33.     if (!n) return 1;
  34.     LL y = pwr(x, n>>1);
  35.     (y = y * y) %= MOD;
  36.     if (n&1)    (y = x * y) %= MOD;
  37.     return y;
  38. }
  39.  
  40. LL kPn(LL k, int n) {
  41.     LL ans = 1;
  42.     for (int i = 0; i < n; i++) {
  43.         (ans *= ((k-i) % MOD)) %= MOD;
  44.     }
  45.     return ans;
  46. }
  47.  
  48. int main() {
  49.     fact[0] = 1;
  50.     for (int i = 1; i < MAXN; i++) {
  51.         (fact[i] = i * fact[i-1]) %= MOD;
  52.     }
  53.     int t, nsum = 0;
  54.     scanf("%d", &t);
  55.     assert(t >= 1 && t <= 1000);
  56.     while (t--) {
  57.         scanf("%d", &n);
  58.         assert(n >= 1 && n <= 100000);
  59.         scanf("%lld", &k);
  60.         assert(k >= 0 && k <= 1000000000000000000l);
  61.  
  62.         LL kpn = kPn(k, n);
  63.         nsum += n;
  64.  
  65.         f[0] = 1, g[0] = 1;
  66.         for (int i = 1; i <= n; i++) {
  67.             (f[i] = ((k-n) % MOD) * f[i-1]) %= MOD;
  68.             if (i >= 2) (f[i] += ((k-n) % MOD) * ((i-1) * f[i-2] % MOD)) %= MOD;
  69.             if (i >= 3) (f[i] += fact[i-1] * (((k-n+1) % MOD) * g[i-3] % MOD)) %= MOD;
  70.             (g[i] = g[i-1] + (f[i] * pwr(fact[i], MOD-2) % MOD)) %= MOD;
  71.         }
  72.  
  73.         LL ans = (f[n] * kpn) % MOD;
  74.         if (ans < 0)    ans += MOD;
  75.         printf("%lld\n", ans);
  76.     }
  77.     assert(nsum <= 1000000);
  78.  
  79.     char ch;
  80.     scanf("%c",&ch);
  81.     assert(ch == '\n');
  82.     assert(scanf("%c", &ch) == EOF);
  83.     return 0;
  84. }
Runtime error #stdin #stdout #stderr 0s 5580KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
prog: prog.cpp:55: int main(): Assertion `t >= 1 && t <= 1000' failed.
https://ideone.com/4q2Pii
language:
C++ (gcc 8.3)
created:
9 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!