暴力：

 

正解：

考虑循环矩阵，f[i][j]表示从i点到j点的方案数

我们发现n很小，我们预处理出n次的f[i][j]

然后在矩阵快速幂中，我们要从当前的f[i][j]*f[j][k]-->fir[i][j]

但是此时的循环为三层

我们考虑转移式子的意义在0-n次从i-j，在n+1到2×n转移至j

这样此时的j-k其实可以把他看作从0开始走j-k步本质上是一样的

然后还有一个特判，就不讲了

for(int j=0;j

 

代码

1 #include
      
        2 #define int long long 3 #define MAXN 4001 4 using namespace std; 5 int c[MAXN],f[MAXN],fir[MAXN]; 6 int n,m; 7 const int mod=1e9+7; 8 void cheng(int k) 9 {10      memset(c,0,sizeof(c));11      if(k==1)12      {13         for(int i=0;i
       
        >=1ll;44      }45 }46 int ff[4ll][MAXN];int g[MAXN];47 int now,last;int ans[MAXN];48 signed main()49 {50      //freopen("text.in","r",stdin);51      //freopen("1.out","w",stdout);52      scanf("%lld%lld",&n,&m);53      int now=1;int last=0;54      ff[0][0]=1;55      for(int i=1;i<=n;++i)56      {57          if(i>1)58          {59              swap(now,last);memset(ff[now],0,sizeof(ff[now]));60          }61          for(int j=0;j