2255.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 2255 on 2006-05-31 at 17:32:37 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long int64;
const int N = 10000000;
const int64 E[][2] = { { 1, 0 }, { 0, 1 } };

int64 powNum(int, int, int);
void powMat(int64[][2], int, int);
void mul(int64[][2], int64[][2], int);

int main()
{
	int t, T, i, j, k;
	int a, b, p, q, e[2];

	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		scanf("%d %d %d %d %d %d", &a, &b, &p, &q, &e[0], &e[1]);
		int mod[2]; e[0]--;
		for(i = 0; i < 2; i++) {
			if(e[i] < 0) { mod[i] = 0; continue; }
			if(p + q == 1) {
				int64 cf = p-2, cc = a*(p-1)-b, cp = b-a;
				if(cf == 0) {
					int64 x = e[i] % (2*N), y = (x*cp+2*a) % (2*N);
					mod[i] = (1+x)*y/2 % N;
				} else {
					cc = cc * e[i] % (N*cf);
					int64 r = (powNum(p-1, e[i], N*cf*cf)-1)*(p-1)/cf, sum = (cp*r+cc)/cf+a;
					mod[i] = sum % N;
				}
			} else {
				int64 rm[][2] = { { 0, 1 }, { q, p } }, rrm[][2] = { { 1-p, 1 }, { q, 1 } };
				int cd = p+q-1;
				powMat(rm, e[i]+1, cd*N);
				for(j = 0; j < 2; j++) for(k = 0; k < 2; k++) rm[j][k] -= E[j][k];
				mul(rm, rrm, cd*N);
				for(j = 0; j < 2; j++) for(k = 0; k < 2; k++) rm[j][k] /= cd;
				mod[i] = (rm[0][0]*a+rm[0][1]*b) % N;
			}
		}
		printf("%d\n", ((mod[1]-mod[0])%N+N)%N);
	}

	return 0;
}

int64 powNum(int a, int p, int m)
{
	int64 r = 1; int i;
	for(i = 31; i >= 0; i--) {
		r = r * r % m;
		if(p & (1<<i)) r = r * a % m;
	}
	return r;
}
void powMat(int64 a[][2], int p, int m)
{
	int64 r[2][2]; memcpy(r, E, sizeof(r));
	int i;
	for(i = 31; i >= 0; i--) {
		mul(r, r, m);
		if(p & (1<<i)) mul(r, a, m);
	}
	memcpy(a, r, sizeof(r));
}
void mul(int64 a[][2], int64 b[][2], int m)
{
	int64 x[2][2] = { 0 };
	int i, j, k;
	for(i = 0; i < 2; i++)
		for(j = 0; j < 2; j++)
			for(k = 0; k < 2; k++) x[i][j] = (x[i][j]+a[i][k]*b[k][j]) % m;
	memcpy(a, x, sizeof(x));
}