记录编号 86249 评测结果 AAAAAAAAAA
题目名称 线性递推式 最终得分 100
用户昵称 Gravatarcstdio 是否通过 通过
代码语言 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;
}