fork download
copy 
  1. #include <iostream>
  2. #define int long long
  3. using namespace std;
  4. const int MOD = 1e9 + 7, SUB = 1e6 + 5;
  5.  
  6. int binp(int a, int n) {
  7. 	if (n == 0) return 1;
  8. 	int x = binp(a, n / 2);
  9. 	if (n % 2 == 0) return (x * x) % MOD;
  10. 	else return ((x * x) % MOD * a) % MOD;
  11. }
  12.  
  13. int di(int a, int b) {
  14. 	return (a * binp(b, MOD - 2)) % MOD; 
  15. }
  16.  
  17. int f1(int a, int n) {
  18. 	//a^n + a^(n - 1) + ... + a + 1
  19. 	if (a == 1) return n + 1;
  20. 	return di(binp(a, n + 1) - 1, a - 1);
  21. }
  22.  
  23. int f2(int a, int k) {
  24. 	//a^n + 2 * a^(n - 1) + 3 * a^(n - 2) + 4 * a^(n - 3) + ... + n * a + (n + 1)
  25. 	if (k == 0) return 1;
  26. 	int n = k / 2;
  27. 	if (k % 2 == 0) return (f2(a, n) + (n * f1(a, n)) % MOD + (binp(a, n + 1) * f2(a, n - 1)) % MOD) % MOD;
  28. 	else return ((binp(a, n + 1) * f2(a, n)) % MOD + ((n + 1) * f1(a, n)) % MOD + f2(a, n)) % MOD;
  29. }
  30.  
  31. signed main() {
  32. 	int q;
  33. 	cin >> q;
  34. 	while (q--) {
  35. 		int t, k, a, b, n;
  36. 		cin >> t >> k >> a >> b >> n;
  37. 		if (t == 1) {
  38. 			int res1 = (binp(a, n - 1) * k) % MOD;
  39. 			int res2 = (f1(a, n - 2) * b) % MOD;
  40. 			cout << (res1 + res2) % MOD << '\n';
  41. 		} else {
  42. 			if (a == 1) cout << ((n * k) % MOD + (b * ((n * (n - 1)) / 2) % MOD) % MOD) % MOD << '\n';
  43. 			else if (b == 0) cout << (k * f1(a, n - 1)) % MOD << '\n';
  44. 			else if (n <= SUB) {
  45. 				int res = 0, cur = k;
  46. 				for (int i = 1; i <= n; ++i) {
  47. 					res = (res + cur) % MOD;
  48. 					cur = (a * cur + b) % MOD;
  49. 				}
  50. 				cout << res << '\n';
  51. 			} else cout << ((k * f1(a, n - 1)) % MOD + (b * f2(a, n - 2)) % MOD) % MOD << '\n';
  52. 		}
  53. 	}
  54. 	return 0;
  55. }
  56.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
6
1 2 3 1 4
2 2 3 1 4
1 5 1 2 5
2 5 1 2 5
1 3 2 0 5
2 3 2 0 5
stdout
copy 
67
98
13
45
48
93
https://ideone.com/mMNcd1
language:
C++ (gcc 8.3)
created:
7 hours 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!