2429.cpp

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

/* This Code is Submitted by wywcgs for Problem 2429 on 2007-01-01 at 17:33:55 */
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;
 
const int DN = 256;
const int F = 10000, FK = 4;
const int N = 128, L = 1024;
 
class BigInt {
private:
	int n[DN], len, sign;
	void format();
	bool lessThan(const BigInt&, int) const;
	void sub(const BigInt&, int);
	void add(const BigInt&);
public:
	BigInt(int e = 0) : len(1), sign(1) { memset(n, 0, sizeof(n)); n[0] = e; }
	BigInt(char*, int);
	
	void operator =(int k) { *this = BigInt(k); }
	
	bool operator <(const BigInt&) const;
	bool operator >(const BigInt& b) const { return b < *this; }
	bool operator <=(const BigInt& b) const { return !(*this > b); }
	bool operator >=(const BigInt& b) const { return !(*this < b); }
	bool operator !=(const BigInt& b) const { return *this > b || *this < b; }
	bool operator ==(const BigInt& b) const { return !(*this != b); }
	
	void operator +=(const BigInt&);
	void operator -=(const BigInt&);
	void operator *=(const BigInt&);
	void operator /=(const BigInt&);
	void operator %=(const BigInt& b) { *this -= *this/b*b; }
	
	BigInt operator +(const BigInt& b) const { BigInt r = *this; r += b; return r; }
	BigInt operator -(const BigInt& b) const { BigInt r = *this; r -= b; return r; }
	BigInt operator *(const BigInt& b) const { BigInt r = *this; r *= b; return r; }
	BigInt operator /(const BigInt& b) const { BigInt r = *this; r /= b; return r; }
	BigInt operator %(const BigInt& b) const { BigInt r = *this; r %= b; return r; }
	
	void operator +=(int k) { return *this += BigInt(k); }
	void operator -=(int k) { return *this -= BigInt(k); }
	void operator *=(int);
	void operator /=(int);
	void operator %=(int k) { return *this -= *this/k*k; }
	
	BigInt operator +(int k) const { BigInt r = *this; r += k; return r; }
	BigInt operator -(int k) const { BigInt r = *this; r -= k; return r; }
	BigInt operator *(int k) const { BigInt r = *this; r *= k; return r; }
	BigInt operator /(int k) const { BigInt r = *this; r /= k; return r; }
	BigInt operator %(int k) const { BigInt r = *this; r %= k; return r; }
	
	friend BigInt operator +(int k, const BigInt& b) { BigInt r = b; r += k; return r; }
	friend BigInt operator *(int k, const BigInt& b) { BigInt r = b; r *= k; return r; }
	
