记录编号	327695	评测结果	AAAAAAAAAA
题目名称	[Ural 1309] 辩论	最终得分	100
用户昵称	kito	是否通过	通过
代码语言	C++	运行时间	0.015 s
提交时间	2016-10-22 19:03:49	内存使用	0.37 MiB

#include<cstdio>
using namespace std;
#define	fcl	fclose(stdin);	fclose(stdout);	return 0
	#define	SUBMIT
const int p=9973;
int n;
int A[10010],B[10010];
int Qpow(int a,int b){
	int ans=1;
	while(b){
		if(b&1){
			ans*=a;
			ans%=p;
		}
		b>>=1;
		a=a*a;
		a%=p;
	}
	return ans;
}

int main(){
	#ifdef SUBMIT
	freopen("Dispute.in","r",stdin);
	freopen("Dispute.out","w",stdout);
	#endif
	scanf("%d",&n);
	int x,y,a,b;
	A[0]=1;	B[0]=0;
	//把f[n]=g(n,f[n-1])	拆开化简，得到f[n]=f[n-1]*(n^5-n+7)+(-n^5+n^3+ 3*n) 
	//由于mod p 所以f[n]=f[n-1]*((n%p)^5-(n%p)+7)+(-(n%p)^5+(n%p)^3+3*(n%p))
	//设A为π(i=1 to n) (i^5-i+7) ，显然A是个定值。
	//把f[n]一直展开到f[0],就是f[n]=a*f[0]+b的形式。显然a=A。
	//那么设A[i],B[i]满足f[i]=A[i]*f[0]+B[i]。
	//当然了，f[p+i]=A[i]*f[p]+B[i],因为这是完整的一个周期，递推式又回来了。
	for(int i=1;i<=p;++i){
		x=Qpow(i,3);	y=Qpow(i,5);
		a=(y-i+7+p)%p;
		b=(-y+x+3*i)%p;
		A[i]=(A[i-1]*a)%p;
		B[i]=(B[i-1]*a+b)%p;
	}
	int N=n/p,Ans=0;
	for(int i=1;i<=N;++i){
		Ans=(Ans*A[p]+B[p])%p;//先推够完整的周期，其实这里可以用矩阵快速幂，但数据范围并不需要。 
	}
	Ans=(Ans*A[n%p]+B[n%p])%p;
	printf("%d",Ans);
	#ifndef SUBMIT
	getchar();	getchar();
	#endif
	fcl;
}