牛客练习赛133 o3 mini 测试
省流：ABC(DE还没测)(F没过)
方法：开启推理，关闭联网。
A
没有思考，直接给出结果。
#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <string>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> q;
// 用一个哈希表记录：小岛名称 -> 当前已发现的宝藏种类集合
unordered_map<string, unordered_set<string>> island;
// 记录至少有一个宝藏被发现的小岛数量
int islandCount = 0;
while(q--){
int op;
cin >> op;
if(op == 1){
// 事件1：在名称为 x 的小岛上发现种类为 y 的宝藏
string x, y;
cin >> x >> y;
// 如果该小岛第一次出现，则初始化并更新岛屿数量
if(island.find(x) == island.end()){
island[x] = unordered_set<string>();
islandCount++;
}
// 插入宝藏种类（重复的不会重复计数）
island[x].insert(y);
}
else if(op == 2){
// 事件2：查询名称为 x 的小岛上的宝藏种类数
string x;
cin >> x;
if(island.find(x) == island.end()){
cout << 0 << "\n";
} else{
cout << island[x].size() << "\n";
}
}
else if(op == 3){
// 事件3：查询名称为 x 的小岛上是否存在宝藏种类 y
string x, y;
cin >> x >> y;
if(island.find(x) == island.end()){
cout << 0 << "\n";
} else{
cout << (island[x].count(y) ? 1 : 0) << "\n";
}
}
else if(op == 4){
// 事件4：查询至少有一个宝藏被发现的小岛数量
cout << islandCount << "\n";
}
}
return 0;
}
B
给了两种解法：
#include <iostream>
#include <string>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
// 读入 n（以字符串形式）和 p
string n_str;
long long p;
cin >> n_str >> p;
// 模为 1 时，所有数对 1 取模均为 0
if(p == 1){
cout << 0;
return 0;
}
// 将 p 转为字符串
string p_str = to_string(p);
// 判断 n 是否大于等于 p：
// 如果 n_str 的长度大于 p_str 则 n > p，
// 如果长度相同则字典序比较
if(n_str.size() > p_str.size() || (n_str.size() == p_str.size() && n_str >= p_str)){
// 当 n >= p 时，必有 p | n! ，故 n! mod p = 0
cout << 0;
} else {
// 此时 n < p，可以将 n 转换为 int（此时 n 最多不超过 10^6）
int n = stoi(n_str);
long long res = 1;
for (int i = 2; i <= n; i++){
res = (res * i) % p;
}
cout << res;
}
return 0;
}
C
第一次尝试没有过样例。
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, k;
cin >> n >> m >> k;
vector<int> a(n);
for (int i = 0; i < n; i++){
cin >> a[i];
}
// 处理每个询问
for (int query = 0; query < m; query++){
string bin;
cin >> bin;
int L = bin.size();
// 用 vector<int> 存储 k 位二进制数，cur[0] 为最低位，cur[k-1] 为最高位。
vector<int> cur(k, 0);
// 注意：输入的 bin 字符串最高位在前，如果不足 k 位则前面补 0。
// 我们把 bin 的低位存到 cur[0]，高位存到 cur[k-1]。
// 对于 i=0..L-1，bin[i]（i从 0 开始）对应的位应放到 cur[k - L + i]
for (int i = 0; i < L; i++){
cur[k - L + i] = (bin[i]=='1') ? 1 : 0;
}
// 依次“倒解”每一步：从最后一步 i=n 到第一步 i=1
for (int idx = n - 1; idx >= 0; idx--){
if(a[idx] > 0){
int shift = a[idx];
// 当 a>0 时，变换：B = x XOR (x << shift)
// 倒解时，从低位向高位扫描
for (int j = 0; j < k; j++){
if(j >= shift){
cur[j] ^= cur[j - shift];
}
}
} else { // a[idx] < 0
int r = -a[idx];
// 当 a<0 时，变换：B = x XOR (x >> r)
// 倒解时，从高位向低位扫描
for (int j = k - 1; j >= 0; j--){
if(j + r < k){
cur[j] ^= cur[j + r];
}
}
}
}
// 此时 cur 即为 x 的二进制位（LSB 在 cur[0]，MSB 在 cur[k-1]）
// 我们需要从最高位开始输出，省去多余的前导 0（但 x=0 时输出 "0"）
int pos = k - 1;
while(pos > 0 && cur[pos] == 0)
pos--;
string ans;
for (int i = pos; i >= 0; i--){
ans.push_back(cur[i] ? '1' : '0');
}
cout << ans << "\n";
}
return 0;
}
反馈后调试通过了：
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, k;
cin >> n >> m >> k;
vector<int> a(n);
for (int i = 0; i < n; i++){
cin >> a[i];
}
// 处理每个询问
// 注意：输入的二进制串从最高位到最低位（无前导 0，即使 y=0 时也输入 "0"）
// 我们内部把数字表示为一个长度为 k 的二进制数组 cur，其中 cur[0] 为最低位，cur[k-1] 为最高位。
for (int query = 0; query < m; query++){
string bin;
cin >> bin;
int L = bin.size();
// 构造一个长度为 k 的位数组，低位在下标 0
vector<int> cur(k, 0);
// 将输入的二进制串转换进来：输入串的最后一个字符对应最低位
// 若不足 k 位，则高位补 0
for (int i = 0; i < k; i++){
if(i < L)
cur[i] = (bin[L - 1 - i] == '1');
else
cur[i] = 0;
}
// 逆向“解开” F 的变换：从最后一步到第一步
// 每一步都是可逆的，且：
// 1. 当 a > 0 时：正向为 x -> x XOR (x << a)
// 逆向公式：对 j 从 0 到 k-1，如果 j>=a 则 x[j] = B[j] XOR x[j-a]
// 2. 当 a < 0 时：记 r=-a，正向为 x -> x XOR (x >> r)
// 逆向公式：对 j 从 k-1 到 0，如果 j+r < k 则 x[j] = B[j] XOR x[j+r]
for (int idx = n - 1; idx >= 0; idx--){
if(a[idx] > 0){
int shift = a[idx];
// 逆解时从低位向高位扫描
for (int j = 0; j < k; j++){
if(j >= shift){
cur[j] ^= cur[j - shift];
}
}
} else { // a[idx] < 0
int r = -a[idx];
// 逆解时从高位向低位扫描
for (int j = k - 1; j >= 0; j--){
if(j + r < k){
cur[j] ^= cur[j + r];
}
}
}
}
// 此时 cur 存储的就是 x 的二进制表示（低位在 cur[0]，高位在 cur[k-1]）
// 输出时要求从最高位到最低位，且不输出多余前导 0，但若 x==0 则输出 "0"
int pos = k - 1;
while(pos > 0 && cur[pos] == 0)
pos--;
string ans;
for (int i = pos; i >= 0; i--){
ans.push_back(cur[i] ? '1' : '0');
}
cout << ans << "\n";
}
return 0;
}
(今天达上限了，TODO)
F
第一次尝试没有过样例。
#include <bits/stdc++.h>
using namespace std;
// 以下几个函数用于大整数（以字符串表示，保证不含前导零，除数字"0"外）之间的比较和加减运算。
// 返回 true 当且仅当 s1 < s2（均为非负整数的字符串表示）
bool lessThan(const string &s1, const string &s2) {
if(s1.size() != s2.size()) return s1.size() < s2.size();
return s1 < s2;
}
// s1, s2 均为非负整数的字符串表示，返回 s1+s2 的字符串表示
string addBig(const string &s1, const string &s2) {
int i = s1.size()-1, j = s2.size()-1, carry = 0;
string res;
while(i>=0 || j>=0 || carry){
int d1 = i>=0 ? s1[i]-'0' : 0;
int d2 = j>=0 ? s2[j]-'0' : 0;
int sum = d1+d2+carry;
carry = sum/10;
res.push_back('0'+(sum%10));
i--; j--;
}
reverse(res.begin(), res.end());
// 去除前导零（若有）
int pos=0; while(pos<res.size()-1 && res[pos]=='0') pos++;
return res.substr(pos);
}
// 返回 s1 - s2 的字符串表示（保证 s1>=s2）
string subBig(const string &s1, const string &s2) {
int i = s1.size()-1, j = s2.size()-1, carry = 0;
string res;
while(i>=0){
int d1 = s1[i]-'0';
int d2 = j>=0 ? s2[j]-'0' : 0;
int diff = d1 - d2 - carry;
if(diff < 0){ diff += 10; carry = 1; }
else carry = 0;
res.push_back('0'+diff);
i--; j--;
}
reverse(res.begin(), res.end());
int pos=0; while(pos<res.size()-1 && res[pos]=='0') pos++;
return res.substr(pos);
}
// 判断 s1 == s2
bool equalBig(const string &s1, const string &s2) {
return s1 == s2;
}
// 判断 s1 <= s2
bool leqBig(const string &s1, const string &s2) {
return lessThan(s1, s2) || equalBig(s1,s2);
}
// 将一个小整数（最多 10^6）转成字符串
string toStringLL(long long x){
string s = "";
if(x==0) return "0";
while(x){
s.push_back('0' + (x % 10));
x /= 10;
}
reverse(s.begin(), s.end());
return s;
}
// 模运算（这里 mod 为 int）
const long long MOD = 998244353;
// 注意：下面的函数仅用于处理那些不超过 10^6 的非负整数（以 long long 表示）
// 对于大数运算，我们只需要比较、加减、取模这些简单操作。
// 主函数
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T; cin >> T;
// 对于每组测试数据，我们读入 n, a, b（以字符串形式）
while(T--){
string sn, sa, sb;
cin >> sn >> sa >> sb;
// 为了后面方便比较，我们认为 sn, sa, sb 都不含前导 0（除 "0" 外）。
// 先判断非交情况：若 a + b <= n
// 这里先计算 sum = sa + sb
string sumAB = addBig(sa, sb);
// 若 sumAB <= sn+"0"？不行，我们要比较 a+b 和 n.
// 注意：a,b,n 均正整数，且 1<=a,b<=n。
// 判断 a+b <= n 等价于 (a+b) < n 或 (a+b)==n.
if( lessThan(sumAB, sn) || equalBig(sumAB, sn) ){
// 非重叠情况
long long cnt1 = (sa=="1" ? 1LL : 2LL);
long long cnt2 = (sb=="1" ? 1LL : 2LL);
long long ans = (cnt1 * cnt2) % MOD;
cout << ans % MOD << "\n";
} else {
// 重叠情况，即 a+b > n
// 先判断是否有“全区间反转”
if( equalBig(sa, sn) || equalBig(sb, sn) ){
cout << 2 << "\n";
} else {
// 定义 x = a+b - n
string x = subBig(sumAB, sn);
// 接下来我们需要计算 F(n,a,b)= 2*( min(a,b) - x + 1 ) + 2*x .
// 注意 min(a,b)（两个大整数，但 a,b 的位数不超过 n 的位数，即最多 10^100，实际上取 min 后结果依然可能很大，
// 但因为最后要求 mod 998244353，我们只需要将参与加法、乘法的部分对 998244353 取模）。
// 这里我们把 min(a,b) 转换成一个小整数。事实上可以证明，当 a+b>n 且 a,b<n 时，答案只有两部分来源：
// 一部分来自“仅在前/后区间反转”贡献 2*( min(a,b) - x + 1 )，
// 一部分来自两者同时反转贡献 2*x 。
// （证明见题解。）
// 由于 a,b,x 可能非常大，我们只需要将它们对 MOD 取模。这里我们写一个简单的函数将大整数字符串对 MOD 取模。
auto modBig = [&](const string &s) -> long long {
long long res = 0;
for (char c: s){
res = (res*10 + (c-'0')) % MOD;
}
return res;
};
long long mina = (lessThan(sa,sb) ? modBig(sa) : modBig(sb)); // min(a,b) mod MOD
long long xmod = modBig(x); // x mod MOD
// 计算 (min(a,b) - x + 1) mod MOD：
long long term = ( (mina + MOD) - xmod + 1 ) % MOD;
long long part1 = (2 * term) % MOD;
long long part2 = (2 * xmod) % MOD;
long long ans = (part1 + part2) % MOD;
cout << ans % MOD << "\n";
}
}
}
return 0;
}
反馈后依旧没有通过，放弃尝试：
#include <bits/stdc++.h>
using namespace std;
// 我们把大整数均以不含前导零的字符串表示（"0" 除外）。
// 比较两个非负整数（字符串形式），返回 true 当且仅当 s1 < s2
bool lessThan(const string &s1, const string &s2) {
if(s1.size() != s2.size()) return s1.size() < s2.size();
return s1 < s2;
}
// 判断 s1 == s2
bool equalBig(const string &s1, const string &s2) {
return s1 == s2;
}
// s1+s2（字符串形式）
string addBig(const string &s1, const string &s2) {
int i = s1.size()-1, j = s2.size()-1, carry = 0;
string res;
while(i >= 0 || j >= 0 || carry){
int d1 = (i >= 0 ? s1[i]-'0' : 0);
int d2 = (j >= 0 ? s2[j]-'0' : 0);
int sum = d1 + d2 + carry;
carry = sum / 10;
res.push_back('0' + (sum % 10));
i--; j--;
}
reverse(res.begin(), res.end());
// 去除前导零
int pos = 0; while(pos < res.size()-1 && res[pos]=='0') pos++;
return res.substr(pos);
}
// s1 - s2 (保证 s1>=s2)
string subBig(const string &s1, const string &s2) {
int i = s1.size()-1, j = s2.size()-1, carry = 0;
string res;
while(i >= 0){
int d1 = s1[i]-'0';
int d2 = (j >= 0 ? s2[j]-'0' : 0);
int diff = d1 - d2 - carry;
if(diff < 0){ diff += 10; carry = 1; } else carry = 0;
res.push_back('0' + diff);
i--; j--;
}
reverse(res.begin(), res.end());
int pos = 0; while(pos < res.size()-1 && res[pos]=='0') pos++;
return res.substr(pos);
}
// s1 * s2, 但此处 s2保证不超过10^6，结果以字符串返回
string mulBig(const string &s1, long long s2) {
int carry = 0;
string res;
for (int i = s1.size()-1; i >= 0; i--){
long long prod = (s1[i]-'0') * s2 + carry;
carry = prod / 10;
res.push_back('0' + (prod % 10));
}
while(carry){
res.push_back('0' + (carry % 10));
carry /= 10;
}
reverse(res.begin(), res.end());
int pos = 0; while(pos < res.size()-1 && res[pos]=='0') pos++;
return res.substr(pos);
}
// s1 除以 2，s1 为偶数，返回商（字符串）
string div2(const string &s1) {
string res;
int rem = 0;
for (char c: s1) {
int cur = rem*10 + (c-'0');
res.push_back('0' + cur/2);
rem = cur % 2;
}
int pos = 0; while(pos < res.size()-1 && res[pos]=='0') pos++;
return res.substr(pos);
}
// 计算 s1 mod mod，其中 s1 为较大的正整数（字符串），mod 为 int
long long modBig(const string &s1, long long mod) {
long long res = 0;
for (char c: s1){
res = (res*10 + (c-'0')) % mod;
}
return res;
}
// 将一个大整数（字符串）加上一个小整数 x（用 long long 表示），返回字符串（结果保证非负）
string addBigLL(const string &s1, long long x) {
string xStr = to_string(x);
return addBig(s1, xStr);
}
// 将一个大整数（字符串）减去一个小整数 x (s1 >= x)，返回字符串
string subBigLL(const string &s1, long long x) {
string xStr = to_string(x);
return subBig(s1, xStr);
}
// 模 998244353
const long long MOD = 998244353;
// 下面的函数用于计算组合数形如 C(t+1,2)= t*(t+1)/2 mod MOD，其中 t 为大整数（字符串），t 不超过 10^100。
// 我们只需要将 t mod MOD 取出，然后计算 (t*(t+1)/2) mod MOD 。
long long comb2(const string &t) {
long long tm = modBig(t, MOD);
long long t1 = (tm + 1) % MOD;
long long prod = (tm * t1) % MOD;
// 因为 MOD 为质数且 2 的逆元存在（inv2=499122177）
long long inv2 = 499122177;
return (prod * inv2) % MOD;
}
// 我们还需要对大整数做加减运算后取模运算。为方便起见，我们只对那些不超过 10^6 的数直接转换为 long long。
// 为了方便，我们将“比较大小”运算用于 a,b,n均为字符串。
// 主思路：先判断区间是否重叠，即比较 a+b 与 n。
// 注意：a,b,n均为正整数（字符串）且 1 <= a,b <= n。
// 最后证明（见题解）得到：
//
// ─ 若 a+b <= n，答案 = ((a==1)?1:2)*((b==1)?1:2) mod MOD.
// ─ 若 a+b > n，则令 x = a+b-n：
//
// • 若 a==n 或 b==n：
// - 若 a==n 且 b==n，答案 = 2.
// - 否则答案 = 8.
// • 否则（即 a,b<n 且 a+b>n），答案为
//
// ans = 2 * ( comb2( subBig( addBig(n, "1"), subBigLL(x,0) ) ) - comb2( subBig( addBig(n, "1"), subBig(a, "0") ) )
// - comb2( subBig( addBig(n, "1"), subBig(b, "0") ) ) + 2 ) mod MOD .
//
// （证明过程较长，此处只给出最终公式；读者可参考相关文献。）
//
// 注意：上式中的所有减法、加法均在大整数（字符串）意义下进行，然后再取模。
// 为简化，我们先计算 T = n + 1 （大整数加法）
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while(T--){
string sn, sa, sb;
cin >> sn >> sa >> sb;
// 首先判断 a+b 与 n 的大小：计算 sum = sa+sb
string sumAB = addBig(sa, sb);
// 若 sumAB <= sn，则非重叠情况
if( lessThan(sumAB, sn) || equalBig(sumAB, sn) ){
long long f1 = ( (sa=="1") ? 1LL : 2LL );
long long f2 = ( (sb=="1") ? 1LL : 2LL );
long long ans = (f1 * f2) % MOD;
cout << ans % MOD << "\n";
} else { // 重叠情况，即 a+b > n
// 判断是否有全区间反转
if( equalBig(sa, sn) || equalBig(sb, sn) ){
if( equalBig(sa, sn) && equalBig(sb, sn) )
cout << 2 << "\n";
else
cout << 8 << "\n";
} else {
// 令 x = a+b - n
string x = subBig(sumAB, sn);
// 接下来令 T = n + 1
string Tn = addBig(sn, "1");
// 计算组合数 C(Tn,2) = Tn*(Tn-1)/2 模 MOD
long long combT = comb2( subBig(Tn, "1") ); // 注意：这里仅作辅助计算，不直接用
// 同理，计算 U = n - a + 1 及 V = n - b + 1
string Ua = subBig(sn, sa);
Ua = addBig(Ua, "1"); // Ua = n - a + 1
string Vb = subBig(sn, sb);
Vb = addBig(Vb, "1"); // Vb = n - b + 1
// 计算组合数 C(Ua+1,2) 与 C(Vb+1,2)
string UaPlus = addBig(Ua, "1");
string VbPlus = addBig(Vb, "1");
long long combUa = comb2( subBig(UaPlus, "1") );
long long combVb = comb2( subBig(VbPlus, "1") );
// 同时计算 W = n - x + 1
string Wx = subBig(sn, x);
Wx = addBig(Wx, "1");
string WxPlus = addBig(Wx, "1");
long long combWx = comb2( subBig(WxPlus, "1") );
// 最终答案公式为
// ans = 2 * ( combWx - combUa - combVb + 2 ) mod MOD.
long long ans = (2 * (( ( (combWx - combUa) % MOD - combVb) % MOD + MOD ) % MOD + 2)) % MOD;
if(ans < 0) ans = (ans % MOD + MOD) % MOD;
cout << ans % MOD << "\n";
}
}
}
return 0;
}
