Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

uses math;
const z=1000000000;
var n,m,i,j,s,mx,t,y:longint;
    f:array[1..100,0..1 shl 14] of longint;

begin
     while not eof do
     begin
          read(n,m);
          mx:=1 shl (2*m+1)-1;
          fillchar(f,sizeof(f),0);
          for j:=0 to m do f[1,1 shl (j+m)+1 shl m-1]:=1;
          for i:=2 to n do
            for s:=0 to mx do
              if f[i-1,s]>0 then
              begin
                   if s shr 1 and 1=0 then
                   begin
                        t:=s shr 1+1;
                        inc(f[i,t],f[i-1,s]);
                        if f[i,t]>=z then dec(f[i,t],z);
                   end
                   else
                   begin
                        y:=min(2*m+1,n+m-i+1);
                        for j:=1 to y do
                            if s shr j and 1=0 then
                            begin
                                 t:=(1 shl j+s) shr 1;
                                 inc(f[i,t],f[i-1,s]);
                                 if f[i,t]>=z then dec(f[i,t],z);
                            end;
                   end;
              end;
          writeln(f[n,1 shl (m+1)-1]);
     end;
end.

Code mẫu của happyboy99x

#include<algorithm>
#include<iostream>
#include<cstring>
#include<bitset>
#include<vector>
using namespace std;

const int N = 100, M = 6, MODULO = 1000000000;

int factorial(int n) {
    int res = 1;
    for(int i = 1; i <= n; ++i)
        res = 1LL * res * i % MODULO;
    return res;
}

int BruteForce(int n, int m) {
    vector<int> per (n);
    for(int i = 0; i < n; ++i) per[i] = i;
    int res = 0;
    do {
        bool ok = true;
        for(int i = 0; i < n && ok; ++i) {
            ok &= abs(per[i] - i) <= m;
        }
        if(ok) ++res;
    } while(next_permutation(per.begin(), per.end()));
    return res;
}

int f[N + 1][1 << (2 * M + 1)];

int main() {
    ios::sync_with_stdio(false);
    for(int m, n; cin >> n >> m; ) {
        if(m >= n - 1) {
            cout << factorial(n) << '\n';
        } else {
            int totalMask = 1 << (2 * m + 1);
            memset(f, 0, sizeof f);
            f[0][((1 << m) - 1) << (m + 1)] = 1;
            for(int i = 0; i < n; ++i) {
                for(int mask = 0; mask < totalMask; ++mask) {
                    if(f[i][mask] > 0) {
//                        cerr << "F(" << i << ", " << bitset<7>(mask).to_string() << ") = " << f[i][mask] << endl;
                        for(int j = max(0, i - m); j < min(n, i + m + 1); ++j) {
                            if((mask & 1 << (m - j + i)) == 0) {
                                int newMask = ((mask | 1 << (m - j + i)) << 1) & (totalMask - 1);
                                if(i + m + 1 >= n) newMask |= 1;
//                                cerr << bitset<7>(newMask).to_string() << endl;
                                f[i + 1][newMask] = (f[i + 1][newMask] + f[i][mask]) % MODULO;
                            }
                        }
                    }
                }
            }
            cout << f[n][totalMask - 1] << '\n';
//            cerr << BruteForce(n, m) << '\n';
        }
    }
    return 0;
}

Code mẫu của ladpro98

#include <bits/stdc++.h>
const int N = 110;
const int MOD = 1000000000;
using namespace std;
int t, m, n;
int F[N][1 << 13];

int main() {
    while (scanf("%d %d", &n, &m) != EOF) {
        memset(F, 0, sizeof F);
        F[1][0] = 1;
        for(int i = 1; i <= n; i++) {
            int l = max(1, i - m), r = min(n, i + m);
            int lim = r - l + 1;
            for(int j = 0; j < (1 << lim); j++) {
                for(int k = 0; k < lim; k++)
                if ((j & (1 << k)) == 0) {
                    int next = j + (1 << k);
                    if (i >= m + 1) {
                        if (next & 1) next >>= 1;
                        else continue;
                    }
                    F[i + 1][next] = (F[i + 1][next] + F[i][j]) % MOD;
                }
            }
        }
        int res = 0;
        for(int i = 0; i < (1 << m + 1); i++)
            res = (res + F[n][i]) % MOD;
        printf("%d\n", res);
    }
    return 0;
}

Code mẫu của RR

