洛谷 P1200 [USACO1.1] 你的飞碟在这儿

// P1200 你的飞碟在这儿 —— 正解：字母变数字，连乘取模，比一比
//
// ★ 这道题是[第 47 章第 3 步](/ch/47-string-basics/)那句「字符本来就是整数」最直白的一次：
//   `c - 'A' + 1` 就是 A=1 … Z=26，**别去查表、别写 26 个 if**。
// ⚠ 唯一要小心的是那个 **+1**：题面写的是「A 是 1，Z 是 26」，
//   而 `c - 'A'` 给的是 0~25（见 p1200Zero.cpp —— 少了那个 1，含 A 的名字整个变成 0）。
// ★ 一笔一眼的账：名字最长 6 个字母 ⇒ 积最大 26⁶ = 308 915 776 < 2³¹（余量 6.95 倍）
//   ⇒ **先乘完再取模也不会溢出**（见 p1200Big.cpp），这道题两种写法都对。
#include <bits/stdc++.h>
using namespace std;

static int val(const string& s) {
    int p = 1;
    for (char c : s) p = p * (c - 'A' + 1) % 47;        // ★ 边乘边取模：怎么长都不会溢出
    return p;
}

int main() {
    string a, b;
    if (!(cin >> a >> b)) return 0;
    printf("%s\n", val(a) == val(b) ? "GO" : "STAY");
    return 0;
}

// P1200 解析页上所有数字的出处。
//   ./p1200All        人话版
//   ./p1200All csv    给 check:viz 用
//
// ★★ 这道题的输入空间是「1~6 个大写字母」两个 ⇒ 单个名字只有
//   Σ 26^L = **321 272 406** 个（3.2 亿）—— 一个名字一个名字全跑一遍是几秒钟的事。
//   ⇒ [「输入空间小的时候，算一遍比对拍又快又充分」](/sol/p1002/)的又一次。
//
// 它算三件事：
//   ① **「边乘边取模」和「先乘完再取模」在题面范围内是不是永远一样** ——
//      3.2 亿个名字逐个比（答案：一个都不差，因为 26⁶ 只有 `int` 上限的 14.4%）；
//   ② ⚠ 那条线在哪：把名字放长到 7 个字母，**最小的会让 int 版出错的积**是多少；
//   ③ ★★ **随机两个名字答 GO 的概率** —— 这个数决定了顺手写的对拍在验什么：
//      它只有 2% 上下，也就是说 300 轮里正解有 290 多轮在说 STAY。
#include <bits/stdc++.h>
using namespace std;

static long long cnt[47];                 // 长度 1~6 的全部名字，积 mod 47 的分布
static long long names = 0, nomatch = 0, maxProd = 0;

/** DFS：p 是「边乘边取模」的值，raw 是「不取模」的真实积 */
static void dfs(int depth, int pmod, long long raw) {
    if (depth > 0) {
        names++;
        cnt[pmod]++;
        if (raw > maxProd) maxProd = raw;
        if ((int)(raw % 47) != pmod) nomatch++;        // 真实积 mod 47 ↔ 边乘边取模
    }
    if (depth == 6) return;
    for (int c = 1; c <= 26; c++) dfs(depth + 1, pmod * c % 47, raw * c);
}

int main(int argc, char** argv) {
    bool csv = argc > 1 && string(argv[1]) == "csv";

    dfs(0, 1, 1);

    /* ② 长度 7：枚举「七个因子的多重集」（C(32,7) = 3 365 856 个），
          找出最小的、会让 int 版算错的那个积。⚠ 线不在「长度 7」上，在「积越过 2³¹」上。 */
    long long INTMAX = 2147483647LL;
    long long minBad = LLONG_MAX;
    int badFactors[7] = {0};
    int f[7];
    function<void(int, int, long long)> pick = [&](int idx, int lo, long long prod) {
        if (idx == 7) {
            if (prod > INTMAX) {
                int asInt = (int)(unsigned)(unsigned long long)prod;   // 32 位截断
                if (asInt % 47 != (int)(prod % 47) && prod < minBad) {
                    minBad = prod;
                    for (int i = 0; i < 7; i++) badFactors[i] = f[i];
                }
            }
            return;
        }
        for (int c = lo; c <= 26; c++) {
            if (prod * c > 20000000000LL) break;        // 剪枝：比 26⁷ 还大就没必要往下走
            f[idx] = c;
            pick(idx + 1, c, prod * c);
        }
    };
    pick(0, 1, 1);

    /* ③ 两个随机名字同余的概率 = Σ (c_r / N)² */
    double collide = 0;
    for (int r = 0; r < 47; r++) { double p = (double)cnt[r] / (double)names; collide += p * p; }

    /* ④ 官方样例 */
    auto val = [](const string& s) { int p = 1; for (char c : s) p = p * (c - 'A' + 1) % 47; return p; };

    long long p7 = 1;
    for (int i = 0; i < 7; i++) p7 *= 26;

    if (csv) {
        printf("names,%lld\nmismatch,%lld\nmaxProd,%lld\n", names, nomatch, maxProd);
        printf("headroom,%.2f\n", (double)INTMAX / (double)maxProd);
        printf("pow7,%lld\nover7,%.2f\n", p7, (double)p7 / (double)INTMAX);
        printf("minBad,%lld\n", minBad);
        printf("minBadName,");
        for (int i = 0; i < 7; i++) putchar('A' + badFactors[i] - 1);
        putchar('\n');
        printf("collide,%.4f\n", collide * 100.0);
        printf("sample1,%d,%d\n", val("COMETQ"), val("HVNGAT"));
        printf("sample2,%d,%d\n", val("ABSTAR"), val("USACO"));
        return 0;
    }

    printf("① 长度 1~6 的名字一共 %lld 个；「边乘边取模」和「真实积 mod 47」对不上 %lld 个\n",
           names, nomatch);
    printf("   最大的积 = 26⁶ = %lld，只有 int 上限的 %.1f%%（余量 %.2f 倍）⇒ 先乘完再取模也安全\n",
           maxProd, 100.0 / ((double)INTMAX / (double)maxProd), (double)INTMAX / (double)maxProd);
    printf("② 放长到 7 个字母：26⁷ = %lld，是 int 上限的 %.2f 倍\n", p7, (double)p7 / (double)INTMAX);
    printf("   最小的、会让 int 版算错的积是 %lld（一个这样的名字：", minBad);
    for (int i = 0; i < 7; i++) putchar('A' + badFactors[i] - 1);
    printf("）\n");
    printf("③ 两个随机名字答 GO 的概率 = %.4f%%（1/47 = %.4f%%）\n", collide * 100.0, 100.0 / 47.0);
    printf("④ 官方样例：COMETQ %d ↔ HVNGAT %d（GO）；ABSTAR %d ↔ USACO %d（STAY）\n",
           val("COMETQ"), val("HVNGAT"), val("ABSTAR"), val("USACO"));
    return 0;
}

