「jzoj5335」早苗 - 动态规划+矩阵快速幂

题目大意

    Sanae准备对大结界进行一次连续$n$天的风祭。Sanae每天可以召唤一种神风。她一共有$m$种神风可以召唤，但是如果有连续$m$天刮了$m$种不同的神风，环境就会遭到破坏。现在，Sanae想知道这$n$天她有多少种召唤神风的方案。
    由于答案可能很大，所以你只需要告诉她方案数对$10^9+7$取模的结果即可。

---

题目分析

设$f[i,j]$表示前$i$天，最后有$j$天刮了不同的风，即可写出很简单的转移方程：

$$f[i+1,j+1]+=f[i,j]\times(m-j)$$ $$f[i+1,k]+=f[i,j]\quad(k\in[1,j])$$

将第一维去掉，第二维视作一个DAG，即可利用矩阵快速幂优化动规过程了。

---

代码

$MinGW$编译器莫名RE，竟然让我上传一个full bug report？？
换成$cygwin$就没问题了。

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

typedef long long LL;

inline const LL Get_Int() {
	LL num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

const int maxn=105;
const LL mod=1e9+7;
struct Matrix {
	LL n,m,a[maxn][maxn];
	Matrix(LL n,LL m) {
		init(n,m);
	}
	Matrix(LL n,LL m,char E) { //单位矩阵
		init(n,m);
		for(int i=1; i<=n; i++)a[i][i]=1;
	}
	void init(LL n,LL m) {
		this->n=n;
		this->m=m;
		memset(a,0,sizeof(a));
	}
	LL* operator [] (const LL x) {
		return a[x];
	}
	Matrix operator * (Matrix b) {
		Matrix c(n,b.m);
		for(int i=1; i<=n; i++)
			for(int j=1; j<=b.m; j++)
				for(int k=1; k<=m; k++)
					c[i][j]=(c[i][j]+a[i][k]*b[k][j])%mod;
		return c;
	}
	void operator *= (Matrix b) {
		*this=*this*b;
	}
	Matrix operator ^ (LL b) {
		Matrix ans(n,m,'e'),a=*this;
		while(b>0) {
			if(b&1)ans=ans*a;
			a*=a;
			b>>=1;
		}
		return ans;
	}
};

LL n,m,ans=0;

int main() {
	n=Get_Int();
	m=Get_Int();
	Matrix A(1,m),B(m,m);
	A[1][1]=m;
	for(int i=1; i<m; i++) {
		if(i+1!=m)B[i][i+1]=m-i;
		for(int j=1; j<=i; j++)B[i][j]=1;
	}
	A=A*(B^(n-1));
	for(int i=1; i<m; i++)ans=(ans+A[1][i])%mod;
	printf("%lld\n",ans);
	return 0;
}