牛客2025年七夕节比赛-AB题解
A
暴力/诈骗题,这里 是自然底数,所以数据最大到
,可以
时间复杂度通过,希望不会有人看成
(
这个模数是
,恰好可以利用
unsigned int
的自然溢出或者与 做按位与,均可优化常数。
赛前没想到的是,本次比赛很多 TLE 的提交用了快速幂,这会导致时间复杂度变为 。
以 为例,显然
,可以通过递推优化掉快速幂。
fun fact: 顺带坑了一下 AI,因为我看到 AI 的提交清一色的快速幂,这不 T 才怪(
n1 = 1
n2 = 1
x1 = 1777777777
mod1 = 998244353
mod2 = 1000000007
mod3 = (1 << 32) - 1
x2 = 2333333333
x3 = 1145141145
x4 = 1919810191
x5 = 114514
x6 = 1919810
sum = 0
for _ in range(int(input())):
n1 *= x5
n1 %= mod1
n2 *= x6
n2 %= mod2
x = n1 * n2
x &= mod3
x ^= x1
x += x2
x &= mod3
x = (x ^ (x >> 15)) * x3 & mod3
x = (x ^ (x >> 14)) * x4 & mod3
x = x ^ (x >> 16)
sum += x
sum &= mod3
print(sum)
#include <bits/stdc++.h>
using namespace std;
constexpr unsigned mod1 = 998244353U;
constexpr unsigned mod2 = 1000000007U;
constexpr unsigned x = 1777777777U;
unsigned myhash(unsigned x) {
x += 2333333333U;
x = (x ^ (x >> 15)) * 1145141145U;
x = (x ^ (x >> 14)) * 1919810191U;
return x ^ (x >> 16);
}
int main() {
int n;
cin >> n;
unsigned sum = 0;
unsigned long long n1 = 1;
unsigned long long n2 = 1;
for (int i = 0; i < n; i++) {
n1 *= 114514U;
n1 %= mod1;
n2 *= 1919810U;
n2 %= mod2;
unsigned n3 = n1 * n2;
n3 ^= x;
unsigned n4 = myhash(n3);
sum += n4;
}
cout << sum << '\n';
}
B
提交时间需满足分和秒都含有一个 。
赛时评测机可能阻塞了,导致提交时间和评测时间差了几秒,算的不准,这里道歉了。
其实 和
提交必过,但是比赛时间是
点整到
点整(