记录编号	144213	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]排斥反应	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	5.805 s
提交时间	2014-12-21 12:24:59	内存使用	0.32 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
using namespace std;
typedef long long LL;
const LL MOD=19921107;
const int MAXP=10,SIZES=130;
class Matrix{
public:
	int n,m;
	LL s[SIZES][SIZES];
	void clear(int n_,int m_){
		n=n_,m=m_;
		memset(s,0,sizeof(s));
	}
	void clear_I(int n_){
		clear(n_,n_);
		for(int i=0;i<n;i++) s[i][i]=1;
	}
	void print(void){
		cout<<"size: "<<n<<" "<<m<<endl;
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				cout<<s[i][j]<<" ";
			}
			cout<<endl;
		}
		cout<<endl;
	}
};
Matrix operator * (Matrix a,Matrix b){
	Matrix c;
	c.n=a.n,c.m=b.m;
	for(int i=0;i<c.n;i++){
		for(int j=0;j<c.m;j++){
			c.s[i][j]=0;
			for(int k=0;k<a.m;k++)
				c.s[i][j]=(c.s[i][j]+a.s[i][k]*b.s[k][j])%MOD;
		}
	}
	return c;
}
Matrix quickpow(Matrix a,int n){
	Matrix ans;ans.clear_I(a.n);
	while(n){
		if(n&1) ans=ans*a;
		a=a*a;
		n>>=1;
	}
	return ans;
}
int P,Q;
int id[1<<MAXP],S[SIZES];
int stot=0;
inline int getdig(int s,int i){
	return (s>>i)&1;
}
Matrix Make_D(void){
	Matrix D;
	D.clear(stot,stot);
	for(int i=0;i<stot;i++){
		for(int j=0;j<stot;j++){
			if(S[i]&S[j]) continue;
			D.s[i][j]=1;
		}
	}
	return D;
}
void work(void){
	if(Q==1){
		printf("%d\n",stot);
		return;
	}
	Matrix D=Make_D();
	D=quickpow(D,Q-1);
	LL ans=0;
	for(int i=0;i<stot;i++){
		for(int j=0;j<stot;j++){
			if(S[i]&S[j]) continue;
			ans+=D.s[i][j];
			ans%=MOD;
		}
	}
	printf("%lld\n",ans);
}
void DFS(int x,int nows){
	if(x==P){
		if(P>1&&getdig(nows,0)&&getdig(nows,P-1)) return;
		id[nows]=stot;
		S[stot]=nows;
		stot++;
		return;
	}
	if(!getdig(nows,0))	DFS(x+1,(nows<<1)|1);
	DFS(x+1,nows<<1);
}
int main(){
	freopen("react.in","r",stdin);
	freopen("react.out","w",stdout);
	scanf("%d%d",&P,&Q);
	memset(id,-1,sizeof(id));
	DFS(0,0);
	work();
	return 0;
}