题目传送门（内部题17）
输入格式
一行两个整数$n$，$m$，含义如题面。
输出格式
一行一个整数，表示方案数模$1e9+7$。
样例
样例输入1：
4 6
样例输出1：
0
样例输入2：
707 185547
样例输出2：
588828156
数据范围与提示
对于$20\%$的数据，$mleqslant 20$。
对于$60\%$的数据，$mleqslant 1,000$。
对于$100\%$的数据，$mleqslant 1e9,nleqslant 1,000$。
题解
这道题原题题意有误，我在上面已经做了修改。
$40\%$算法：
直接输出$0$就好啦，我也很震惊居然有这么多分～
时间复杂度：$Theta(1)$。
期望得分：$0$分。
实际得分：$40$分。
$60\%$算法：
设$dp[i][j]$表示在第$i$步到$j$的方案数，那么很轻松的就能列出状态转移方程：$dp[i][j]=dp[i-1][j-i]+dp[i-1][j+i]$。
时间复杂度：$Theta(n imes m)$。
期望得分：$60$分。
实际得分：$60$分（结合上面的“算法”可以得到$80$分）。
$100\%$算法：
发现我们可以只预处理出来前$n$步的情况，然后用快速幂处理$left lceil frac{m}{n}
ight
ceil$次，后$mmod n$步再暴力走完，时间复杂度不允许？循环矩阵哇，可以感性的理解为将步数向右推一位。
时间复杂度：$Theta(n^2 imes log m)$。
期望得分：$100$分。
实际得分：$100$分。
代码时刻
#include<bits/stdc++.h>
using namespace std;
long long n,m;
long long dp[1001][1001];
long long wzc[1001],flag[1001],ans[1001];
void matrix1()
{
for(long long i=0;i<n;i++)flag[i]=ans[i],ans[i]=0;
for(long long i=0;i<n;i++)
for(long long j=0;j<n;j++)
ans[(i+j)%n]=(ans[(i+j)%n]+flag[i]*wzc[j]%1000000007)%1000000007;
}
void matrix2()
{
for(long long i=0;i<n;i++)flag[i]=wzc[i],wzc[i]=0;
for(long long i=0;i<n;i++)
for(long long j=0;j<n;j++)
wzc[(i+j)%n]=(wzc[(i+j)%n]+flag[i]*flag[j]%1000000007)%1000000007;
}
int main()
{
scanf("%lld%lld",&n,&m);
dp[0][0]=1;
for(long long i=1;i<=n;i++)
for(long long j=0;j<n;j++)
{
if((j-i+n)%n==(j+i)%n)dp[i][j]=dp[i-1][(j+i)%n];
else dp[i][j]=(dp[i-1][(j-i+n)%n]+dp[i-1][(j+i)%n])%1000000007;
}
for(long long i=0;i<n;i++)
wzc[i]=dp[n][i];
ans[0]=1;
long long bs=m/n;
while(bs)
{
if(bs&1)matrix1();
matrix2();
bs>>=1;
}
bs=m%n;
for(long long i=0;i<n;i++)
dp[0][i]=ans[i];
for(long long i=1;i<=bs;i++)
for(long long j=0;j<n;j++)
{
if((j-i+n)%n==(j+i)%n)dp[i][j]=dp[i-1][(j+i)%n];
else dp[i][j]=(dp[i-1][(j-i+n)%n]+dp[i-1][(j+i)%n])%1000000007;
}
printf("%lld",dp[bs][0]);
return 0;
}
rp++