Choosing number

【题目类型】矩阵

&题解：

这题就和已经dp极像了,所以找方程就很困难了.可以这样找:

设f(n)是前n-1个人已经完成,第n个人选>k,g(n)是前n-1个人已经完成,第n个人选<=k.

那么f(n)=f(n-1)*(m-k)+g(n-1)*(m-k) g(n)=f(n-1)*k+g(n-1)*(k-1)

最后答案是f(n)+g(n) 所以这题难就难在想公式上

【时间复杂度】\(O(logn)\)

&代码：

#include <cstdio>

#include <bitset>

#include <iostream>

#include <set>

#include <cmath>

#include <cstring>

#include <algorithm>

#include <map>

#include <queue>

#include <vector>

using namespace std;

#define INF 0x3f3f3f3f

typedef long long ll;

const int M= 1000000007;

ll n,m,k;

struct mat

{

	ll m[4][4];

}A;

mat Mul(mat a,mat b)

{

	mat c;

	for(int i=0;i<2;i++){

		for(int j=0;j<2;j++){

			c.m[i][j]=0;

			for(int k=0;k<2;k++){

				c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j])%M;

			}

		}

	}

	return c;

}

mat bPow(mat a,ll z)

{

	mat un;

	for(int i=0;i<2;i++)for(int j=0;j<2;j++)

	un.m[i][j]=(i==j);

	while(z){

		if(z&1)

			un=Mul(un,a);

		a=Mul(a,a);

		z>>=1;

	}

	return un;

}

int tb[4];

void Init()

{

	tb[0]=m-k,tb[1]=k;

	A.m[0][0]=A.m[0][1]=m-k;

	A.m[1][0]=k,A.m[1][1]=k-1;

}

int main()

{

	freopen("E:1.txt","r",stdin);

	while(cin>>n>>m>>k){

		Init();

		A=bPow(A,n-1);

		ll ans=0;

		for(int i=0;i<2;i++)

		for(int j=0;j<2;j++){

			ans=(ans+A.m[i][j]*tb[j])%M;

		}

		cout<<ans<<endl;

	}

	return 0;

}

巴特西

ZOJ 3690 Choosing number(矩阵)

Choosing number

最新文章

热门文章