[CSP-S模拟测试]:山洞（DP+快速幂）

题目传送门（内部题17）

输入格式

一行两个整数$n$，$m$，含义如题面。

输出格式

一行一个整数，表示方案数模$1e9+7$。

样例

样例输入1：

4 6

样例输出1：

样例输入2：

707 185547

样例输出2：

588828156

数据范围与提示

对于$20\%$的数据，$m\leqslant 20$。
对于$60\%$的数据，$m\leqslant 1,000$。
对于$100\%$的数据，$m\leqslant 1e9,n\leqslant 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\times m)$。

期望得分：$60$分。

实际得分：$60$分（结合上面的“算法”可以得到$80$分）。

$100\%$算法：

发现我们可以只预处理出来前$n$步的情况，然后用快速幂处理$\left \lceil \frac{m}{n}\right \rceil$次，后$m\mod n$步再暴力走完，时间复杂度不允许？循环矩阵哇，可以感性的理解为将步数向右推一位。

时间复杂度：$\Theta(n^2\times \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++

巴特西