fork download
copy 
  1. #define NguyenDangQuan the_author
  2. #define my_heart love_you_to_the_moon_and_back
  3. #pragma GCC target("avx2")
  4. #pragma GCC optimization("O3")
  5. #pragma GCC optimization("unroll-loops")
  6.  
  7. #include <bits/stdc++.h>
  8. using namespace std;
  9. using ll = long long;
  10. using ld = long double;
  11. using ull = unsigned long long;
  12.  
  13. bool typetest;
  14. inline void fastIOfileinput()
  15. {
  16. 	ios::sync_with_stdio(0);
  17. 	cin.tie(0);
  18. 	cout.tie(0);
  19. 	typetest = 0;
  20. }
  21.  
  22. const int N = 1e6 + 5;
  23. int k;
  24. ll n, tu;
  25. ll f[N], rf[N], gt[N], rgt[N], agt[N], ragt[N];
  26. const ll mod = 123456789;
  27.  
  28. void Read()
  29. {
  30. 	cin >> n >> k;
  31. }
  32.  
  33. ll Pow(ll a, ll b)
  34. {
  35. 	ll ans = 1;
  36. 	for (; b > 0; b >>= 1)
  37. 	{
  38. 		if (b & 1)
  39. 			ans = ans * a % mod;
  40. 		a = a * a % mod;
  41. 	}
  42. 	return ans;
  43. }
  44.  
  45. void Solve()
  46. {
  47. 	f[0] = 0;
  48. 	tu = 1;
  49. 	gt[0] = rgt[0] = agt[0] = ragt[0] = 1;
  50. 	for (int i = 1; i <= k + 2; ++i)
  51. 	{
  52. 		f[i] = (f[i - 1] + Pow(i, k)) % mod;
  53. 		gt[i] = gt[i - 1] * i % mod;
  54. 		agt[i] = agt[i - 1] * (-i) % mod;
  55. 		rgt[i] = Pow(gt[i], mod - 2);
  56. 		ragt[i] = Pow(agt[i], mod - 2);
  57. 		tu = tu * (n - i) % mod;
  58. 		//cout << i << " " << f[i] << "\n";
  59. 	}
  60. 	if (n <= k + 2)
  61. 	{
  62. 		cout << f[n];
  63. 		return;
  64. 	}
  65. 	ll ans = 0;
  66. 	for (int i = 1; i <= k + 2; ++i)
  67. 		(ans += f[i] * rgt[i - 1] % mod * ragt[k + 2 - i] % mod * tu % mod * Pow(n - i, mod - 2) % mod) %= mod;
  68. 	cout << (ans + mod) % mod;
  69. }
  70.  
  71. int32_t main()
  72. {
  73. 	fastIOfileinput();
  74. 	if (typetest)
  75.  
  76. 	{
  77. 		int t;
  78. 		cin >> t;
  79. 		while (t--)
  80. 		{
  81. 			Read();
  82. 			Solve();
  83. 		}
  84. 	}
  85. 	else
  86. 	{
  87. 		Read();
  88. 		Solve();
  89. 	}
  90. }
Success #stdin #stdout 0.01s 11864KB
comments (?)
stdin
copy 
4 1
stdout
copy 
112556475
https://ideone.com/wQ3Dgj
language:
C++14 (gcc 8.3)
created:
14 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!