http://acm.hdu.edu.cn/showproblem.php?pid=3411

        浙江理工邀请赛G题,又是一道比赛的时候没有做出来的题目,当时思路被题目给的公式限制住了,一看有除法又要取模,而且数据都很大,觉得没有办法入手,就跳过了。赛后,发现是可以构造矩阵做-_-||| 唉,被题目给的公式限制了思路啊。。。
       
                 设 An = (-q)^n
                 Sn = sigma ( Ai ),i = 0, 1,..., n              | Sn    | = | 1, 1  | * | Sn-1 |
                                                                            | An+1|    | 0, -q |    |  An  |
               Sn = ( 1 - ( -q )^n ) / ( 1 + q )
               则 f( n ) = | S(n-1) |, 注意是绝对值的S(n-1),因为题目中的f( n ) 是一个正数,就是因为这里没弄清楚WA了一次。
               以下是我的代码:

// | Sn       |    =   | 1,  1   | * | Sn-1 |
// | An+1 |          | 0, -q  |     |  An  |
#include<iostream>
using namespace std;
typedef __int64 ll;
ll p;
ll pow_mod( ll a, ll n, ll z1 )
{
    ll ans 
= 1, d = a % p;
    
while( n )
    
{
        
if( n & 1 ) ans = ( ans * d ) % p;
        d 
= ( d * d ) % p;
        n 
>>= 1;
    }

    ans 
= ( ans + z1 ) % p;
    ans 
= ( p - ans ) % p;
    
return ans;
}


void matrix_mod( ll a[][2], ll b[][2] )
{
    ll c[
2][2];
    
int i, j, k;
    memset( c, 
0sizeof( c ) );
    
for( k = 0; k < 2; k++ )
        
for( i = 0; i < 2; i++ )
            
for( j = 0; j < 2; j++ )
                c[k][i] 
+= a[k][j] * b[j][i];
    
for( i = 0; i < 2; i++ )
        
for( j = 0; j < 2; j++ )
            a[i][j] 
= c[i][j] % p;
}


ll Mod( ll x1, ll y1, ll z1, ll y2, ll z2 )
{
    
int i, j, k;
    ll q 
= pow_mod( x1, y1, z1 );
    ll a[
2][2], I1[2][2], I2[2][2];
    a[
0][0= 1, a[0][1= 1, a[1][0= 0, a[1][1= q;
    I1[
0][0= 1, I1[0][1= 0, I1[1][0= 0, I1[1][1= 1;
    
while( z2 )
    
{
        
if( z2 & 1 ) matrix_mod( I1, a );
        matrix_mod( a, a );
        z2 
>>= 1;
    }

    a[
0][0= 1, a[0][1= 1, a[1][0= 0, a[1][1= q;
    I2[
0][0= 1, I2[0][1= 0, I2[1][0= 0, I2[1][1= 1;
    
for( i = 0; i < y2; i++ )
    
{
        matrix_mod( I2, a );
        matrix_mod( a, a );
    }

    memset( a, 
0sizeof( a ) );
    
for( i = 0; i < 2; i++ )
        
for( j = 0; j < 2; j++ )
            
for( k = 0; k < 2; k++ )
                a[i][j] 
+= I1[i][k] * I2[k][j];
    
for( i = 0; i < 2; i++ )
        
for( j = 0; j < 2; j++ )
            a[i][j] 
%= p;
    
return ( a[0][0+ a[0][1* q ) % p;
}


int main( )
{
    ll x1, y1, z1, y2, z2;
    ll ans;
    
while1 )
    
{
        scanf(
"%I64d%I64d%I64d",&x1,&y1,&z1);
        
if( x1 == -1 && y1 == -1 && z1 == -1 )break;
        scanf(
"%I64d%I64d%I64d",&y2,&z2,&p);
        ans 
= Mod( x1, y1, z1, y2, z2 );
        
if( ( y2 == 0 && z2 % 2 == 1 ) || ( y2 != 0 && z2 % 2 == 0 ) )
            ans 
= p - ans;
        printf(
"%I64d\n",ans);
    }

    
return 0;
}