fork download
copy 
  1. #pragma GCC optimize("O3,unroll-loops")
  2. #include <bits/stdc++.h>
  3. #define ll long long
  4. #define int long long
  5. #define itachi ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  6.  
  7. using namespace std;
  8.  
  9. const int MOD = 1000000007;
  10. const int MAXN = 1005;
  11. const int MAXMASK = 1 << 13;   // vì k <= 6 → 2k+1 <= 13
  12.  
  13. int n, k;
  14. int L;
  15. ll dp[MAXN][MAXMASK];
  16.  
  17. int add(int a, int b){
  18.     a += b;
  19.     if(a >= MOD) a -= MOD;
  20.     return a;
  21. }
  22.  
  23. signed main(){
  24.     itachi;
  25.     cin >> n >> k;
  26.  
  27.     L = 2 * k + 1;
  28.     int FULL = (1 << L) - 1;
  29.  
  30.     /* ======================
  31.        Khởi tạo dp[0][mask]
  32.        Cửa sổ ban đầu: [1-k , 1+k]
  33.        Các số <1 hoặc >n coi như đã dùng
  34.        ====================== */
  35.     int init_mask = 0;
  36.     for(int t = 0; t < L; t++){
  37.         int val = 1 - k + t;
  38.         if(val < 1 || val > n)
  39.             init_mask |= (1 << t);
  40.     }
  41.     dp[0][init_mask] = 1;
  42.  
  43.     /* ======================
  44.        DP theo vị trí
  45.        ====================== */
  46.     for(int i = 1; i <= n; i++){
  47.         int start = i - k; // đầu cửa sổ
  48.         for(int mask = 0; mask < (1 << L); mask++){
  49.             if(dp[i-1][mask] == 0) continue;
  50.  
  51.             // chọn 1 số trong cửa sổ để gán cho vị trí i
  52.             for(int t = 0; t < L; t++){
  53.                 if(mask & (1 << t)) continue;
  54.  
  55.                 int val = start + t;
  56.                 if(val < 1 || val > n) continue;
  57.  
  58.                 int nmask = mask | (1 << t);
  59.  
  60.                 // số sắp bị đẩy ra ngoài phải đã dùng
  61.                 if((nmask & 1) == 0) continue;
  62.  
  63.                 // dịch cửa sổ
  64.                 nmask >>= 1;
  65.  
  66.                 // thêm số mới vào cửa sổ
  67.                 if(start + L > n)
  68.                     nmask |= (1 << (L - 1));
  69.  
  70.                 dp[i][nmask] = add(dp[i][nmask], dp[i-1][mask]);
  71.             }
  72.         }
  73.     }
  74.  
  75.     cout << dp[n][FULL];
  76.     return 0;
  77. }
  78.  
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/K2hatB
language:
C++14 (gcc 8.3)
created:
20 hours 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!