这题线性递推，需要用矩阵乘法。
构建矩阵：由于有一个常数，表示结果的矩阵需要1*2，可设A0=【x0，c】,An=【xn，c】
然后 An=【xn，c】=A0* (B^n) 由于Am(1*2)*B(2*2)=An(1*2) (n=m+1,m>=0)
所以B是个2*2的矩阵,
设B=
[b11,b12]
[b21,b22]
则 An(1,1)=Am(1,*)*B(*,1)=x*a+c=x*b11+c*b21
An(1,2)=Am(1,*)*B(*,2)=c=x*b12+c*b22
可知b11=a,b21=1,b12=0,b22=1
所以B=
[a,0]
[1,1]
然后套用矩阵乘模板求出An=A0*（B^n）即可
乘的时候要用取模的“快速”乘防止溢出。

Accepted, time = 0 ms, mem = 528 KiB, score = 100
代码：
#include<stdio.h>
typedef long long ll; 
#define GetI64(x) scanf("%I64d",&x)
#define PutI64(x,arg...) printf("%I64d" arg,x)

ll mod;

ll mul(ll a,ll b){
    ll ans=0;
    while(b){
        if(b&1)ans=(ans+a)%mod;
        a=(a+a)%mod;
        b>>=1;
    }
    return ans;
}



struct mat{
    int m,n;
    ll a[3][3];
    mat(int M=0,int N=0){m=M;n=N;}
    void clear(){
        for(int i=1;i<=m;++i){
            for(int j=1;j<=n;++j){
                a[i][j]=0;
            }
        }
    }
    ll*operator[](int d){return a[d];}
};

mat operator*(mat a,mat b){
    mat c(a.m,b.n);
    //a.n==b.m
    c.clear();
    for(int k=1;k<=a.n;++k){
        for(int i=1;i<=a.m;++i){
            for(int j=1;j<=b.n;++j){
                c[i][j]+=mul(a[i][k],b[k][j]);
                c[i][j]%=mod;
                if(c[i][j]<0)c[i][j]+=mod;
            }
        }
    }
    return c;
}

mat operator^(mat x,ll p){
    if(p==1)return x;
    if(p==2)return x*x;
    mat t=x^(p/2);
    t=t*t;
    if(p&1)t=t*x;
    return t;
}


int main(){
    ll m,a,c,x0,n,g;
    GetI64(m);GetI64(a);GetI64(c);GetI64(x0);GetI64(n);GetI64(g);
    mod=m;
    mat b(1,2);
    b[1][1]=x0;
    b[1][2]=c;
    mat f(2,2);
    f[1][1]=a;
    f[1][2]=0;
    f[2][1]=1;
    f[2][2]=1;
    mat ans=b*(f^n);
    ll x=ans[1][1]%g;
    if(x<0)x+=g;
    PutI64(x,"\n");
    return 0;
}
   

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std ;

#define ll long long

ll m , a , c , n , g , x ;

ll multi( ll y , ll cnt ) {
if ( ! cnt ) return 0 ;
if ( cnt == 1 ) return y % m ;
ll rec = multi( y , cnt / 2 ) ;
rec = ( rec + rec ) % m ;
if ( cnt % 2 ) rec = ( rec + y ) % m ;
return rec ;
}

struct maxtrix {
ll a[ 2 ][ 2 ] ;
maxtrix( ) {
memset( a , 0 , sizeof( a ) ) ;
}
void print( ) {
for ( int i = 0 ; i < 2 ; i ++ ) {
for ( int j = 0 ; j < 2 ; j ++ ) {
cout << a[ i ][ j ] << " " ;
}
cout << endl ;
}
}
};

maxtrix Multi( maxtrix m1 , maxtrix m2 ) {
maxtrix rec ;
for ( int i = 0 ; i < 2 ; i ++ ) {
for ( int j = 0 ; j < 2 ; j ++ ) {
for ( int k = 0 ; k < 2 ; k ++ ) {
rec.a[ i ][ j ] += multi( m1.a[ i ][ k ] , m2.a[ k ][ j ] ) ;
rec.a[ i ][ j ] %= m ;
}
}
}
return rec ;
}

maxtrix Pow( maxtrix x , ll cnt ) {
if ( cnt == 1 ) return x ;
maxtrix rec = Pow( x , cnt / 2 ) ;
rec = Multi( rec , rec ) ;
if ( cnt % 2 ) rec = Multi( rec , x ) ;
return rec ;
}