const
  res:array[0..100,0..6] of longint=(
(0,1,1,1,1,1,1),
(0,1,1,1,1,1,1),
(0,2,2,2,2,2,2),
(0,3,6,6,6,6,6),
(0,5,14,24,24,24,24),
(0,8,31,78,120,120,120),
(0,13,73,230,504,720,720),
(0,21,172,675,1902,3720,5040),
(0,34,400,2069,6902,17304,30960),
(0,55,932,6404,25231,76110,172200),
(0,89,2177,19708,95401,329462,899064),
(0,144,5081,60216,365116,1441923,4553166),
(0,233,11854,183988,1396948,6487445,22934774),
(0,377,27662,563172,5316192,29555588,116914351),
(0,610,64554,1725349,20135712,135025756,610093513),
(0,987,150639,5284109,76227216,615260976,222826972),
(0,1597,351521,16177694,288878956,791161792,101449940),
(0,2584,820296,49526506,95937420,618600768,706002192),
(0,4181,1914208,151635752,159450913,8446080,654768640),
(0,6765,4466904,464286962,783649241,708989200,274267136),
(0,10946,10423761,421566698,878012558,42944564,313508416),
(0,17711,24324417,352505527,128287882,435858788,129749632),
(0,28657,56762346,326304313,543171080,888017477,822765632),
(0,46368,132458006,802053896,198646496,665958797,900630896),
(0,75025,309097942,926806216,132725784,89640318,515065868),
(0,121393,721296815,497958000,439463906,353956314,861681452),
(0,196418,683185225,122069784,731589482,508086040,518547105),
(0,317811,927803988,709284968,399580847,997868856,769607257),
(0,514229,165743600,628154457,859146849,553980624,667692238),
(0,832040,388759708,73801961,856272280,357751400,766434666),
(0,1346269,911830577,683817146,475723944,147148728,92369240),
(0,2178309,471963129,692636638,809822368,504265442,21000920),
(0,3524578,793641686,715532344,884553600,846714538,690207984),
(0,5702887,245200926,542958886,836739072,661682903,149631408),
(0,9227465,45568402,561997774,232939992,98194105,840721808),
(0,14930352,766589599,922310971,251368472,260059144,820444296),
(0,24157817,551617921,831061101,508113457,477521080,542842872),
(0,39088169,400730960,76861388,815549697,644089856,759061602),
(0,63245986,89440192,134377508,775835386,336957312,402938698),
(0,102334155,236547824,606748072,541177678,716685824,564494703),
(0,165580141,507967969,242927724,228577016,94393792,631451489),
(0,267914296,643198401,522989132,858889352,341665728,117841944),
(0,433494437,358761490,388667677,645991352,75718952,259541544),
(0,701408733,644018726,212345237,779872406,277915016,217709248),
(0,134903170,337886430,234516758,387037278,466017273,543752640),
(0,836311903,885327871,209705506,430943775,339194601,696798336),
(0,971215073,415494793,238028360,861539817,355281402,93335808),
(0,807526976,148000956,495726122,670133268,902498606,885368192),
(0,778742049,422638928,821356114,543825852,946077496,557993280),
(0,586269025,338381012,528413999,671012736,902243416,463864384),
(0,365011074,87436065,128246449,534983328,465630032,785308632),
(0,951280099,604655193,25770512,755445264,500488552,650719992),
(0,316291173,738071454,834723792,191093636,309682424,782491249),
(0,267571272,228376110,929302752,86804772,709708982,174769473),
(0,583862445,327681594,315468272,93670897,952181150,585728570),
(0,851433717,44070031,749555024,470838201,915050235,481050254),
(0,435296162,940237089,952200945,71899334,737286893,40986104),
(0,286729879,797765912,484333329,131714066,196400012,73341560),
(0,722026041,455295776,971909490,921274792,950193812,380291984),
(0,8755920,463384136,645528310,748937456,595543408,624938928),
(0,730781961,478230065,654060120,119911960,561016192,609776560),
(0,739537881,926814593,49053502,5898186,716502848,66404520),
(0,470319842,982631546,358038582,377087954,748658432,275684888),
(0,209857723,466427446,885940115,491093151,524231696,395148470),
(0,680177565,323099942,778779397,841384961,387181020,969210494),
(0,890035288,133232911,787486100,236001968,865752428,932411647),
(0,570212853,272506121,782253196,72182096,563596317,886478985),
(0,460248141,208580580,302991896,201642944,101031317,113429684),
(0,30460994,217199536,384096996,819233280,725130486,135766524),
(0,490709135,656311372,360010292,473221248,310704258,154935056),
(0,521170129,596550993,27706581,231365552,493859832,145567808),
(0,11879264,354994937,384943965,948448560,732635032,875167616),
(0,533049393,814032038,159475470,117373729,282779216,337590848),
(0,544928657,603966526,420749210,12213313,591062984,679901952),
(0,77978050,261611554,943193960,569767026,402781144,684472320),
(0,622906707,554736191,811614626,273328534,261879754,950185072),
(0,700884757,962410497,755295802,184665304,692105810,742661476),
(0,323791464,634012064,255599463,42121112,608030959,931984740),
(0,24676221,773529984,840706409,797243512,674103217,114153777),
(0,348467685,210269408,116578584,739058878,765253136,135186425),
(0,373143906,133826753,196511000,186529990,301803120,350273734),
(0,721611591,852302977,650139472,252678127,427779712,39753330),
(0,94755497,491132706,887204488,29309801,340449792,878669560),
(0,816367088,476388934,785030328,192577900,810669056,107814104),
(0,911122585,447114414,706885577,61141412,330949504,621199280),
(0,727489673,742667487,143009913,181250592,834488832,354933168),
(0,638612258,585809865,241795626,312290592,271190096,751906384),
(0,366101931,574715852,266023246,467471632,8574480,237347464),
(0,4714189,158377744,430276216,15151772,576249265,844681816),
(0,370816120,41260804,287966870,289066428,299301137,966552010),
(0,375530309,489285825,137637406,632005249,900031474,378587154),
(0,746346429,709517273,155496875,240474329,112351062,967783967),
(0,121876738,926840302,529510877,183936894,446934744,271751425),
(0,868223167,673874510,871378012,957177754,996199608,593692592),
(0,990099905,725522762,555379252,888358216,684606928,601864272),
(0,858323072,815440303,315764872,767550464,738464200,998956544),
(0,848422977,269112353,274286108,344669208,643878104,222983296),
(0,706746049,62429928,623041436,207658930,600104478,978978048),
(0,555169026,81865952,66248909,180754746,597644614,867439104),
(0,261915075,976433848,573110885,295017423,164197555,971686656),
(0,817084101,262287249,789115910,983520481,938945669,763763584));

