fork download 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define f first
  4. #define s second
  5. const ll mod = 1000000007;
  6. const int N = 105;
  7. using namespace std;
  8. int n,k,m;
  9. vector<int>v1;
  10. vector<pair<int,int>>v2;
  11. int id[105][105],cnt[105][105];
  12. struct Matrix {
  13.     ll val[N][N];
  14.     Matrix() {
  15.         for(int i = 0; i < m; i++) {
  16.             for(int j = 0; j < m; j++) {
  17.                 val[i][j] = 0;
  18.             }
  19.         }
  20.     }
  21.     void unit() {
  22.         for(int i = 0; i < m; i++) {
  23.             val[i][i] = 1;
  24.         }
  25.     }
  26. };
  27. Matrix I;
  28. Matrix operator * (Matrix x, Matrix y) {
  29.     Matrix res;
  30.     for(int i = 0; i < m; i++) {
  31.         for(int j = 0; j < m; j++) {
  32.             for(int k = 0; k < m; k++) {
  33.                 res.val[i][j] += (x.val[i][k] * y.val[k][j]) % mod;
  34.                 res.val[i][j] %= mod;
  35.             }
  36.         }
  37.     }
  38.     return res;
  39. }
  40. Matrix power(Matrix x, ll n) {
  41.     Matrix res;
  42.     res.unit();
  43.     while(n) {
  44.         if(n & 1)res = res * x;
  45.         n /= 2;
  46.         x = x * x;
  47.     }
  48.     return res;
  49. }
  50. void iswn(){
  51.     cin >> n >> k;
  52.     for(int i = 0;i < (1 << k);i++){
  53.         if(i & (i << 1))continue;
  54.         v1.push_back(i);
  55.     }
  56.     if(n == 1){cout << v1.size();return;}
  57.     for(int i = 0;i < v1.size();i++){
  58.         int x = v1[i];
  59.         for(int j = 0;j < k - 2;j++){
  60.             cnt[v1[i]][j] = __builtin_popcountll(x & 7);
  61.             x >>= 1;
  62.         }
  63.         for(int j = 0;j < v1.size();j++){
  64.             if(v1[i] & v1[j])continue;
  65.             id[v1[i]][v1[j]] = v2.size();
  66.             v2.push_back({v1[i],v1[j]});
  67.         }
  68.     }
  69.     if(n == 2){cout << v2.size();return;}
  70.     m = v2.size();
  71.     for(int i = 0;i < v2.size();i++){
  72.         for(int j = 0;j < v1.size();j++){
  73.             if(v2[i].s & v1[j])continue;
  74.             bool ok = 1;
  75.             for(int l = 0;l < k - 2;l++){
  76.                 int x = cnt[v2[i].f][l] + cnt[v2[i].s][l] + cnt[v1[j]][l];
  77.                 if(x < 2){
  78.                     ok = 0;
  79.                     break;
  80.                 }
  81.             }
  82.             if(ok){
  83.                 I.val[id[v2[i].f][v2[i].s]][id[v2[i].s][v1[j]]] = 1;
  84.             }
  85.         }
  86.     }
  87.     Matrix Fi = power(I,n-2);
  88.     ll res = 0;
  89.     for(int i = 0;i < m;i++){
  90.         for(int j = 0;j < m;j++){
  91.             res += Fi.val[i][j];
  92.             res %= mod;
  93.         }
  94.     }
  95.     cout << res;
  96. }
  97. int main(){
  98.     ios_base::sync_with_stdio(0);
  99.     cin.tie(0);cout.tie(0);
  100.     if(fopen("BAIC.INP","r")){
  101.         freopen("BAIC.INP","r",stdin);
  102.         freopen("BAIC.OUT","w",stdout);
  103.     }
  104.     int ts = 1;//cin >> ts;
  105.     while(ts--)iswn();
  106.     return 0;
  107. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin 
Standard input is empty
stdout 
1
https://ideone.com/HrW4XK
language:
C++14 (gcc 8.3)
created:
4 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!