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, 0, sizeof( 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, 0, sizeof( 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; while( 1 ) { 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; }
|