记录编号	169879	评测结果	AAAAAAAAAA
题目名称	线性递推式	最终得分	100
用户昵称	落尘	是否通过	通过
代码语言	C++	运行时间	0.012 s
提交时间	2015-07-11 10:52:55	内存使用	0.32 MiB

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#define LL long long int
#define NUM_MOD 9973
using namespace std;
LL N;
int D;
class MATRIX{
public:
	LL s[21][21];
	int n,m;
//以下，初始化。。。
	void clear(){
		memset(s,0,sizeof(s));
		n=m=0;
	}
	MATRIX(){clear();}
//以下,单位矩阵。。。
	void NEW_MATRIX(int x){
		clear();
		m=n=x;
		for(int i=1;i<=n;++i)
			s[i][i]=1;
	}
//以下，operator* 重载。。。
	MATRIX operator* (MATRIX b){
		MATRIX c;MATRIX a=*this;//a*b
		c.n=a.n,c.m=b.m;
		for(int i=1;i<=c.n;++i)
			for(int j=1;j<=c.m;++j)
				for(int k=1;k<=a.m;++k)
					c.s[i][j]=(c.s[i][j]+a.s[i][k]*b.s[k][j])%NUM_MOD;
		return c;
	}
//以下，输出。。。
//(最后单独输出也可。。。)
	void Print(){ printf("%d\n",s[1][D]); }
}S,T;
//以下，快速幂。。。
MATRIX QUICK_POW(MATRIX a,LL n){
	MATRIX ans;
	ans.NEW_MATRIX(a.n);
	while(n){
//让我看看是奇还是偶。。。
//1UL就是1啦，但是快那么一点点。。。
		if(n&1UL)
			ans=ans*a;
		a=a*a;
		n>>=1UL;
	}
	return ans;
}
void init(){
    scanf("%d%lld",&D,&N);
//以下，初始化。。。
	S.clear(),T.clear();//初始矩阵和单位矩阵清0。。。
	S.n=1,S.m=D+1;//初始矩阵大小。。。
	T.n=T.m=D+1;//D+1阶矩阵。。。
	for(int i=1;i<=D+1;++i)
		scanf("%lld",&T.s[i][D]),
		T.s[i][D]%=NUM_MOD;//管他有没有用。。。
	for(int i=1;i<=D;++i)
		scanf("%lld",&S.s[1][i]),
		S.s[1][i]%=NUM_MOD;
//以下，设置单位矩阵。。。
	for(int i=1;i<D;++i)
		T.s[i+1][i]=1;
	S.s[1][D+1]=1;T.s[D+1][D+1]=1;//差点忘了写它们。。。
}
int main(){
    freopen("recursion.in","r",stdin);
	freopen("recursion.out","w",stdout);
	init();
	S=S*QUICK_POW(T,N+1-D);
	S.Print();
	fclose(stdin);
	fclose(stdout);
	return 0;
}