fork download 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. const int max_const = int(1e9+7);
  5.  
  6. int matrix_zenik(int n, int k)
  7. {
  8. 	int matrix[n+1][n+1][n+1];
  9. 	for(int i=0;i<=n;++i){
  10. 		for(int j=0;j<=n;++j){
  11. 			for(int k=0;k<=n;++k){
  12. 				matrix[i][j][k]=0;
  13. 			}
  14. 		}
  15. 		matrix[i][i][i]=1;
  16. 	}
  17. 	for(int step_from=1;step_from<n;++step_from){
  18. 		for(int step_to=step_from+1;step_to<=n;++step_to){
  19. 			for(int min_i=1;min_i<=step_from+1;++min_i){
  20. 				int last = min(min_i+k,step_from+1);
  21. 				for(int max_i=min_i;max_i<=last;++max_i){
  22. 					int min_to_write = min(min_i,step_to-step_from);
  23. 					int max_to_write = max(max_i,step_to-step_from);
  24. 					matrix[step_to][min_to_write][max_to_write] += matrix[step_from][min_i][max_i];
  25. 					if(matrix[step_to][min_to_write][max_to_write]>max_const){
  26. 						matrix[step_to][min_to_write][max_to_write]-=max_const;
  27. 					}
  28. 				}
  29. 			}
  30. 		}
  31.  
  32. 	}
  33. 	int sum =0;
  34. 	for(int i=0;i<=n;++i){
  35. 		for(int j=0;j<=n;++j){
  36. 			sum+=matrix[n][i][j];
  37. 			if(sum>max_const){
  38. 				sum-=max_const;
  39. 			}
  40. 		}
  41. 	}	
  42. 	return sum;
  43. }
  44.  
  45. int main() {
  46. 	cout<<matrix_zenik(100,100);
  47. 	return 0;
  48. }
Success #stdin #stdout 0.02s 7084KB
comments (?)
stdin 
Standard input is empty
stdout 
988185646
https://ideone.com/xPWktF
language:
C++14 (gcc 8.3)
created:
6 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!