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

题目

分析

设表示每一行的状态，用一个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;
	}
}