CCPC－Wannafly & Comet OJ 夏季欢乐赛（2019）E

这个题暴好啊，考了很多东西。

首先设f(x)为离终点还有x步要走的期望步数，我们可以发现 :

1.x>=k时，x可以转移到的点的下标都<x。

2.x<k时，则可能走回到x或者下标更大的点。

因为k特别小，所以我们可以把 f(0) (显然是0)，f(1)，f(2)，.....，f(k-1) 暴力高斯消元出来 (这个你们不会的话可以试着把每个0<x<k的x的等式写出来，然后把f(x)项全移到左边，其他项全移到右边，就可以得到一个方程；这样可以列k-1个方程，正好k-1个未知数，高斯消元模板)。

这样我们就解决了2.情况。于是对于大量1.情况，我们便可以用2.情况推的下标比较小的f() 做矩阵乘法。

所以这就是两个题：先建一个矩阵然后高斯消元，再建一个然后矩阵快速幂，最后再做一次向量乘矩阵就可以得到答案了。

#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int N=23,ha=1000000007;

inline int add(int x,int y){ x+=y; return x>=ha?x-ha:x;}

inline void ADD(int &x,int y){ x+=y; if(x>=ha) x-=ha;}

inline int ksm(int x,int y){

	int an=1;

	for(;y;y>>=1,x=x*(ll)x%ha) if(y&1) an=an*(ll)x%ha;

	return an;

}

int k,inv,Inv,ans;

ll n;

struct node{

	int a[N][N];

	inline void clear(){ memset(a,0,sizeof(a));}

	inline void Base(){

		clear();

		for(int i=0;i<=k;i++) a[i][i]=1;

	}

    node operator *(const node &u)const{

    	node r; r.clear();

    	for(int l=0;l<=k;l++)

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

    	        for(int j=0;j<=k;j++) ADD(r.a[i][j],a[i][l]*(ll)u.a[l][j]%ha);

    	return r;

	}

	inline void build(){

		clear(),a[k][k]=1;

		for(int i=1;i<k;i++){

			a[i][k]=(i*2>k)?1:k*(ll)Inv%ha,a[i][i]=1;

			for(int j=1,to;j<=k;j++){

				to=i-j;

				if(to<0) to=-to;

				if(to&&to!=i) ADD(a[i][to],ha-((i*2>k)?inv:Inv));

			}

		}

	}

	inline void solve(){

		for(int i=1,ne;i<k;i++){

			for(int j=i;j<k;j++) if(a[j][i]){ ne=j; break;}

			if(ne!=i) for(int l=i;l<=k;l++) swap(a[ne][l],a[i][l]);

			int ni=ksm(a[i][i],ha-2),now;

			for(int j=i+1;j<k;j++){

				now=ni*(ll)a[j][i]%ha;

				for(int l=i;l<=k;l++) ADD(a[j][l],ha-a[i][l]*(ll)now%ha);

			}

		}

		for(int i=k-1;i;i--){

			for(int j=i+1;j<k;j++) ADD(a[i][k],ha-a[i][j]*(ll)a[j][k]%ha);

			a[i][k]=a[i][k]*(ll)ksm(a[i][i],ha-2)%ha;

//			printf("%d %d\n",i,a[i][k]);

		}

	}

	inline void init(){

        clear();

        for(int i=k-2;i>=0;i--) a[i+1][i]=1;

        for(int i=0;i<k;i++) a[i][k-1]=inv;

        a[k][k-1]=1,a[k][k]=1;

	}

}A,X,ANS;

int main(){

	scanf("%lld%d",&n,&k),inv=ksm(k,ha-2),Inv=ksm(k-1,ha-2);

	if(k==1){ printf("%d\n",n%ha); return 0;}

	A.build(),A.solve(),X.init();

	n-=k-1,ANS.Base();

	for(;n;n>>=1,X=X*X) if(n&1) ANS=ANS*X;

	for(int i=0;i<=k;i++) ADD(ans,A.a[i][k]*(ll)ANS.a[i][k-1]%ha);

	printf("%d\n",ans);

	return 0;

}

巴特西

CCPC－Wannafly & Comet OJ 夏季欢乐赛（2019）E

最新文章

热门文章