还是暴力大蛇

看到这道题，一般思路是使用动态规划。因为如果使用 DFS，显然会超时。

但是，我们可以事先在别处进行 DFS 操作，将结果记录下来，然后传入本题，直接使用。

为了解决代码太长不让提交的问题，我们可以仅将 $m≥10$ 的情况记录下来，其他情况直接 DFS 即可。

说白了就是一部分打表一部分强算

最终代码

#include<bits/stdc++.h>
using namespace std;
int n,m,ans;
long a[31][31];
void dfs(int now,int step)
{
    if(m-step<now-1&&m-step<n-now+1) return;
    if(step==m)
    {
        if(now==1) ans++;
        return;
    }
    if(now+1>n) dfs(1,step+1);
    else dfs(now+  1,step+1);//神奇ACGO会把这里屏蔽成星号
    if(now-1<1) dfs(n,step+1);
    else dfs(now-1,step+1);
    return;
}
int main()
{
    cin>>n>>m;
    a[3][10]=342,a[3][11]=682,a[3][12]=1366,a[3][13]=2730,a[3][14]=5462,a[3][15]=10922,a[3][16]=21846,a[3][17]=43690,a[3][18]=87382,a[3][19]=174762,a[3][20]=349526,a[3][21]=699050,a[3][22]=1398102,a[3][23]=2796202,a[3][24]=5592406,a[3][25]=11184810,a[3][26]=22369622,a[3][27]=44739242,a[3][28]=89478486,a[3][29]=178956970,a[3][30]=357913942,a[4][10]=512,a[4][11]=0,a[4][12]=2048,a[4][13]=0,a[4][14]=8192,a[4][15]=0,a[4][16]=32768,a[4][17]=0,a[4][18]=131072,a[4][19]=0,a[4][20]=524288,a[4][21]=0,a[4][22]=2097152,a[4][23]=0,a[4][24]=8388608,a[4][25]=0,a[4][26]=33554432,a[4][27]=0,a[4][28]=134217728,a[4][29]=0,a[4][30]=536870912,a[5][10]=254,a[5][11]=330,a[5][12]=948,a[5][13]=1430,a[5][14]=3614,a[5][15]=6008,a[5][16]=13990,a[5][17]=24786,a[5][18]=54740,a[5][19]=101118,a[5][20]=215766,a[5][21]=409640,a[5][22]=854702,a[5][23]=1652090,a[5][24]=3396916,a[5][25]=6643782,a[5][26]=13530350,a[5][27]=26667864,a[5][28]=53971350,a[5][29]=106914242,a[5][30]=215492564,a[6][10]=342,a[6][11]=0,a[6][12]=1366,a[6][13]=0,a[6][14]=5462,a[6][15]=0,a[6][16]=21846,a[6][17]=0,a[6][18]=87382,a[6][19]=0,a[6][20]=349526,a[6][21]=0,a[6][22]=1398102,a[6][23]=0,a[6][24]=5592406,a[6][25]=0,a[6][26]=22369622,a[6][27]=0,a[6][28]=89478486,a[6][29]=0,a[6][30]=357913942,a[7][10]=252,a[7][11]=110,a[7][12]=924,a[7][13]=572,a[7][14]=3434,a[7][15]=2730,a[7][16]=12902,a[7][17]=12376,a[7][18]=48926,a[7][19]=54264,a[7][20]=187036,a[7][21]=232562,a[7][22]=720062,a[7][23]=980674,a[7][24]=2789164,a[7][25]=4086550,a[7][26]=10861060,a[7][27]=16878420,a[7][28]=42484682,a[7][29]=69242082,a[7][30]=166823430,a[8][10]=272,a[8][11]=0,a[8][12]=1056,a[8][13]=0,a[8][14]=4160,a[8][15]=0,a[8][16]=16512,a[8][17]=0,a[8][18]=65792,a[8][19]=0,a[8][20]=262656,a[8][21]=0,a[8][22]=1049600,a[8][23]=0,a[8][24]=4196352,a[8][25]=0,a[8][26]=16781312,a[8][27]=0,a[8][28]=67117056,a[8][29]=0,a[8][30]=268451840,a[9][10]=252,a[9][11]=22,a[9][12]=924,a[9][13]=156,a[9][14]=3432,a[9][15]=910,a[9][16]=12870,a[9][17]=4760,a[9][18]=48622,a[9][19]=23256,a[9][20]=184796,a[9][21]=108528,a[9][22]=705894,a[9][23]=490314,a[9][24]=2708204,a[9][25]=2163150,a[9][26]=10430500,a[9][27]=9373652,a[9][28]=40313160,a[9][29]=40060078,a[9][30]=156305070,a[10][10]=254,a[10][11]=0,a[10][12]=948,a[10][13]=0,a[10][14]=3614,a[10][15]=0,a[10][16]=13990,a[10][17]=0,a[10][18]=54740,a[10][19]=0,a[10][20]=215766,a[10][21]=0,a[10][22]=854702,a[10][23]=0,a[10][24]=3396916,a[10][25]=0,a[10][26]=13530350,a[10][27]=0,a[10][28]=53971350,a[10][29]=0,a[10][30]=215492564,a[11][10]=252,a[11][11]=2,a[11][12]=924,a[11][13]=26,a[11][14]=3432,a[11][15]=210,a[11][16]=12870,a[11][17]=1360,a[11][18]=48620,a[11][19]=7752,a[11][20]=184756,a[11][21]=40698,a[11][22]=705434,a[11][23]=201894,a[11][24]=2704204,a[11][25]=961400,a[11][26]=10401250,a[11][27]=4440150,a[11][28]=40123152,a[11][29]=20030010,a[11][30]=155172330,a[12][10]=252,a[12][11]=0,a[12][12]=926,a[12][13]=0,a[12][14]=3460,a[12][15]=0,a[12][16]=13110,a[12][17]=0,a[12][18]=50252,a[12][19]=0,a[12][20]=194446,a[12][21]=0,a[12][22]=758100,a[12][23]=0,a[12][24]=2973350,a[12][25]=0,a[12][26]=11716252,a[12][27]=0,a[12][28]=46333566,a[12][29]=0,a[12][30]=183739940,a[13][10]=252,a[13][11]=0,a[13][12]=924,a[13][13]=2,a[13][14]=3432,a[13][15]=30,a[13][16]=12870,a[13][17]=272,a[13][18]=48620,a[13][19]=1938,a[13][20]=184756,a[13][21]=11970,a[13][22]=705432,a[13][23]=67298,a[13][24]=2704156,a[13][25]=354200,a[13][26]=10400602,a[13][27]=1776060,a[13][28]=40116656,a[13][29]=8584290,a[13][30]=155118390,a[14][10]=252,a[14][11]=0,a[14][12]=924,a[14][13]=0,a[14][14]=3434,a[14][15]=0,a[14][16]=12902,a[14][17]=0,a[14][18]=48926,a[14][19]=0,a[14][20]=187036,a[14][21]=0,a[14][22]=720062,a[14][23]=0,a[14][24]=2789164,a[14][25]=0,a[14][26]=10861060,a[14][27]=0,a[14][28]=42484682,a[14][29]=0,a[14][30]=166823430,a[15][10]=252,a[15][11]=0,a[15][12]=924,a[15][13]=0,a[15][14]=3432,a[15][15]=2,a[15][16]=12870,a[15][17]=34,a[15][18]=48620,a[15][19]=342,a[15][20]=184756,a[15][21]=2660,a[15][22]=705432,a[15][23]=17710,a[15][24]=2704156,a[15][25]=106260,a[15][26]=10400600,a[15][27]=592020,a[15][28]=40116600,a[15][29]=3121560,a[15][30]=155117522,a[16][10]=252,a[16][11]=0,a[16][12]=924,a[16][13]=0,a[16][14]=3432,a[16][15]=0,a[16][16]=12872,a[16][17]=0,a[16][18]=48656,a[16][19]=0,a[16][20]=185136,a[16][21]=0,a[16][22]=708512,a[16][23]=0,a[16][24]=2725408,a[16][25]=0,a[16][26]=10532160,a[16][27]=0,a[16][28]=40870080,a[16][29]=0,a[16][30]=159189120,a[17][10]=252,a[17][11]=0,a[17][12]=924,a[17][13]=0,a[17][14]=3432,a[17][15]=0,a[17][16]=12870,a[17][17]=2,a[17][18]=48620,a[17][19]=38,a[17][20]=184756,a[17][21]=420,a[17][22]=705432,a[17][23]=3542,a[17][24]=2704156,a[17][25]=25300,a[17][26]=10400600,a[17][27]=161460,a[17][28]=40116600,a[17][29]=950040,a[17][30]=155117520,a[18][10]=252,a[18][11]=0,a[18][12]=924,a[18][13]=0,a[18][14]=3432,a[18][15]=0,a[18][16]=12870,a[18][17]=0,a[18][18]=48622,a[18][19]=0,a[18][20]=184796,a[18][21]=0,a[18][22]=705894,a[18][23]=0,a[18][24]=2708204,a[18][25]=0,a[18][26]=10430500,a[18][27]=0,a[18][28]=40313160,a[18][29]=0,a[18][30]=156305070,a[19][10]=252,a[19][11]=0,a[19][12]=924,a[19][13]=0,a[19][14]=3432,a[19][15]=0,a[19][16]=12870,a[19][17]=0,a[19][18]=48620,a[19][19]=2,a[19][20]=184756,a[19][21]=42,a[19][22]=705432,a[19][23]=506,a[19][24]=2704156,a[19][25]=4600,a[19][26]=10400600,a[19][27]=35100,a[19][28]=40116600,a[19][29]=237510,a[19][30]=155117520,a[20][10]=252,a[20][11]=0,a[20][12]=924,a[20][13]=0,a[20][14]=3432,a[20][15]=0,a[20][16]=12870,a[20][17]=0,a[20][18]=48620,a[20][19]=0,a[20][20]=184758,a[20][21]=0,a[20][22]=705476,a[20][23]=0,a[20][24]=2704708,a[20][25]=0,a[20][26]=10405800,a[20][27]=0,a[20][28]=40157550,a[20][29]=0,a[20][30]=155402532,a[21][10]=252,a[21][11]=0,a[21][12]=924,a[21][13]=0,a[21][14]=3432,a[21][15]=0,a[21][16]=12870,a[21][17]=0,a[21][18]=48620,a[21][19]=0,a[21][20]=184756,a[21][21]=2,a[21][22]=705432,a[21][23]=46,a[21][24]=2704156,a[21][25]=600,a[21][26]=10400600,a[21][27]=5850,a[21][28]=40116600,a[21][29]=47502,a[21][30]=155117520,a[22][10]=252,a[22][11]=0,a[22][12]=924,a[22][13]=0,a[22][14]=3432,a[22][15]=0,a[22][16]=12870,a[22][17]=0,a[22][18]=48620,a[22][19]=0,a[22][20]=184756,a[22][21]=0,a[22][22]=705434,a[22][23]=0,a[22][24]=2704204,a[22][25]=0,a[22][26]=10401250,a[22][27]=0,a[22][28]=40123152,a[22][29]=0,a[22][30]=155172330,a[23][10]=252,a[23][11]=0,a[23][12]=924,a[23][13]=0,a[23][14]=3432,a[23][15]=0,a[23][16]=12870,a[23][17]=0,a[23][18]=48620,a[23][19]=0,a[23][20]=184756,a[23][21]=0,a[23][22]=705432,a[23][23]=2,a[23][24]=2704156,a[23][25]=50,a[23][26]=10400600,a[23][27]=702,a[23][28]=40116600,a[23][29]=7308,a[23][30]=155117520,a[24][10]=252,a[24][11]=0,a[24][12]=924,a[24][13]=0,a[24][14]=3432,a[24][15]=0,a[24][16]=12870,a[24][17]=0,a[24][18]=48620,a[24][19]=0,a[24][20]=184756,a[24][21]=0,a[24][22]=705432,a[24][23]=0,a[24][24]=2704158,a[24][25]=0,a[24][26]=10400652,a[24][27]=0,a[24][28]=40117356,a[24][29]=0,a[24][30]=155125640,a[25][10]=252,a[25][11]=0,a[25][12]=924,a[25][13]=0,a[25][14]=3432,a[25][15]=0,a[25][16]=12870,a[25][17]=0,a[25][18]=48620,a[25][19]=0,a[25][20]=184756,a[25][21]=0,a[25][22]=705432,a[25][23]=0,a[25][24]=2704156,a[25][25]=2,a[25][26]=10400600,a[25][27]=54,a[25][28]=40116600,a[25][29]=812,a[25][30]=155117520,a[26][10]=252,a[26][11]=0,a[26][12]=924,a[26][13]=0,a[26][14]=3432,a[26][15]=0,a[26][16]=12870,a[26][17]=0,a[26][18]=48620,a[26][19]=0,a[26][20]=184756,a[26][21]=0,a[26][22]=705432,a[26][23]=0,a[26][24]=2704156,a[26][25]=0,a[26][26]=10400602,a[26][27]=0,a[26][28]=40116656,a[26][29]=0,a[26][30]=155118390,a[27][10]=252,a[27][11]=0,a[27][12]=924,a[27][13]=0,a[27][14]=3432,a[27][15]=0,a[27][16]=12870,a[27][17]=0,a[27][18]=48620,a[27][19]=0,a[27][20]=184756,a[27][21]=0,a[27][22]=705432,a[27][23]=0,a[27][24]=2704156,a[27][25]=0,a[27][26]=10400600,a[27][27]=2,a[27][28]=40116600,a[27][29]=58,a[27][30]=155117520,a[28][10]=252,a[28][11]=0,a[28][12]=924,a[28][13]=0,a[28][14]=3432,a[28][15]=0,a[28][16]=12870,a[28][17]=0,a[28][18]=48620,a[28][19]=0,a[28][20]=184756,a[28][21]=0,a[28][22]=705432,a[28][23]=0,a[28][24]=2704156,a[28][25]=0,a[28][26]=10400600,a[28][27]=0,a[28][28]=40116602,a[28][29]=0,a[28][30]=155117580,a[29][10]=252,a[29][11]=0,a[29][12]=924,a[29][13]=0,a[29][14]=3432,a[29][15]=0,a[29][16]=12870,a[29][17]=0,a[29][18]=48620,a[29][19]=0,a[29][20]=184756,a[29][21]=0,a[29][22]=705432,a[29][23]=0,a[29][24]=2704156,a[29][25]=0,a[29][26]=10400600,a[29][27]=0,a[29][28]=40116600,a[29][29]=2,a[29][30]=155117520,a[30][10]=252,a[30][11]=0,a[30][12]=924,a[30][13]=0,a[30][14]=3432,a[30][15]=0,a[30][16]=12870,a[30][17]=0,a[30][18]=48620,a[30][19]=0,a[30][20]=184756,a[30][21]=0,a[30][22]=705432,a[30][23]=0,a[30][24]=2704156,a[30][25]=0,a[30][26]=10400600,a[30][27]=0,a[30][28]=40116600,a[30][29]=0,a[30][30]=155117522;
    if(m<10)
    {
        dfs(1,0);
        cout<<ans;
    }
    else cout<<a[n][m];
    return 0;
}