牛客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

提交时间需满足分和秒都含有一个
赛时评测机可能阻塞了,导致提交时间和评测时间差了几秒,算的不准,这里道歉了。
其实 提交必过,但是比赛时间是 点整到 点整(

全部评论
B 可以 20:57提交疯狂卡
3 回复 分享
发布于 08-29 21:02 湖北
这个时间啊,我搁那sleep那么久算什么
点赞 回复 分享
发布于 08-30 09:11 湖南

相关推荐

头像 会员标识
08-13 17:09
已编辑
门头沟学院 电机工程师
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
4
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务