var
  m,n:longint;

begin
  while not eof(input) do
    begin
      readln(m,n);
      writeln(res[m,n]);
    end;
end.

Code mẫu của hieult

#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<list>
//#include<conio.h>
#define ep 0.000000001
#define maxn 10011
#define oo 1111111
#define mod 1000000000
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
#define fi first 
#define se second
double const PI=4*atan(1);

using namespace std;

typedef pair<int, int> II;
typedef vector<int> VI;
typedef vector<II> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;

int n, k;
int f[105][1 << 12];

int main(){
    //freopen("input.in","r",stdin); 
    //freopen("output.out","w",stdout);

    while(scanf("%d %d",&n,&k) > 0){

        memset(f, 0 ,sizeof (f));
        f[0][(1 << k) - 1] = 1;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < (1 << (2 * k)); j++){
                if(!(j & 1)){
                    f[i + 1][j >> 1] = (f[i + 1][j >> 1] + f[i][j]) % mod;
                }
                else{
                    f[i + 1][j >> 1 | (1 << (2 * k - 1))] = (f[i + 1][j >> 1 | (1 << (2 * k - 1))] + f[i][j]) % mod;
                    for(int t = 1; t < 2 * k ; t ++) if( !(j >> t & 1)){
                        f[i + 1][j >> 1 | (1 << (t - 1))] = (f[i + 1][j >> 1 | (1 << (t - 1))] + f[i][j]) % mod;
                    }
                }
            } 
        }
        printf("%d\n",f[n][(1 << k) - 1]);
    }     
     // getch();
}

Code mẫu của ll931110

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#define BASE 1000000000
using namespace std;

int n,k;
int f[102][4096];

int rec(int x,int v)
{
    if (f[x][v] != -1) return f[x][v];
    if (x == n) return 1;
    int ans = 0,w = v;
    if (v % 2 == 0 && x >= k) ans = rec(x + 1,v >> 1); else
    {
       v >>= 1;
       for (int i = 0; i < 2 * k; i++)
         if (i + x + 1 - k >= 0 && i + x + 1 - k < n && (v & (1 << i)) == 0)
           ans = (ans + rec(x + 1,v + (1 << i))) % BASE;    
    };

    f[x][w] = ans;  return ans;
};

int main()
{
//   freopen("per.in","r",stdin);
//    freopen("per.ou","w",stdout);
    while (cin >> n >> k)
    {
          memset(f,-1,sizeof(f));
          cout << rec(0,0) << endl;
    };
};

Code mẫu của skyvn97

#include<cstdio>
#include<cstring>
#define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1)
#define REP(i,n) for (int i=0;i<(n);i=i+1)
#define add(x,y) x=(x+(y))%mod
#define bit(x,y) (((x)|(1<<(y)))==(x))
const int mod=(int)1e9;
int f[111][(1<<13)+7];
int n,m;
void optimize(void) {
    //printf("%d %d\n",n,m);
    if (n<m) m=n;
    memset(f,0,sizeof f);
    FOR(i,1,m+1) f[1][((1<<m)-1)|(1<<(i+m-1))]++;
    FOR(i,1,n) REP(j,1<<(2*m+1)) if (f[i][j]>0) {
        //printf("f(%d,%d)=%d\n",i,j,f[i][j]);
        if (!bit(j>>1,0)) add(f[i+1][(j>>1)|1],f[i][j]);
        else {
            REP(k,2*m+1) if (k+i-m<=n && !bit(j>>1,k)) add(f[i+1][(j>>1)|(1<<k)],f[i][j]);
        }
    }
    printf("%d\n",f[n][(1<<(m+1))-1]);
}
int main(void) {
    while (scanf("%d%d",&n,&m)==2) optimize();
    return 0;
}