题目描述

输入格式

第一行两个整数n,z
然后一行n个整数a1~an

输出格式
一个整数表示余数

输入样例1

3 52 3 2

输出样例1

2

输入样例2

5 82 2 1 2 3

输出样例2

4

样例说明
样例1:

3^2=9
2^9=512
512除以5余2

code

#include #define for1(i,n) for(i=1;i<=(n);i++)using namespace std;const int N=1005;typedef long long ll;int n,a[N],v[N],zq[N][N],t[N][N];int dfs(int dep,int z){int i,ii,w=a[dep]%z;zq[dep][0]=1;t[dep][1]=0;if(v[dep+1]){for1(i,v[dep+1]) zq[dep][i]=w*zq[dep][i-1]%z;return zq[dep][v[dep+1]];}for1(i,z){zq[dep][i]=w*zq[dep][i-1]%z;int &tt=t[dep][zq[dep][i]];ii=i-tt;if(tt) return zq[dep][tt+((dfs(dep+1,ii)-tt)%ii+ii)%ii];tt=i;}return 0;}int main(){int i,j,z;scanf("%d%d",&n,&z);n=min(n,z);for1(i,n){scanf("%d",&a[i]);if(a[i]==1) break;}n=max(1,i-1);v[n+1]=1;for(i=n;i;i--){v[i]=1;for1(j,v[i+1]){v[i]*=a[i];if(v[i]>z) break;}if(v[i]>z){v[i]=0;break;}}printf("%d\n",dfs(1,z));return 0;}

天天赞天天看！！！