fork download
copy 
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3.  
  4. const int D=1e4;
  5. const long long N=1e12;
  6. const int MOD=998244353;
  7.  
  8. long long n, d;
  9. int C[D+1][D+2];
  10.  
  11. int add(int a, int b){
  12. 	return (a+b>=MOD?a+b-MOD:a+b);
  13. }
  14.  
  15. int add2(int &a, int b){
  16. 	return a=add(a,b);
  17. }
  18.  
  19. int main() {
  20. 	cin >> n >> d;
  21. 	d--;
  22.  
  23. 	for(int i=0; i<=d; i++) C[i][0]=1;
  24. 	for(int i=1; i<=d; i++){
  25. 		for(int j=1; j<=i; j++){
  26. 			C[i][j]=add(C[i-1][j], C[i-1][j-1]);
  27. 			// cout << "C[" <<i << "][" << j << "] " << C[i][j] << "\n";
  28. 		}
  29. 	}
  30.  
  31. 	int ans = 2;
  32. 	for(int k=1; k<=d+1; k++){
  33. 		vector<vector<int>> c={{C[d][k], k-1<0?0:C[d][k-1]}, {k-1<0?0:C[d][k-1], k-2<0?0:C[d][k-2]}};
  34. 		vector<vector<int>> m={{1, 0}, {0, 1}};
  35.  
  36. 		auto mult=[&](vector<vector<int>> a, vector<vector<int>> b)->vector<vector<int>>{
  37. 			vector<vector<int>> c(2,vector<int>(2));
  38. 			for(int i=0; i<2; i++){
  39. 				for(int j=0; j<2; j++){
  40. 					for(int k=0; k<2; k++){
  41. 						add2(c[i][j], ((long long)a[i][k]*b[k][j])%MOD);
  42. 					}
  43. 				}
  44. 			}	
  45. 			return c;
  46. 		};
  47.  
  48. 		for(int i=0; (1LL<<i)<=n; i++){
  49. 			if(n&(1LL<<i)){
  50. 				m=mult(c, m);
  51. 			}
  52. 			c=mult(c,c);
  53. 		}
  54. 		// cout << m[0][0] << " " << m[0][1] << '\n' << m[1][0] << " " << m[1][1] << '\n';
  55. 		add2(ans, add(m[0][0], m[1][1]));
  56. 	}
  57. 	cout << ans;
  58. }
Success #stdin #stdout 0.07s 88740KB
comments (?)
stdin
copy 
299792458 3141
stdout
copy 
138897974
https://ideone.com/62dTTa
language:
C++14 (gcc 8.3)
created:
1 year 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!