題目
木門道伏擊戰(intercept)
【題目背景】
建興九年（231 年）， 諸葛亮率蜀軍四出祁山。 司馬懿料到蜀軍糧草不濟，堅守
不出，又命人在成都散布諸葛亮欲謀反的謠言。劉禅聽信謠言，下旨命諸葛亮退
兵。在退兵時，魏軍決定追擊，諸葛亮早有防備，在木門道伏擊射殺張郃。
【題目描述】 小 W 在《三國演義》中讀到四出祁山，對此非常感興趣，在思考這場戰役時 他想出了一個問題。 小 W 認為蜀軍共有 N 處伏擊地點，可以把這 N 個伏擊地點從 1 到 N 進行标 号，且蜀軍恰好有 M 個兵種。 由于伏擊需要保證軍隊可以友善地排程，是以不 存在連續 M 個伏擊地點埋伏了 M 個不同的兵種。小 W 想知道所有不同的埋伏 方案數對 1e9+7 取模。
【輸入格式】
從檔案 intercept.in 中讀入資料。
一行一個數 N。
輸出格式】
輸出到檔案 intercept.out 中。
一行一個數，表示結果對 1e9+7 取模的結果。
【樣例輸入 1】
3 3
【樣例輸出 1】
21
【資料範圍】 對于 8%的資料， m=2
對于另 16%的資料， n<=10,m<=4
對于 48%的資料， n<=100000,m<=10
對于 80%的資料， n<=100000,2<=m<=100
對于 100%的資料， 2<=m<=100,m<=n<=10^16
題解
–是dp
f[i][j]：前i個位置，末尾最長不相同序列長度為j的方案數
可 以 乘 上(m-j)之 後 轉 移 到f[i+1][j+1],
也 可 以 轉 移 到f[i+1][k]（1<=k<=j）。
由于第二維隻到100，并且轉移的系數是固定的，是以可以用矩陣乘法進行優化。
代碼
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAXN=105;
const int mod=1e9+7;
long long n,m;
struct hehe{
long long f[MAXN][MAXN];
}a,b;
hehe mul(hehe a,hehe b){
hehe c;
for(int i=1;i<=m;i++)
for(int j=1;j<=m;j++){
c.f[i][j]=0;
for(int k=1;k<=m;k++)
c.f[i][j]=(c.f[i][j]+a.f[i][k]*b.f[k][j]%mod)%mod;
}
return c;
}
long long Pow(hehe a,long long b){
hehe ans;
for(int i=1;i<=m;i++)
ans.f[i][i]=1;
while(b){
if(b&1)
ans=mul(ans,a);
a=mul(a,a);
b>>=1;
}
long long sum=0;
for(int i=1;i<=m;i++)
sum=(sum+ans.f[i][1])%mod;
return sum;
}
int main(){
// freopen("intercept.in","r",stdin);
// freopen("intercept.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=m;i++)
for(int j=1;j<=m;j++){
if(i-1==j)
a.f[i][j]=m-(j-1);
else if(i==1)
a.f[i][j]=0;
else if(i<=j)
a.f[i][j]=1;
}
cout<<Pow(a,n);
return 0;
}