SHARE
TWEET

Untitled

a guest Feb 10th, 2016 1,886 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. #define forn(i, n) for (int i = 0; i < int(n); i++)
  4. #define ford(i, n) for (int i = int(n) - 1; i >= 0; i--)
  5. #define fore(i, l, r) for (int i = int(l); i < int(r); i++)
  6. #define correct(x, y, n, m) (0 <= (x) && (x) < (n) && 0 <= (y) && (y) < (m))
  7. #define all(a) (a).begin(), (a).end()
  8. #define sz(a) int((a).size())
  9. #define pb(a) push_back(a)
  10. #define mp(x, y) make_pair((x), (y))
  11. #define x first
  12. #define y second
  13.  
  14. using namespace std;
  15.  
  16. typedef long long li;
  17. typedef long double ld;
  18. typedef pair<int, int> pt;
  19.  
  20. template<typename X> inline X abs(const X& a) { return a < 0? -a: a; }
  21. template<typename X> inline X sqr(const X& a) { return a * a; }
  22.  
  23. const int INF = int(1e9);
  24. const li INF64 = li(1e18);
  25. const ld EPS = 1e-9, PI = 3.1415926535897932384626433832795;
  26.  
  27. int n, k;
  28.  
  29. inline bool read() {
  30.     return !!(cin >> n >> k);
  31. }
  32.  
  33. const int mod = 1000 * 1000 * 1000 + 7;
  34.  
  35. int gcd(int a, int b, int& x, int& y) {
  36.     if (!a) {
  37.         x = 0, y = 1;
  38.         return b;
  39.     }
  40.     int xx, yy, g = gcd(b % a, a, xx, yy);
  41.     x = yy - b / a * xx;
  42.     y = xx;
  43.     return g;
  44. }
  45.  
  46. inline int normal(int n) {
  47.     n %= mod;
  48.     (n < 0) && (n += mod);
  49.     return n;
  50. }
  51.  
  52. inline int inv(int a) {
  53.     int x, y;
  54.     assert(gcd(a, mod, x, y) == 1);
  55.     return normal(x);
  56. }
  57.  
  58. inline int add(int a, int b) { return a + b >= mod ? a + b - mod : a + b; }
  59. inline int sub(int a, int b) { return a - b < 0 ? a - b + mod : a - b; }
  60. inline int mul(int a, int b) { return int(a * 1ll * b % mod); }
  61. inline int _div(int a, int b) { return mul(a, inv(b)); }
  62.  
  63. inline int binPow(int a, int b) {
  64.     int ans = 1;
  65.     while (b) {
  66.         if (b & 1) ans = mul(ans, a);
  67.         a = mul(a, a);
  68.         b >>= 1;
  69.     }
  70.     return ans;
  71. }
  72.  
  73. int calc(const vector<int>& y, int x) {
  74.     int ans = 0;
  75.     int k = 1;
  76.     fore(j, 1, sz(y)) {
  77.         k = mul(k, normal(x - j));
  78.         k = _div(k, normal(0 - j));
  79.     }
  80.     forn(i, sz(y)) {
  81.         ans = add(ans, mul(y[i], k));
  82.         if (i + 1 >= sz(y)) break;
  83.         k = mul(k, _div(normal(x - i), normal(x - (i + 1))));
  84.         k = mul(k, _div(normal(i - (sz(y) - 1)), normal(i + 1)));
  85.     }
  86.     return ans;
  87. }
  88.  
  89. inline int solve() {
  90.     vector<int> y;
  91.     int sum = 0;
  92.     y.pb(sum);
  93.     forn(i, k + 1) {
  94.         sum = add(sum, binPow(i + 1, k));
  95.         y.pb(sum);
  96.     }
  97.     if (n < sz(y)) return y[n];
  98.     return calc(y, n);
  99. }
  100.  
  101. int main() {
  102. #ifdef SU1
  103.     assert(freopen("input.txt", "rt", stdin));
  104.     //assert(freopen("output.txt", "wt", stdout));
  105. #endif
  106.    
  107.     cout << setprecision(10) << fixed;
  108.     cerr << setprecision(5) << fixed;
  109.  
  110.     while (read()) {
  111.         cout << solve() << endl;
  112.     }
  113.    
  114.     return 0;
  115. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top