牛客多校第四场 A-Ternary String(欧拉降幂)
程序员文章站
2022-04-02 21:30:27
...
Ternary String
问题分析
题意:问多长时间后可以将整个序列完全消除,每秒序列会在后面插入一个,在后面插入一个,作为序列的第一个数字将会消失。最后答案对取模。
emmm,通过打表就可以发现
假设现有一个长度为的序列,
每次序列插入一个后,我们需要秒才能将这个序列消除;
每次序列插入一个后,我们需要秒才能将这个序列消除;
每次序列插入一个后,我们需要秒才能将这个序列消除。
再来看一下数据范围,最大有,明显在处理的时候会超时。所以此时欧拉降幂就能很好的优化这种算式了。详情请看蒻刚补的欧拉定理叭。然后如果泥萌看了我的那篇欧拉定理的话,就会发现如果我们从不断嵌套求值,每次模数除了第一次都是偶数,最后我们一定可以在不多于次内将值降为,所以可以采用递归回溯计算。
。
但是这里为了方便理解,窝就贴一个非递归的代码。。因为是多组数据,因此我们需要预处理出。
#include<bits/stdc++.h>
typedef long long LL;
LL phi(LL n) {
LL ret = 1;
for (LL i = 2; i * i <= n; ++i) {
if (n % i == 0) {
n /= i, ret *= i - 1;
while (n % i == 0)
n /= i, ret *= i;
}
}
if (n > 1) ret *= n - 1;
return ret;
}
std::map<LL,LL> m;
char s[100001];
LL pow_(LL a,LL n,LL mod) {
LL ans = 1;
while (n) {
if (n & 1) ans = ans * a % mod;
a = a * a % mod;
n >>= 1;
}
return ans;
}
int main() {
LL T;
m[0] = 1e9 + 7;
for (int i = 1; i < 1e5; ++i)
m[i] = phi(m[i - 1]);
std::cin >> T;
while (T--) {
std::cin >> s;
int cnt = 0;
for (int i = 0; s[i]; ++i)
if (s[i] == '2')
cnt++;
LL ans = 0;
for (int i = 0; s[i]; ++i) {
if (s[i] == '0')
ans++, ans %= m[cnt];
else if (s[i] == '1')
ans = (ans * 2 + 2) % m[cnt];
else {
cnt--;
if (ans < m[cnt])
ans = 3 * (pow_(2, (ans + 1) % m[cnt], m[cnt]) - 1 + m[cnt]) % m[cnt];
else
ans = 3 * (pow_(2, (ans + 1) % m[cnt] + m[cnt], m[cnt]) - 1 + m[cnt]) % m[cnt];
}
}
std::cout << ans << std::endl;
}
return 0;
}
上一篇: fetch的实现原理解析
下一篇: I题(Inverse Pair)