fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define MAXK 330
  5. #define MOD 1234567891
  6.  
  7. unsigned int f[MAXK+1][MAXK+1];
  8.  
  9. unsigned int pwr(int x, int n) {
  10. 	if (!n)	return 1;
  11. 	unsigned int y = pwr(x, n>>1);
  12. 	y = (1ULL * y * y) % MOD;
  13. 	if (n & 1)	y = (1ULL * x * y) % MOD;
  14. 	return y;
  15. }
  16.  
  17. void precompute() {
  18. 	f[0][1] = 1;
  19. 	for (int i = 1; i < MAXK; i++) {
  20. 		long long s = 0;
  21. 		for (int j = 2; j <= i+1; j++) {
  22. 			f[i][j] = (((1ULL * i * pwr(j, MOD-2)) % MOD) * 1ULL * f[i-1][j-1]) % MOD;
  23. 			s += f[i][j];
  24. 		}
  25. 		f[i][1] = (MOD + 1 - (s % MOD)) % MOD;
  26. 	}
  27. }
  28.  
  29. unsigned int calc(int n, int k) {
  30. 	unsigned int ans = 0;
  31. 	for (int i = k+1; i >= 0; i--) {
  32. 		ans = (1ULL * n * ans + f[k][i]) % MOD;
  33. 	}
  34. 	return ans;
  35. }
  36.  
  37. int main() {
  38. 	precompute();
  39. 	cout << calc(2, 3) << endl;
  40. 	int t, n, k;
  41. 	scanf("%d", &t);
  42. 	while (t--) {
  43. 		scanf("%d%d", &n, &k);
  44. 		int ans = (1ULL * (n+1) * calc(n, k)) % MOD;
  45. 		ans = (1LL * ans - calc(n, k+1) + MOD) % MOD;
  46. 		printf("%d\n", ans);
  47. 		// n = 2, k = 3 => 3 * 
  48. 	}
  49. 	return 0;
  50. }
Success #stdin #stdout 0.01s 4376KB
comments (?)
stdin
copy 
5
2 3
10 3
3 3
100 0
100 1
stdout
copy 
9
10
7942
46
5050
171700
https://ideone.com/tz5E9G
language:
C++14 (gcc 8.3)
created:
3 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!