Choosing number
--------------------------------------------------------------------------------
Time Limit: 2 Seconds Memory Limit: 65536 KB
--------------------------------------------------------------------------------
There are n people standing in a row. And There are m numbers, 1.2...m. Every one should choose a number. But if two persons standing adjacent to each other choose the same number, the number shouldn't equal or less thank. Apart from this rule, there are no more limiting conditions.
And you need to calculate how many ways they can choose the numbers obeying the rule.
Input
There are multiple test cases. Each case contain a line, containing three integer n (2 ≤ n ≤ 108), m (2 ≤ m ≤ 30000), k(0 ≤ k ≤ m).
Output
One line for each case. The number of ways module 1000000007.
Sample Input
4 4 1
Sample Output
216
--------------------------------------------------------------------------------
Author: GU, Shenlong
題意： 輸入 n m k
有n個人 選擇m個數 每個人可以任意選數 ， 當2個相鄰的人選擇相同的數 當且僅當這個數大於k 問總共有多少種方法選擇數
思路：
設x0 為上一個人選的時候選擇的小於k的數的方法數， x1為上一個人選的時候選擇的大於k的數的方法數
y0為當前人選擇的小於k的數的方法數，y1為當前人選擇的大於k的數的方法數
則有 y0=x0*(k-1)+x1*k
y1=x0*(m-k)+x1*(m-k)
這樣可以構造一個矩陣了
; k-1 k ; ;x0; ;y0
; ; * ; ; = ;
; m-k m-k ; ;x1; ;
[cpp]
#include <stdio.h>
#define N 2
#define mod 1000000007
struct mat
{
long long mar[2][2];
};
mat a,b,c,init,temp;
mat res=
{
1,0,
0,1
};
mat mul(mat a1,mat b1)
{
long long i,j,l;
mat c1;
for (i=0;i<N;i++)
{
for (j=0;j<N;j++)
{
c1.mar[i][j]=0;
for (l=0;l<N;l++)
{
c1.mar[i][j]+=(a1.mar[i][l]*b1.mar[l][j])%mod;
c1.mar[i][j]%=mod;
}
}
}
return c1;
}
mat er_fun(mat e,long long x)
{
mat tp;
tp=e;
e=res;
while(x)
{
if(x&1)
e=mul(e,tp);
tp=mul(tp,tp);
x>>=1;
}
return e;
}
long long mi(long long a,long long k,long long M)
{
long long b=1;
while(k>=1){
if(k%2==1){
b=a*b%M;
}
a=(a%M)*(a%M)%M;
k/=2;
}
return b;
}
int main()
{
long long i,j;
long long x1,x2;
long long dp[2];
long long ss;
long long n,m,k;
while(scanf("%lld%lld%lld",&n,&m,&k)!=EOF)
{
if(k!=0)
{
init.mar[0][0]=k-1;
init.mar[0][1]=k;
init.mar[1][0]=m-k;
init.mar[1][1]=m-k;
a=init;
b=er_fun(a,n-1);
dp[0]=k;
dp[1]=m-k;
ss=b.mar[0][0]*dp[0]%mod+b.mar[0][1]*dp[1]%mod+b.mar[1][0]*dp[0]%mod+b.mar[1][1]*dp[1]%mod;
ss=ss%mod;
printf("%lld\n",ss);
}
else
{
printf("%lld\n",mi(m,n,1000000007));
}
}
return 0;
}
