铺砖问题

题目

数据范围

50%的数据满足1<=N<=100,1<=M<=11
另外50%的数据满足1<=N<=10^200,1<=M<=5

分析

我们可以从两种数据范围分别突破，
人话：打分段。
对于第一个数据范围，我们设(f_{i,s})表示，做到第i行，这一行的状态为s，
s是一个m位的二进制数，表示这一行每个为对下一行的同一个位有没有影响。
首先预处理两个状态是否可以转移，
dp就很水了。
对于第二个数据范围，
矩阵快速幂。

#include <cmath>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
const long long maxlongint=2147483647;
const long long mo=1000000007;
const long long N=2505;
using namespace std;
long long n1[N],m,a[N][N],f[105][N],n,f1[N][N],g[N];
char s[101];
long long matrix(int k)
{
	int j=0;
	for(int i=1;i<=(1<<m)-1;i*=2)
	{
		if((k&i)==0) j++;
		else 
		{
			if(j%2==1) return 0;
			j=0;
		}
	}
	if(j%2==1) return 0;
		else return 1;
}
long long time()
{
	long long f2[N];
	for(int i=0;i<=(1<<m)-1;i++)
		f2[i]=f[0][i];
	for(int i=0;i<=(1<<m)-1;i++)
	{
		f[0][i]=0;
		for(int j=0;j<=(1<<m)-1;j++)
			f[0][i]=(f[0][i]+f2[j]*a[j][i]%mo)%mo;
	}
}
long long time1()
{
	for(int i=0;i<=(1<<m)-1;i++)
		for(int j=0;j<=(1<<m)-1;j++)
			f1[i][j]=a[i][j];
	for(int i=0;i<=(1<<m)-1;i++)
		for(int j=0;j<=(1<<m)-1;j++)
		{
			a[i][j]=0;
			for(int k=0;k<=(1<<m)-1;k++)
			{
				a[i][j]=(a[i][j]+f1[i][k]*f1[k][j]%mo)%mo;
			}
		}
}
long long chu()
{
    int k=0;
    for(int i=n1[0];i>=1;i--)
    {
        if(i-1) n1[i-1]+=(n1[i]%2)*10;
        n1[i]/=2;
    }
    while(!n1[n1[0]] && n1[0]>0)
        n1[0]--;
}
long long mi()
{
	while(n1[0])
	{
		if(n1[1]%2) time();
		time1();
		chu();
	}
}
int main()
{
	scanf("%s%lld",s,&m);
	n1[0]=strlen(s);
	for(int i=1;i<=n1[0];i++)
		n1[i]=s[n1[0]-i]-'0';
	for(int i=0;i<=(1<<m)-1;i++)
		for(int j=0;j<=(1<<m)-1;j++)
			if((i&j)==0) a[i][j]=matrix(i|j);
	if(m<=5)
	{
		f[0][0]=1;
		mi();
		printf("%lld",f[0][0]);
		return 0;
	}
	int k=1;
	if(m>5) 
		for(int i=1;i<=n1[0];i++)
		{
			n+=k*n1[i];
			k*=10;
		}
	for(int i=0;i<=(1<<m)-1;i++) 
		f[1][i]=matrix(i);
	for(int i=2;i<=n+1;i++)
		for(int j=0;j<=(1<<m)-1;j++)
			f[i][j]=0;
	for(int i=1;i<=n-1;i++)
	{
		for(int j=0;j<=(1<<m)-1;j++)
		if(f[i][j])
		{
			for(int k=0;k<=(1<<m)-1;k++)
			if(a[j][k])
			{
				f[i+1][k]=(f[i+1][k]+f[i][j])%mo;
			}
		}
	} 
	printf("%lld
",f[n][0]);
}