2019 IEEEXtreme 13.0 题解记录

比赛时间 2019.10.19 8:00 - 2019.10.20 8:00

比赛网站 https://csacademy.com/ieeextreme13

// 连续24小时做题真的是极限体验

// 刚比完躺了醒来就会做压轴题了，吐血 = =

Alfa Pool

题目大意

有一种比赛的计分规则为：相邻得分下一次将加倍，两次连续不得分则终止比赛，每次从1开始得分。计算有多少种方式使总分为B， B = 5 的全部情况如下表。询问包含 N 组，每次求总分为 \(B_i\) 的方案数对 1e9+7 取模的结果。

1 X 1 X 1 X 1 X 1 X X

X 1 X 1 X 1 X 1 X 1 X X

1 2 X 1 X 1 X X

X 1 2 X 1 X 1 X X

1 X 1 2 X 1 X X

X 1 X 1 2 X 1 X X

1 X 1 X 1 2 X X

X 1 X 1 X 1 2 X X

数据范围

\(1≤N≤10^4\)
\(0 \leq B_i≤10^5\)

解题思路

分别尝试直接爆搜，分块爆搜（每一块得分为 \(2^k -1\)）都 TLE ，只通过了一组测试。

由于答案没有递推性质，打表找不出规律，队友通过OEIS大法找到了该问题的数列，但求法太复杂，遂放弃。

注意到 B 不超过 1e5，最大的一部分得分为 \(2^{16} - 1=65535\)，那么全部能选的分数只有 16 种可能。

考虑设 dp[n][k] ：总得分为 n 最后一部分得分为 \(2^k-1\) 的方案数（1<=k<=16)，那么就可以写出状态转移方程了。

const int p[17] = {0,1,3,7,15,31,63,127,255,511,1023,2047,4095,8191,16383,32767,65535};

// Ans[n][0] : 总得分为 n 的全部方案数

Ans[i][0] += Ans[i][j] (1<=j<=16)

Ans[i+p[j]][j] += Ans[i][0] (1<=j<=16)

// 答案即为 2*Ans[B][0]

AC代码

#include<iostream>

#include<cstdio>

using namespace std;

const int mod = 1e9+7;

const int p[17] = {0,1,3,7,15,31,63,127,255,511,1023,2047,4095,8191,16383,32767,65535};

int Ans[100010][17];

// Ans[n][0] : ans[n]

void init() {

    Ans[0][0] = 1;

    for(int i=0;i<=100000;i++) {

        for(int j=1;j<=16;j++) {

            Ans[i][0] = (Ans[i][0] + Ans[i][j]) % mod;

        }

        for(int j=1;j<=16;j++) {

            if(i+p[j]<=100000)

                Ans[i+p[j]][j] = (Ans[i+p[j]][j] + Ans[i][0]) % mod;

        }

    }

}

int main() {

    init();

    int n; cin>>n;

    while(n--) {

        int B;

        scanf("%d", &B);

        if(B==0) printf("1\n");

        else

            printf("%d\n", 2*Ans[B][0]%mod);

    }

    return 0;

}

Ranged Alfa Pool

该题与上一题为最后两小时出的压轴题，题目背景一致，条件改为求得分在一个区间段内的方案数。同时 \(B_i\) 加强到 \(10^6\) 上限，时限 2s，能够直接才用上题思路，预处理前缀和即可。

Googolplex

题目大意

已知 \(googolplex = 10^{10^{100}}\) ，给定 X，Y，求最小的 \(t = (X^{googolplex+T}) \mod 10^Y\) 。

其中

\(1≤N≤20\)
\(1 \leq X \leq 10^8\)
\(1 \leq Y \leq 9\)
\(0 \leq T \leq 86399\)

解题思路

显然利用欧拉降幂公式直接算，枚举 T 找到最小值。

坑点：取余过程中会出现 0，那么 \(a ^ 0 = 1\)则会出现错误，本意为求 \(a ^ {phi(p)}\) 。

AC代码

// 幸亏没有罚时，经历了一路 TLE - TLE - … - WA - WA … - AC 的艰难debug历程，数论不好我的锅 T_T

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

typedef long long ll;

ll base[10] = {1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};

ll expp[10] = {2,5,40,400,4000,40000,400000,4000000,40000000,400000000};

ll qpow(ll a, ll n, ll p) {

	ll res = 1;

	while(n) {

		if(n&1) res = res * a % p;

		a = a*a % p;

		n >>= 1;

	}

	return res;

}

int main() {

	int t; cin>>t;

	while(t--) {

		ll X, Y;

		scanf("%lld %lld", &X, &Y);

		ll a = qpow(X, expp[Y], base[Y]), b = 1;

		Y = base[Y];

		ll ans = 2*Y;

		for(int T=0;T<=86399;++T) {

			ans = min(ans, a*b%Y);

			b = (b*X)%Y;

		}

		printf("%lld\n", ans);

	}

    return 0;

}

/*

// 初始版本正确写法

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

typedef long long ll;

ll base[10] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000};

ll qpow(ll a, ll n, ll p) {

	ll res = 1;

	while(n) {

		if(n&1) res = res * a % p;

		a = a*a % p;

		n >>= 1;

	}

	return res;

}

ll phi(ll x) {

	ll res = x;

	for(ll i=2;i*i<=x;i++) {

		if(x%i==0) {

			res = res/i*(i-1);

			while(x%i==0) x/=i;

		}

	}

	if(x>1) res = res/x *(x-1);

	return res;

}

ll cal(ll x, ll p) {

	ll ph1 = phi(p);

	ll ph2 = phi(ph1);

	ll ten_100 = qpow(10, 100, ph2);

	if(ten_100==0) ten_100 += ph2;			// 不写就会WA!!!

	ll ten_ten_100 = qpow(10, ten_100, ph1);

	if(ten_ten_100==0) ten_ten_100 += ph1; 	// 不写就会WA!!!

	return qpow(x, ten_ten_100, p);

}

int main() {

	int t; cin>>t;

	while(t--) {

		ll X, Y;

		scanf("%lld %lld", &X, &Y);

		Y = base[Y];

		ll a = cal(X, Y), b=1;

		ll ans = 2*Y;

		for(ll T=0;T<=86399;T++) {

			// b = qpow(X, T, Y); TLE

			ans = min(ans, a*b%Y);

			b = b*X % Y;

		}

		printf("%lld\n", ans);

	}

    return 0;

}

*/

巴特西

2019 IEEEXtreme 13.0 题解记录

Alfa Pool

题目大意

数据范围

解题思路

AC代码

Ranged Alfa Pool

Googolplex

题目大意

解题思路

AC代码

Impact Factor 影响因子

最新文章

热门文章