题目

分析

设表示每一行的状态，用一个4位的二进制来表示，当前这一行中的每一个位数对下一位有没有影响。

设\(f_{i,s}\)表示，做完了的i行，其状态为s，的方案数。

两个状态之间是否可以转移就留给读者自己思考了。

答案就是\(f_{n,0}\)因为最后一行对下一行不能造成影响。

然而，这样只有60分。

100分是个矩阵快速幂，

B矩阵构造很简单，当两个状态\(s、s'\)可以转移，那么，B矩阵\(g_{s,s'}=1\)。

当i等于零时， A矩阵为{1, 0 \(<\)repeats 15 times\(>\)}

#include <cmath>

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <queue>

const long long maxlongint=2147483647;

const long long N=500005;

using namespace std;

long long m,n,e[16][16]=

{

{1,0,0,1,0,0,0,0,0,1,0,0,1,0,0,1},

{0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0},

{0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0},

{1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0},

{0,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0},

{0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0},

{0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0},

{0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0},

{0,1,0,0,1,0,0,1,0,0,0,0,0,0,0,0},

{1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0},

{0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0},

{0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0},

{1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0},

{0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0},

{0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0},

{1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}

};

long long r[16]={1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},f[16],g[16][16];

long long time()

{

	long long f1[16];

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

		f1[i]=f[i];

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

	{

		f[i]=0;

		for(int j=0;j<=15;j++)

			f[i]=(f[i]+f1[j]*g[j][i]%m)%m;

	}

}

long long time1()

{

	long long f1[16][16];

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

		for(int j=0;j<=15;j++)

			f1[i][j]=g[i][j];

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

		for(int j=0;j<=15;j++)

		{

			g[i][j]=0;

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

			{

				g[i][j]=(g[i][j]+f1[i][k]*f1[k][j]%m)%m;

			}

		}

}

long long mi(long long x)

{

	while(x)

	{

		if(x&1) time();

		time1();

		x/=2;

	}

}

int main()

{

	while(1)

	{

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

			f[i]=r[i];

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

			for(int j=0;j<=15;j++)

				g[i][j]=e[i][j];

		scanf("%lld%lld",&n,&m);

		if(n==0 && m==0) break;

		mi(n);

		cout<<f[0]<<endl;

	}

}

巴特西

【NOIP2016提高A组模拟9.17】数格子

题目

分析

最新文章

热门文章