	void print() const;
	int lastDigit() const { return n[0]; }
};
BigInt::BigInt(char* str, int slen = -1) {
	memset(n, 0, sizeof(n));
	sign = (*str == '-' ? -1 : 1);
	if(!isdigit(*str)) str++;
	if(slen == -1) slen = strlen(str);
	len = (slen+FK-1)/FK;
	for(int i = slen, k = 0; i > 0; i -= FK, k++) {
		int sum = 0;
		for(int j = max(i-FK, 0); j < i; j++)
			sum = sum*10+str[j]-'0';
		n[k] = sum;
	}
	format();
}
void BigInt::format() {
	while(len > 1 && n[len-1] == 0) len--;
	if(len == 1 && n[0] == 0) sign = 1;
}
bool BigInt::lessThan(const BigInt& b, int bg = 0) const {
	if(len-bg != b.len) return len-bg < b.len;
	for(int i = len-bg-1; i >= 0; i--)
		if(n[bg+i] != b.n[i]) return n[bg+i] < b.n[i];
	return false;
}
void BigInt::add(const BigInt& b) {
	len >?= b.len;
	int r = 0;
	for(int i = 0; i < len; i++) {
		n[i] += r+b.n[i];
		r = n[i]/F; n[i] %= F;
	}
	if(r != 0) n[len++] = r;
	format();
}
void BigInt::sub(const BigInt& b, int bg = 0) {
	for(int i = 0; i < b.len; i++) {
		n[bg+i] -= b.n[i];
		if(n[bg+i] < 0) { n[bg+i] += F; n[bg+i+1]--; }
	}
	format();
}
bool BigInt::operator <(const BigInt& b) const {
	if(sign != b.sign) return sign < b.sign;
	else if(sign == 1) return lessThan(b);
	else return b.lessThan(*this);
}
void BigInt::operator +=(const BigInt& b) {
	if(sign == b.sign) add(b);
	else if(b.lessThan(*this)) sub(b);
	else {
		int cs = -sign;
		BigInt r = b; r.sub(*this);
		*this = r; sign = cs;
		format();
	}
}
void BigInt::operator -=(const BigInt& b) {
	if(sign != b.sign) add(b);
	else if(b.lessThan(*this)) sub(b);
	else {
		int cs = -sign;
		BigInt r = b; r.sub(*this);
		*this = r; sign = cs;
		format();
	}
}
void BigInt::operator *=(const BigInt& b) {
	BigInt a = *this;
	memset(n, 0, sizeof(n)); len = a.len+b.len; sign *= b.sign;
	for(int i = 0; i < a.len; i++)
		for(int j = 0; j < b.len; j++) {
			int k = i+j;
			n[k] += a.n[i]*b.n[j];
			if(n[k] >= F) { n[k+1] += n[k]/F; n[k] %= F; len >?= k+2; }
		}
	format();
}
void BigInt::operator /=(const BigInt& b) {
	BigInt a = *this;
	memset(n, 0, sizeof(n));
	len = max(a.len-b.len+1, 0); sign *= b.sign;
	for(int i = len-1; i >= 0; i--) {
		int al = a.n[max(i+b.len, a.len)-1], bl = b.n[b.len-1], ar = al+1, br = bl+1;
		if(a.len-i != b.len) { al *= F; ar *= F; }
		int l = al/br, r = ar/bl+1;
		while(r-l != 1) {
			int mid = (l+r)/2;
			if(a.lessThan(b*mid, i)) r = mid;
			else l = mid;
		}
		a.sub(b*l, i);
		n[i] = l;
	}
	if(len == 0) len++;
	format();
}
void BigInt::operator *=(int k) {
	int r = 0;
	for(int i = 0; i < len; i++) {
		n[i] = n[i]*k+r;
		r = n[i]/F; n[i] %= F;
	}
	if(r != 0) n[len++] = r;
	format();
}
void BigInt::operator /=(int k) {
	int r = 0;
	for(int i = len-1; i >= 0; i--) {
		n[i] += r*F;
		r = n[i]%k; n[i] /= k;
	}
	format();
}
void BigInt::print() const {
	if(sign == -1) putchar('-');
	printf("%d", n[len-1]);
	for(int i = len-2; i >= 0; i--)
		printf("%0*d", FK, n[i]);
}
 
int alpha[N], beta[N];
int d, c, m;
 
BigInt f(BigInt);
 
int main()
{
	char digit[L];
 
	while(scanf("%d %d %d", &d, &c, &m) != EOF && d != 0) {
		for(int i = 1; i < d; i++) scanf("%d", &alpha[i]);
		for(int i = 0; i < d; i++) scanf("%d", &beta[i]);
		scanf("%s", digit);
		if(d == 1) printf("%d\n", (beta[0]/(1-c)%m+m)%m);
		else { f(BigInt(digit)).print(); printf("\n"); }
	}
	
	return 0;
}
 
BigInt f(BigInt M)
{
	if(M < BigInt(d)) return BigInt((alpha[M.lastDigit()]%m+m)%m);
	else return ((c*f(M/d)+beta[(M%d).lastDigit()])%m+m)%m;
}