fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. long long mod=1e9 + 7;
  5. int m;
  6. struct matrix {
  7.     long long v, h;
  8.     vector<vector<long long>> c = vector<vector<long long>>(500, vector<long long>(500, 0));
  9.     matrix(int a = 500, int b = 500){
  10.     	v = a;
  11.     	h = b;
  12.     }
  13.     void ident(){
  14.     	for(int i = 0; i < v; i++) c[i][i] = 1;
  15.     }
  16.  
  17. };
  18.  
  19. int id(int i, int j){
  20. 	i--;
  21. 	j--;
  22. 	return i * m + j;
  23. }
  24.  
  25. matrix operator * (matrix a,matrix b){
  26.  
  27.     int n = a.v, m = a.h, p = b.h;
  28.     matrix res(n, p);
  29.     for (int i=0;i<n;i++)
  30.         for (int j=0;j<p;j++){
  31.             for (int k=0;k<m;k++){
  32.                 res.c[i][j]+= ((a.c[i][k] % mod) * (b.c[k][j] % mod)) % mod;
  33.                 res.c[i][j] %= mod;
  34.             }
  35.         }
  36.     return res;
  37. }
  38. matrix powermod(matrix a, long long n){
  39.     matrix r(a.v, a.v);
  40.     r.ident();
  41.     for(; n > 0; n >>= 1, a = a * a) if(n & 1) r = r * a; return r;
  42.  
  43. }
  44. int main(){
  45. 	// freopen("tile.inp", "r", stdin);
  46. 	// freopen("tile.out", "w", stdout);
  47.     ios_base::sync_with_stdio(false);
  48.     cin.tie(NULL);
  49.     long long n, k, p, q, r; cin >> n >> m >> k;
  50.     matrix dp(m * m, 1);
  51.     for(int i = 1; i <= m; i++){
  52.     	dp.c[id(i, i)][0] = 1;
  53.     	for(int j = 1; j < i; j++){
  54.     		for(int d = max(1LL, j - k); d <= min(j + k, (long long)i); d++){
  55.     			dp.c[id(i, j)][0] += dp.c[id(i - j, d)][0];
  56.     		}
  57.     	}
  58.     }
  59.     dp.c[0][0] = 1;
  60. 	matrix a(m * m + m * m);
  61.     for(int j = 1; j <= m; j++){
  62.     	for(int d = max(1LL, j - k); d <= min(j + k, (long long)m); d++){
  63.     		a.c[id(m, j)][id(m - j + 1, d)] = 1;
  64.     	}
  65.     }
  66.  
  67.     for(int i = 1; i < m; i++){
  68.     	for(int j = 1; j <= m; j++){
  69.     		a.c[id(i, j)][id(i + 1, j)] = 1;
  70.     	}
  71.     }
  72. 	// for(int i = 0; i <= (m + 1) * (m + 1); i++){
  73.  //   	cout << dp.c[i][0] << endl;
  74.  //   }
  75.  //   for(int i = 0; i < (m + 1) * ( m + 1); i++){
  76.  //   	for(int j = 0; j < (m + 1) * ( m + 1); j++)cout << a.c[i][j] << " ";
  77.  //   	cout << endl;
  78.  //   }
  79.  //   cout << endl;
  80. 	if(m >= n){
  81. 		long long ans = 0;
  82. 		for(int i = 1; i <= m; i++) ans = (ans + dp.c[id(n, i)][0]) % mod;
  83. 		cout << ans;
  84. 	}else{
  85. 	a = powermod(a, n - m) * dp;
  86. 	long long ans = 0;
  87.     for(int i = 1; i <= m; i++) ans = (ans + a.c[id(m, i)][0]) % mod;
  88.     // for(int i = 0; i < (m + 1) * ( m + 1); i++){
  89.     // 	for(int j = 0; j < (m + 1) * ( m + 1); j++)cout << a.c[i][j] << " ";
  90.     // 	cout << endl;
  91.     // }
  92.  
  93.  
  94.     cout << ans;}
  95.  
  96.  
  97.  
  98.  
  99.  
  100. 	// cout << a.c[0][0];
  101.  
  102. }
Success #stdin #stdout 0.25s 17144KB
comments (?)
stdin 
4 3 1
stdout 
5
https://ideone.com/ErZV3L
language:
C++14 (clang 8.0)
created:
2 days 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!