放牧代码和思想
专注自然语言处理、机器学习算法
    正处于一个非常忙的阶段,抱歉不会经常回应任何联络

GCJ Japan 2011 决赛 B 题解《挑战程序设计竞赛》

目录

GCJ Japan 2011 决赛 B

细菌繁殖:x个细菌一小时后繁殖为xx个,求A个细菌B小时后的数量模C的余?

输入格式:第一行为整数T,代表T个测试用例。接着是T行,每行3个整数,代表A B C。其中数据范围如下——

1 ≤ T ≤ 500

1 ≤ A ≤ 1000

1 ≤ C ≤ 1000

Small

1 ≤ B ≤ 2

Large

1 ≤ B ≤ 1000

输出格式:Case #X: N,X为用例ID,N为答案。示例如下——

输入
 
输出
5
1 10 997
2 2 997
2 2 6
461 1 709
461 1000 709
Case #1: 1
Case #2: 256
Case #3: 4
Case #4: 674
Case #5: 461

4.1更加复杂的数学问题 

模运算的世界 

有两个月没刷题了,智商完全下线了。这是Google Code Jam Japan 2011决赛的题目B,一开始想当然地以为可以先求余再迭代,大错特错。无奈看了官方的解说,才明白是怎么回事。

定义n小时后细菌的数量为an,记bn,m=an % m。那么题目就是求 bB,C 。

根据细菌的性质,有

虽然并不成立,但是如下关系是成立的:

因为等式右边残留着an 所以无法递推 bn,m 。与其直接考虑,不如将指数 an 换为0、1、2……来观察有没有规律。取 bn,m = 14, m = 24 计算 bn,m0 mod m , bn,m1 mod m , … 有:

除了开头三个数之外,接下来都是8和16的循环节。记循环节「 8, 16, … 」周期为p,开头不规则的部分「 1, 14, 4 」长度为q,给定 bn,m 和 m 就能将p和q算出来,因为m最大1000,顶多循环1000次。

那么接下来在考虑anan也是个大数,无法直接计算。既然一个数的幂乘的余后半部分一定是循环的,那么只要知道an是否位于循环节中,以及a% p就行了。前者很简单,而后者就是bn,p

到此为止,就可以用 bn,m , bn,p  bn+1,m 表示出来了,这是一个递归的求法。由于n和p的取值在1000*1000之内,所以可以将其枚举出来,之后直接从dp cache里取答案的话就能在有限时间内算完large了。

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;

const int MAX_N = 1000;
const LL INF = 10000;

// 二维数组[i][j]表示组合i^n % j (n=0,1,2...)
int q[MAX_N + 1][MAX_N + 1];	// 组合对应的非循环节的长度
int p[MAX_N + 1][MAX_N + 1];    // 组合对应的循环节的长度
int dp[MAX_N + 1][MAX_N + 1];	// dp[b][c] := A固定、B为b、C为c时的答案 
int an[MAX_N + 1];				// an[i] = A^A迭代i次

// 初始化组合的循环节软cache
void init() 
{
	int used[MAX_N + 1];					// 记录当前值是否出现过,对应其在第几次计算时出现
	for (int i = 1; i <= MAX_N; ++i)		// 计算bn,m^[0,1,2...]对应的p、q
	{
		for (int j = 1; j <= MAX_N; ++j) 
		{
			memset(used, -1, sizeof(used));
			int step = 0;
			int x = 1;
			while (1) 
			{
				x = x * i % j;
				if (used[x] >= 0) 
				{
					q[i][j] = used[x];
					p[i][j] = step - used[x];
					break;
				}
				used[x] = step++;
			}
		}
	}
}

// return (a ^ b) % mod
LL power(LL x, LL b, LL mod) 
{
	LL ret = 1LL;

	while (b > 0) 
	{
		if (b & 1)
			ret = ret * x % mod;
		x = x * x % mod;
		b >>= 1;
	}

	return ret;
}

// return min(INF, x^b)
LL power(LL x, LL b) 
{
	LL ret = 1LL;

	while (b > 0) 
	{
		if (b & 1)
			ret = min(INF, ret * x);
		x = min(INF, x * x);
		b >>= 1;
	}

	return ret;
}

// return x^x迭代b次后除以mod的余数
int rec(int x, int b, int mod) 
{
	if (!b) return x % mod;						// 不繁殖
	if (mod == 1) return 0;
	if (dp[b][mod] >= 0) return dp[b][mod];		// 在递归过程中已经计算过

	int y = rec(x, b - 1, mod);					// 往前递归,求出b[n-1][m]
	if (!y)
		return dp[b][mod] = 0;					// i^n % j,当i=0的时候,当然为0

	int head = q[y][mod];
	int loop = p[y][mod];

	int ret;
	if (an[b - 1] <= head)						// 循环节之外
		ret = power(y, an[b - 1], mod);
	else										// 循环节之内
	{
		int z = rec(x, b - 1, loop);			            // a[n-1]%p
		z = ((z - (head + 1)) % loop + loop) % loop + 1 + head;	// 由于循环节是从head开始的,需要减掉这个head求余之后加回来
		ret = power(y, z, mod);			// b[n-1][m]^(a[n-1]) % m
	}

	return dp[b][mod] = ret;
}

void solve() 
{
	int T;

	cin >> T;
	for (int i = 0; i < T; ++i) 
	{
		int A, B, C;
		cin >> A >> B >> C;

		an[0] = A;
		for (int j = 1; j <= MAX_N; ++j)
		{
			an[j] = power(an[j - 1], an[j - 1]);
		}

		memset(dp, -1, sizeof(dp));
		int ret = rec(A, B, C);
		cout << "Case #" << i + 1 << ": " << ret << endl;
	}
}


///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
	freopen("B-large-practice.in", "r", stdin);
	freopen("out.txt", "w", stdout);

	init();
	solve();

	fclose(stdin);
	fclose(stdout);
	system("out.txt");
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

Reference

https://code.google.com/codejam/contest/dashboard?c=1363489#s=a&a=1

http://techtipshoge.blogspot.com/2012/04/google-code-jam-japan-2011.html

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » GCJ Japan 2011 决赛 B 题解《挑战程序设计竞赛》

分享到:更多 ()

评论 欢迎留言

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机