int main( ) {
cin >> m >> a >> c >> x >> n >> g ;
maxtrix m1 , m2 ;
m2.a[ 0 ][ 0 ] = a , m2.a[ 0 ][ 1 ] = 0 , m2.a[ 1 ][ 0 ] = c , m2.a[ 1 ][ 1 ] = 1 ;
m1.a[ 0 ][ 0 ] = x , m1.a[ 0 ][ 1 ] = 1 ;
maxtrix ans = Multi( m1 , Pow( m2 , n ) ) ;
cout << ans.a[ 0 ][ 0 ] % g << endl ;
return 0 ;
}

似乎可以不用要矩阵乘法吧……
为什么当初我看到这道题第一感觉就是推式子……
不过好像也可以做的样子……
(其实现在我也觉得是矩乘

使用矩阵乘法和快速幂，而且需要快速乘法。解题报告里有详细的矩阵乘法的推导。

基本思路矩阵+快速幂

当然这道题可能存在通项公式，而大牛可能可以求出通项公式。但这个对于普通大多数人不适合……
快速幂的思想不仅要和矩阵相结合，而且乘法也需要。因为long long直接乘肯定爆。

构建矩阵

1. x0 c

2. a 0
   1 1
   其中第2个要n次方然后乘第一个，为了方便我的矩阵乘法是针对第2个矩阵的，第一个的至于第1个乘以第2个，就直接在print里弄了。so愿大家不要打我……
   另外友情提醒，**vijos输入输出long long要用%I64d，不是标准的%lld**
   %I64d
   还有不要提交错题目了，我就是（貌似这有点sb）……
   这是代码。可能不是很好

   code

   #include<stdio.h>
   #include<string.h>
   #include<stdlib.h>
   #include<math.h>
   #define N 2
   #define M 2
   #define MAX_NUM 1000000000
   long long MU,g,c,a,n,x0;
   typedef long long matrix[N][M];
   matrix base,result,tmp1,tmp2;
   long long t;
   long long mytime(long long a,long long b)
   {
   if ((a <= MAX_NUM) && (b <= MAX_NUM))
   return (a*b)%MU;
   if ((b < 10) || (a < 10))
   return (a*b)%MU;
   if (a > b) {
   t = a; a = b; b = t;
   }
   t = mytime(b>>1,a);
   t = (t*2)%MU;
   if (b&1)
   t = (t+a)%MU;
   return t;
   }

   void mtime(long long *a,long long *b,long long r)
   {
   int static i,j,k;
   for (i = 0;i < N;i++)
   for (j = 0;j < M;j++) {
   for (k = 0,tmp2[i][j] = 0;k < M;k++)
   tmp2[i][j] = (tmp2[i][j]+mytime((a+i*M+k),*(b+k*M+j)))%MU;
   }
   for (i = 0;i < N;i++)
   for (j = 0;j < M;j++)
   *r++ = tmp2[i][j];
   }

   void power(long long *base,long long n,long long *result)
   {
   int static i,j;
   if (n == 1) {
   for (i = 0;i < N;i++)
   for (j = 0;j < M;j++)
   *result++ = *base++;
   return;
   }
   if (n&1) {/*odd*/
   power(base,n>>1,result);
   mtime(result,result,tmp1[0]);
   mtime(tmp1[0],base,result);
   } else {
   power(base,n>>1,tmp1[0]);
   mtime(tmp1[0],tmp1[0],result);
   }
   }
   void print()
   {
   long long ans,tmp;
   ans = 0;
   tmp = mytime(x0,result[0][0]);
   ans = mytime(c,result[1][0]);
   ans = (tmp+ans)%MU;
   ans %= g;
   printf("%I64d",ans);
   }
   int main()
   {

   void init();

   init();
   power(base[0],n,result[0]);
   print();
   return 0;
   }

   void init()
   {
   scanf("%I64d%I64d%I64d%I64d%I64d%I64d",&MU,&a,&c,&x0,&n,&g);
   a %= MU; c %= MU;
   base[0][0] = a; base[0][1] = 0;
   base[1][0] = 1; base[1][1] = 1;
   }

有接触过矩阵乘法的就会觉得比较简单了

这题难在两个大数相乘的时候可能会超过INT64而爆

有一种方法可以在logn的时间内得到a*b mod m

贴一下代码

function c(a,b:int64):int64;

begin

c:=0;

while b>0 do begin

if b mod 2=1 then

c:=(c+a) mod m else

a:=(a+a) mod m;

b:=b div 2; 

end;

end;

矩阵

除出题人外第一A！！！

五十分乱搞，50-85分快速幂没打好，最后15分要让a*b mod m不爆掉，猎奇的cal函数，不解释，自己看。
交了4次才A，感觉智商下降了，矩阵一开始构造错了。
type arr=array[1..2,1..2]of int64;
var
j,k,o,p,n,m:int64;
c,g,i,a:int64;
x:int64;
a1,b1:arr;
function cal(x,y:int64):int64;
var
ans:int64;
temp:int64;
begin
ans:=0;
temp:=x;
while y<>0 do
begin
if y and 1=1 then ans:=(ans+temp)mod m;
temp:=(temp+temp)mod m;
y:=y shr 1;
end;
exit(ans);
end;
function mul(a,b:arr;var c:arr):arr;
var
k,i,j:longint;
begin
fillchar(c,sizeof(c),0);
for i:=1 to 2 do
for j:=1 to 2 do
begin
for k:=1 to 2 do
c[i,j]:=(c[i,j]+cal(a[i,k],b[k,j]))mod m;
end;
exit(c);
//a1:=c;
end;
begin
readln(m,a,c,x,n,g);
a1[1,1]:=x;
a1[1,2]:=1;
b1[1,1]:=a;
b1[2,1]:=c;
b1[2,2]:=1;
while n<>0 do
begin
if n and 1=1 then
mul(a1,b1,a1);
mul(b1,b1,b1);
n:=n>>1;
end;
writeln(a1[1,1] mod g);
end.

矩阵乘法非常显然，但是后三个数据longlong一乘就爆了，所以用了一种诡异的方法解决了这个问题.......
#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;

long long m, a, c, x, n, g;
long long origin[2][2], temp[2][2], b[2][2];

int xx[64];

long long mod(long long p, long long q) {
for (int i = 0; i <= 62; ++i) {
xx[i] = p & 1;
p >>= 1;
}
long long ans = 0;
for (int i = 0; i <= 62; ++i) {
if (xx[i] & 1) {
long long z = q;
for (int j = 1; j <= i; ++j) {
z *= 2;
z %= m;
}
ans += z;
ans %= m;
}
}
return ans;
}
void pow0(long long k) {
if (k == 1) {
memcpy(b, origin, sizeof (b));
return;
}
if (k & 1) {
pow0(k - 1);
memcpy(temp, b, sizeof (b));
for (int i = 0; i < 2; ++i) {
for (int k = 0; k < 2; ++k) {
b[i][k] = ((mod(origin[i][0], temp[0][k]) % m) + mod(origin[i][1], temp[1][k]) % m) % m;
}
}
}
else {
pow0(k / 2);
memcpy(temp, b, sizeof (b));
for (int i = 0; i < 2; ++i) {
for (int k = 0; k < 2; ++k) {
b[i][k] = ((mod(temp[i][0], temp[0][k]) % m) + mod(temp[i][1], temp[1][k]) % m) % m;
}
}
}
}
int main(int argc, const char *argv[]) {
scanf("%lld %lld %lld %lld %lld %lld", &m, &a, &c, &x, &n, &g);
origin[0][0] = a % m;
origin[0][1] = c % m;
origin[1][1] = 1;
pow0(n);
printf("%lld\n", ((mod(x, b[0][0]) + b[0][1]) % m) % m % g);
return 0;
}

P1725随机数生成器 Accepted
记录信息
评测状态 Accepted
题目 P1725 随机数生成器
递交时间 2015-11-03 21:01:19
代码语言 C++
评测机 Jtwd2
消耗时间 41 ms
消耗内存 508 KiB
评测时间 2015-11-03 21:01:21
评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 480 KiB, score = 5
测试数据 #1: Accepted, time = 15 ms, mem = 476 KiB, score = 5
测试数据 #2: Accepted, time = 0 ms, mem = 480 KiB, score = 5
测试数据 #3: Accepted, time = 0 ms, mem = 480 KiB, score = 5
测试数据 #4: Accepted, time = 0 ms, mem = 476 KiB, score = 5
测试数据 #5: Accepted, time = 0 ms, mem = 484 KiB, score = 5
测试数据 #6: Accepted, time = 0 ms, mem = 480 KiB, score = 5
测试数据 #7: Accepted, time = 0 ms, mem = 484 KiB, score = 5
测试数据 #8: Accepted, time = 0 ms, mem = 480 KiB, score = 5
测试数据 #9: Accepted, time = 0 ms, mem = 484 KiB, score = 5
测试数据 #10: Accepted, time = 11 ms, mem = 496 KiB, score = 5
测试数据 #11: Accepted, time = 0 ms, mem = 496 KiB, score = 5
测试数据 #12: Accepted, time = 0 ms, mem = 500 KiB, score = 5
测试数据 #13: Accepted, time = 0 ms, mem = 500 KiB, score = 5
测试数据 #14: Accepted, time = 0 ms, mem = 500 KiB, score = 5
测试数据 #15: Accepted, time = 0 ms, mem = 508 KiB, score = 5
测试数据 #16: Accepted, time = 15 ms, mem = 504 KiB, score = 5
测试数据 #17: Accepted, time = 0 ms, mem = 500 KiB, score = 5
测试数据 #18: Accepted, time = 0 ms, mem = 504 KiB, score = 5
测试数据 #19: Accepted, time = 0 ms, mem = 504 KiB, score = 5
Accepted, time = 41 ms, mem = 508 KiB, score = 100
代码
#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;

unsigned long long m , a , c , x , n , g;

inline unsigned long long mul( unsigned long long a , unsigned long long b )
{
if( !b ) return 0;
if( b & 1 ) return ( mul( a , b - 1 ) + a ) % m;
unsigned long long t = mul( a , b >> 1 );
return ( t << 1 ) % m;
}

struct matrix
{
unsigned long long mat[2][2];
matrix( unsigned long long a , unsigned long long b , unsigned long long c , unsigned long long d )
{
mat[0][0] = a , mat[0][1] = b , mat[1][0] = c , mat[1][1] = d;
}
matrix() {}
};

inline matrix operator * ( matrix a , matrix b )
{
matrix c;
memset( c.mat , 0 , sizeof( c.mat ) );
for( register int k = 0 ; k < 2 ; k++ )
for( register int i = 0 ; i < 2 ; i++ )
for( register int j = 0 ; j < 2 ; j++ )
c.mat[i][j] += mul( a.mat[i][k] , b.mat[k][j] ) , c.mat[i][j] %= m;
return c;
}

matrix power( long long x )
{
if( !x ) return matrix( 1 , 0 , 0 , 1 );
if( x & 1 ) return matrix( a , 0 , 1 , 1 ) * power( x - 1 );
matrix a = power( x >> 1 );
return a * a;
}

int main()
{
cin >> m >> a >> c >> x >> n >> g;
matrix ans = power( n );
cout << ( matrix( x , c , 0 , 0 ) * ans ).mat[0][0] % g << endl;
return 0;
}

var
fan:array[1..2,1..2] of int64;
ans,x,i,m,a,c,n,g:int64;
function plus(aa,bb:int64):int64;
var tt,yy:int64;

begin
tt:=0 ;
yy:=aa;
while bb<>0 do
begin
if (bb and 1)=1 then

tt:=(tt+yy) mod m;

yy:=(yy+yy) mod m;
bb:=bb shr 1;
end;
exit(tt);

end;

procedure quick(b:int64);
var t,y:array[1..2,1..2] of int64;
begin
t[1,1]:=1;
t[1,2]:=0;
t[2,1]:=0;
t[2,2]:=1;
y:=fan;
while b<>0 do
begin
if (b and 1 )=1 then
begin

t[1,2]:=(plus(t[1,1],y[1,2])mod m + t[1,2] mod m) mod m;
t[1,1]:=plus(t[1,1],y[1,1] )mod m;
end;

y[1,2]:=(plus(y[1,1],y[1,2])mod m + y[1,2] mod m )mod m ;
y[1,1]:=plus(y[1,1],y[1,1])mod m;

b:=b shr 1;
end;
//writeln(t[1,1],'--',t[1,2]);
fan:=t;
end;

begin
// assign(input,'1725.in');
// reset(input);
readln(m,a,c,x,n,g);
fan[1,1]:=a;
fan[1,2]:=1;
fan[2,1]:=0;
fan[2,2]:=1;
quick(n);
ans:=((plus(fan[1,1],x) mod m +plus(fan[1,2],c) mod m) mod m )mod g;
writeln(ans);

end.

program pro;
type mine=array[1..2,1..2]of int64;
var
m,a,c,x0,n,g:int64;
ans,matrix:mine;
i,j:longint;

function cal(x,y:int64):int64;
var
ans:int64;
temp:int64;
begin
ans:=0;
temp:=x;
while y<>0 do
begin
if y and 1=1 then ans:=(ans+temp)mod m;
temp:=(temp+temp)mod m;
y:=y shr 1;
end;
exit(ans);
end;

procedure matrixc(x,y:mine; var z:mine);
var
ii,jj,kk:longint;
begin
fillchar(z,sizeof(z),0);
for ii:=1 to 2 do
for jj:=1 to 2 do
for kk:=1 to 2 do
z[ii,jj]:=(z[ii,jj]+cal(x[ii,kk],y[kk,jj]))mod m;
end;

begin
readln(m,a,c,x0,n,g);
matrix[1,1]:=a;
matrix[1,2]:=0;
matrix[2,1]:=c;
matrix[2,2]:=1;
ans[1,1]:=x0; ans[1,2]:=1;
while n<>0 do
begin
if n and 1=1 then matrixc(ans,matrix,ans);
matrixc(matrix,matrix,matrix);
n:=n shr 1;
end;
writeln(ans[1,1]mod g);
end.