巴中网站建设/百度如何添加店铺位置信息

bzoj2875

第一眼看是矩阵乘法+高精，顺便借此机会学了一下压八位高精

然后一直WA…拍到最后拍不下去了，索性重打了一遍，不过没用高精，用的类似快速幂的快速乘，同样解决了溢出问题~

代码：
（快速乘+矩阵乘法）

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
typedef long long ll;
using namespace std;struct matrix{ll num[10][10];
}ans,mid;
ll m,a,c,x0,n,g;ll mult(ll a,ll b)
{ll ans=0;while(b){if(b&1) ans=(ans%m+a%m)%m;a=(a%m+a%m)%m;b>>=1; }return ans;
}matrix operator *(const matrix &a,const matrix &b)
{matrix ans;for(int i=1;i<=2;i++){for(int j=1;j<=2;j++){ans.num[i][j]=0;for(int k=1;k<=2;k++){ans.num[i][j]=(ans.num[i][j]%m+mult(a.num[i][k]%m,b.num[k][j]%m)%m)%m;}}}return ans;
}ll ppow()
{while(n){if(n&1) ans=ans*mid;mid=mid*mid;n>>=1;}return ans.num[1][1]%m;
}int main()
{scanf("%lld%lld%lld%lld%lld%lld",&m,&a,&c,&x0,&n,&g);ans.num[1][1]=x0;ans.num[1][2]=1;mid.num[1][1]=a; mid.num[1][2]=0;mid.num[2][1]=c; mid.num[2][2]=1;printf("%lld",ppow()%g);return 0;
}