记录编号	86249	评测结果	AAAAAAAAAA
题目名称	线性递推式	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.008 s
提交时间	2014-01-23 16:51:37	内存使用	0.32 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<iomanip>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
const int SIZEN=20;
ll MOD=9973;
ll N;
int D;
class MATRIX{
public:
	ll s[SIZEN][SIZEN];
	int n,m;//n行m列
	void clear(){
		memset(s,0,sizeof(s));
		n=m=0;
	}
	MATRIX(){clear();}
	void assign_one(int x){//初始化为x*x的单位矩阵
		clear();
		m=n=x;
		for(int i=1;i<=n;i++) s[i][i]=1;
	}
	void print(void){
		cout<<"size:"<<n<<" "<<m<<endl;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++) cout<<s[i][j]<<" ";
			cout<<endl;
		}
	}
};
MATRIX operator * (MATRIX a,MATRIX b){
	MATRIX c;
	c.n=a.n,c.m=b.m;
	int i,j,k;
	for(i=1;i<=c.n;i++){
		for(j=1;j<=c.m;j++){
			for(k=1;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,ll n){//a^n
	MATRIX ans;
	ans.assign_one(a.n);
	while(n){
		if(n&1) ans=ans*a;
		a=a*a;
		n>>=1;
	}
	return ans;
}
MATRIX ori,step;
void work(void){
	scanf("%d%lld",&D,&N);
	ori.clear(),step.clear();
	ori.n=1,ori.m=D+1;
	step.n=step.m=D+1;
	for(int i=1;i<=D+1;i++) scanf("%lld",&step.s[i][D]),step.s[i][D]%=MOD;
	for(int i=1;i<D;i++) step.s[i+1][i]=1;
	step.s[D+1][D+1]=1;
	for(int i=1;i<=D;i++) scanf("%lld",&ori.s[1][i]),ori.s[1][i]%=MOD;
	ori.s[1][D+1]=1;
	ori=ori*quickpow(step,N+1-D);
	printf("%lld\n",ori.s[1][D]);
}
int main(){
	freopen("recursion.in","r",stdin);
	freopen("recursion.out","w",stdout);
	work();
	return 0;
}