• API
• FAQ
• Tools
• Archive
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.
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.