// P1200 ✗ 错法一：`c - 'A'` —— A 变成了 0
//
// ⚠ 题面写的是「A 是 1，Z 是 26」，而 `c - 'A'` 给的是 0~25。
// ★ 说清楚它算了什么：**只要名字里出现一个 A，整个积就被乘成 0**。
//   ⇒ 于是「两个名字都含 A」时它必答 GO（0 == 0），
//     「只有一个含 A」时它几乎必答 STAY。
// ⚠ 它不是「每一组都错」型 —— 不含 A 的名字它也只是把每个字母都算小 1，
//   积完全不同，可**取模之后照样可能撞上**。
#include <bits/stdc++.h>
using namespace std;

static int val(const string& s) {
    int p = 1;
    for (char c : s) p = p * (c - 'A') % 47;            // ⚠ 少了 + 1
    return p;
}

int main() {
    string a, b;
    if (!(cin >> a >> b)) return 0;
    printf("%s\n", val(a) == val(b) ? "GO" : "STAY");
    return 0;
}

// P1200 的生成器：./p1200Gen 种子 [档位]
//
// ★ 三个错法各靠什么现形：
//   · p1200Zero（`c - 'A'`，A 变成 0）→ 两套算法结论不同（名字里有没有 A 是关键）；
//   · p1200NoMod（忘了取模）          → **两个积模 47 同余，但它们本身不相等**；
//   · p1200Sum（把积读成和）          → 「和同余」和「积同余」这两件事结论不同。
//
// ⚠⚠ 而顺手写的那一档有个大问题：**随机两个名字答 GO 的概率只有 2.17%**
//   ⇒ 300 轮里正解有 290 多轮在说 STAY，两版**一起说 STAY** 算「通过」
//     ——[「一致有两种：都算对了，和都没算」](/sol/p1746/)。⇒ 必须专门造一档「保证 GO」。
//
// 档位：
//   0  ★ 顺手写的：两个随机名字，长度 1~6
//   1  ⚠ 保证 GO：先随机第一个，再摇第二个直到两者同余（期望 47 次）
//   2  ⚠ 两个名字都只有**一个字母**（★ 那时「和」就是「积」⇒ p1200Sum 在这一档必然是 0）
//   3  ★ 最终档：一半保证 GO、一半随机
//
// ⚠ rng() 一律先落到具名变量再传参（[第 24 章 P1776](/sol/p1776/) 那一跤）。
#include <bits/stdc++.h>
using namespace std;

static mt19937 rng;

static string pick(int lo, int hi) {
    unsigned r = rng() % (unsigned)(hi - lo + 1);
    int len = lo + (int)r;
    string s;
    for (int i = 0; i < len; i++) { unsigned c = rng() % 26u; s.push_back((char)('A' + c)); }
    return s;
}
static int val(const string& s) {
    int p = 1;
    for (char c : s) p = p * (c - 'A' + 1) % 47;
    return p;
}

int main(int argc, char** argv) {
    unsigned seed = argc > 1 ? (unsigned)atoi(argv[1]) : 1;
    int mode = argc > 2 ? atoi(argv[2]) : 0;
    rng.seed(seed * 1000003u + 20260907u);

    int lo = 1, hi = 6;
    if (mode == 2) { lo = 1; hi = 1; }

    bool wantGo = (mode == 1);
    if (mode == 3) { unsigned f = rng() % 2u; wantGo = (f == 0); }

    string a = pick(lo, hi), b = pick(lo, hi);
    if (wantGo) {
        for (int guard = 0; guard < 100000 && val(a) != val(b); guard++) b = pick(lo, hi);
    }
    printf("%s\n%s\n", a.c_str(), b.c_str());
    return 0;
}