Choosing numberTime Limit:2 Seconds Memory Limit:65536 KB
There arenpeople standing in a row. And There aremnumbers, 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 Input4 4 1Sample Output216
题意：有n个人，1到m个数，这n个人，每人选一个数字，要求相邻的两个人选择的数要么不相等，要么相等时大于k
题解：dp[i][0]：第i个人选大于k的数的最优解，dp[i][1]：第i个人选小于等于k的数的最优解。
则 dp[i][0]=(m-k)*dp[i-1][0]+(m-k)*dp[i-1][1]
dp[i][1]=k*dp[i-1][0]+(k-1)*dp[i-1][1].
构造矩阵： | dp[i][0] | | m-k ,m-k | | dp[i-1][0] |
= *
| dp[i][1] | | k ,k-1 | | dp[i-1][1] |
#include<cstring>#include<cstdio>#include<algorithm>#include<iostream>#include<vector>#define ll long long#define mod 1000000007using namespace std;typedef vector<ll>vec;typedef vector<vec>mat;ll n,m,k;mat mul(mat &A,mat &B) {mat C(A.size(),vec(B[0].size()));for(int i=0; i<A.size(); i++) {for(int k=0; k<B.size(); k++) {for(int j=0; j<B[0].size(); j++) {C[i][j]=(C[i][j]+A[i][k]*B[k][j])%mod;}}}return C;}mat pow_mod(mat A,ll x) {mat B(A.size(),vec(A.size()));for(int i=0; i<A.size(); i++) {B[i][i]=1;}while(x>0) {if(x&1)B=mul(B,A);A=mul(A,A);x>>=1;}return B;}int main() {//freopen("test.in","r",stdin);while(~scanf("%lld%lld%lld",&n,&m,&k)) {mat A(2,vec(2));A[0][0]=m-k,A[0][1]=m-k;A[1][0]=k,A[1][1]=k-1;A=pow_mod(A,n-1);ll ans=(A[0][0]+A[1][0])*(m-k)%mod+(A[0][1]+A[1][1])*k%mod;printf("%lld\n",ans%mod);}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
，路灯和我之间，究竟谁是谁的过客，
