【csp模拟赛3】bridge.cpp--矩阵加速递推

题目描述

穿越了森林，前方有一座独木桥，连接着过往和未来（连接着上一题和下一题...）。这座桥无限长。

小 Q 在独木桥上彷徨了。他知道，他只剩下了 N 秒的时间，每一秒的时间里，他会向左或向右移动一步。 N 秒之后，小 Q 恰在桥上某一特定位置，且他每两次经过此位置的时间间隔不会超过 M 秒。那么问题来了，这 N 秒的时间里，小 Q 的路线总共会有多少种可能的形式。

输入

文件第一行两个正整数 N、M，如题目所描述

输出

输出一个整数，表示可能的路线数量最终模 1000000007 的结果

样例输入 1

4 2

样例输出 1

样例输入2

10 6

样例输出 2

184

数据规模与约定对于 30% 的测试数据， 2 <=N<=100 ; 对于全部测试数据， 9 2 <=N <=10 , M <=N 且 M <=100 。保证 N 和 M 都是偶数。资源限制每个测试点空间限制 256MB，时间限制 1s。一共 20 个测试点，满分 100 分。

思想：

　　　　矩阵加速递推

若只考虑从最终到达的特定位置向单一方向出发，令 F(x, y)表示在一次出行内离开最终位置 x 个单位时间时你恰好处于距最终位置 y 个单位距离的方案数。易得转移方程： F(1,1)=1，F(x,y)=F(x-1,y-1)+F(x-1,y+1). 预处理 F 数组，时间复杂度 O(M2 )。由此可直接通过递推简便地得到答案，时间复杂度 O(NM)，可通过 60%的测试数据。利用矩阵乘法优化，可将时间复杂度优化至 O(M^3*log2N)，通过全部测试数据。

代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define mod 1000000007
using namespace std;

int n,m;
long long f[200][200];
struct node {
	long long a[200][200];
	
}a,c;

inline node MUL(node a,node b) {
		node wfx;
		memset(wfx.a,0,sizeof(c.a));
		for(int i = 1;i <= m >> 1;i ++)
			for(int j = 1;j <= m >> 1;j ++)		
				for(int k = 1;k <= m >> 1;k ++)
					wfx.a[i][j] = (wfx.a[i][j] + a.a[i][k] * b.a[k][j]) % mod;
		return wfx;
	}		

inline void KSM(int y) {
	for( ; y ; y >>= 1,a = MUL(a,a))
		if(y & 1) c = MUL(c,a);
}


int main()
{
	#ifdef yilnr
	#else
	freopen("bridge.in","r",stdin);
	freopen("bridge.out","w",stdout);
	#endif
	scanf("%d%d",&n,&m);
	f[1][1]=1;
	for(int i=1;i<=m;i++)
	  for(int j=1;j<=(m>>1);j++)
	  {
	     f[i+1][j+1]=(f[i+1][j+1]+f[i][j])%mod;
		 f[i+1][j-1]=(f[i+1][j-1]+f[i][j])%mod;
	  }
	for(int i=1;i<=(m>>1)-1;i++)a.a[i+1][i]=1;
	for(int i=1;i<=(m>>1);i++)c.a[i][i] = 1,a.a[1][i]=(f[i<<1][0]<<1)%mod;
	KSM(n>>1);
	printf("%d",c.a[1][1]);
}