记录编号	42638	评测结果	EEEEEEEEEEEEEEEEEEEE
题目名称	[NOI 2012]随机数生成器	最终得分	0
用户昵称	skyfisherman	是否通过	未通过
代码语言	C++	运行时间	1.425 s
提交时间	2012-09-27 17:47:00	内存使用	2.82 MiB

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long LL;
LL Mod,mod,X0,n;
LL f(LL a,LL b){
   int r; LL t,c; 
   a%=Mod,b%=Mod;
   for(r=0;b&&(~b&1);b>>=1,r++);
   for(c=0;b;b>>=1)c<<=1,c|=(b&1);b=c;
   for(t=0;b;b>>=1)t<<=1,t+=(b&1)?a:0,t%=Mod;
   while(r--)t<<=1,t-=(t>Mod)?Mod:0;
   return t;
}
class mat{
      public:
      LL a[2][2];
      friend::mat operator *(const mat&a,const mat&b)
      {
                  mat c;
                  for(int i=0;i<2;i++)
                          for(int j=0;j<2;j++) {
                                  LL temp=f(a.a[i][0],b.a[0][j]);
                                  temp+=f(a.a[i][1],b.a[1][j]);
                                  c.a[i][j]=temp%Mod;
                          }
                  return c;
      }
      mat power(LL n)
      {
          mat c;
          c.a[0][0]=c.a[1][1]=1; 
          c.a[1][0]=c.a[0][1]=0;
          while (n){
                if(n&1)c=c*(*this);n>>=1;
                (*this)=(*this)*(*this);
          }
          return c;
      }
      void print()
      {
           cout<< a[0][0]<< ' '<< a[0][1] << endl;
           cout<< a[1][0]<< ' '<< a[1][1] << endl;
      }
}A;
int main()
{
    freopen("random.in","r",stdin);
    freopen("random.out","w",stdout);
    scanf("%lld%lld%lld%lld%lld%lld",&Mod,&A.a[0][0],&A.a[1][0],&X0,&n,&mod);
    A.a[1][1]=1; A=A.power(n); 
    LL ans = f(X0,A.a[0][0])+A.a[1][0];
    ans%=Mod;
    ans%=mod;
    printf("%lld\n",ans);
}