fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int mod = 998244353;
  4. vector<int> fact, inv, factinv;
  5. inline int binomial_coefficient(int a, int b) {
  6. 	return 1LL * fact[a] * factinv[b] % mod * factinv[a - b] % mod;
  7. }
  8. int n; long long m;
  9. int main() {
  10. 	cin >> n >> m;
  11. 	if(n > 200000 || m > 200000) return 0;
  12. 	fact.resize(n + m + 1); fact[0] = 1;
  13. 	for(int i = 1; i <= n + m; i++) fact[i] = 1LL * fact[i - 1] * i % mod;
  14. 	inv.resize(n + m + 1); inv[1] = 1;
  15. 	for(int i = 2; i <= n + m; i++) inv[i] = 1LL * inv[mod % i] * (mod - mod / i) % mod;
  16. 	factinv.resize(n + m + 1); factinv[0] = 1;
  17. 	for(int i = 1; i <= n + m; i++) factinv[i] = 1LL * factinv[i - 1] * inv[i] % mod;
  18. 	vector<int> g(m + 1, 0); g[1] = 1;
  19. 	for(int i = 2; i <= m; i++) g[i] = (g[i - 1] + g[i - 2]) % mod;
  20. 	int ret = 0;
  21. 	if(n == 1) ret = g[m];
  22. 	else {
  23. 		for(int i = 1; i <= m; i++) {
  24. 			long long res = 1LL * binomial_coefficient(n - 2 + m - i, n - 2) * g[i];
  25. 			ret = (ret + res) % mod;
  26. 		}
  27. 	}
  28. 	cout << ret << endl;
  29. 	return 0;
  30. }
Success #stdin #stdout 0s 3476KB
comments (?)
stdin
copy 
3 20
stdout
copy 
46345
https://ideone.com/z8OhZI
language:
C++14 (gcc 8.3)
created:
7 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!