记录编号	372942	评测结果	AAAAAAAAAAAAREEEEE
题目名称	[HZOI 2016]你猜是不是DP V2	最终得分	66
用户昵称	_Itachi	是否通过	未通过
代码语言	C++	运行时间	1.428 s
提交时间	2017-02-19 16:43:45	内存使用	63.37 MiB

#include <stdio.h>
#define int unsigned
char ch;inline void R_int(int &x){
	while(ch=getchar(),ch<'!');x=ch-48u;
	while(ch=getchar(),ch>'!')x=x*10u+ch-48u;
}
const int maxn=11512u;
int n,g[maxn];int char f[maxn][maxn],mod[maxn],gm[maxn];
inline int get(int x){
	x^=(x>>7u)^(x<<3u)^(x>>2u);
	return (x>=n?x%n:x)+1u;
}
bool _(),__=_();signed main(){;}
bool _(){
	freopen("NC.in","r",stdin);freopen("NC.out","w",stdout);
	int x;R_int(n),R_int(x);
	register int i,j,m=n+1u,p=x,ans=0u,i0,i1,i2,i3;
	
	g[0u]=gm[0u]=1u;
	for(i=1u;i<m;i++){
		mod[i]=mod[i-1u]+1u;
		if(mod[i]==p)mod[i]=0u;		
	}
	for(i=1u;i<m;i++)g[i]=g[mod[i]]?g[mod[i]]:get(mod[i]);
	for(i=1u;i<m;i++)gm[i]=mod[g[i]];
	
	for(i=1u;i<m;i++)R_int(x),f[0][i]=x%p;
	
	for(i=1u;i<m;i++)
	for(j=1u;j<m;j+=4u)
		i0=gm[f[i-1u][j]],
		i1=gm[f[i-1u][j+1u]],
		i2=gm[f[i-1u][j+2u]],
		i3=gm[f[i-1u][j+3u]],
		f[i][j]=i0,
		f[i][j+1u]=i1,
		f[i][j+2u]=i2,
		f[i][j+3u]=i3;
		
	for(i=1u;i<m;i++)
	for(j=1u;j<m;j+=4u)
		i0=f[i-1u][j],
		i1=f[i-1u][j+1u],
		i2=f[i-1u][j+2u],
		i3=f[i-1u][j+3u],
		f[i][j]=mod[f[i][j]+f[g[i0]][g[i0+1u]]],ans+=f[i][j],
		f[i][j+1u]=mod[f[i][j+1u]+f[g[i1]][g[i1+1u]]],ans+=f[i][j+1u],
		f[i][j+2u]=mod[f[i][j+2u]+f[g[i2]][g[i2+1u]]],ans+=f[i][j+2u],
		f[i][j+3u]=mod[f[i][j+3u]+f[g[i3]][g[i3+1u]]],ans+=f[i][j+3u],ans=mod[ans];
	x=ans;printf("%u\n",x);
}