洛谷 P1055 [NOIP 2008 普及组] ISBN 号码

// P1055 ISBN 号码 —— 正解：跳过分隔符，加权求和，mod 11
//
// ★ 题面把格式钉死了（`x-xxx-xxxxx-x`，而且「保证输入符合格式要求」）
//   ⇒ 九位数字的下标是固定的：0 / 2 3 4 / 6 7 8 9 10，识别码在 12 号位。
//   ⚠ 所以**不用做格式校验**，但**必须跳过那三个 `-`**（见 p1055Idx.cpp：拿下标当权重的那一版）。
//
// ⚠ 这道题只有一处不对称，而它就是全部的坑：**余数 10 要写成大写字母 `X`**。
//   ⇒ 于是「识别码」不是一个数字，是一个**字符**（见 p1055X.cpp）。
// ★ 一笔一眼的账：加权和最大 9 × (1+2+…+9) = 405 ⇒ `int` 余量大到不用想。
#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    if (!(cin >> s)) return 0;
    int sum = 0, w = 1;
    for (int i = 0; i < 12; i++)
        if (s[i] != '-') sum += (s[i] - '0') * w++;     // ★ 跳过分隔符，权重才是 1..9
    int r = sum % 11;
    char want = (r == 10) ? 'X' : (char)('0' + r);      // ⚠ 这道题唯一的不对称
    if (s[12] == want) printf("Right\n");
    else { s[12] = want; printf("%s\n", s.c_str()); }   // ⚠ 要打整串，带分隔符
    return 0;
}

// P1055 ✗ 错法一：把识别码当成一个数字 —— 忘了余数 10 写作 `X`
//
// ⚠ 两处一起错，而且是同一个原因：
//   ① 比较时写 `s[12] - '0'` —— 而 `'X' - '0'` 是 **40**，永远不等于任何余数；
//   ② 输出时写 `'0' + r` —— `r = 10` 时打出来的是 `:`（ASCII 58），一个不该存在的字符。
// ★ 触发条件是一句话：**正确的识别码正好是 `X`（也就是加权和 mod 11 == 10）**。
//   ⇒ 而随机一个 ISBN 落到这一档的比例是 **9.09%**（p1055Count.cpp 里那张表是精确算出来的）
//   ⚠ 官方两组样例的余数都是 4 ⇒ **两组都碰不到它**。
#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    if (!(cin >> s)) return 0;
    int sum = 0, w = 1;
    for (int i = 0; i < 12; i++) if (s[i] != '-') sum += (s[i] - '0') * w++;
    int r = sum % 11;
    if (s[12] - '0' == r) printf("Right\n");            // ⚠ 'X' - '0' = 40
    else { s[12] = (char)('0' + r); printf("%s\n", s.c_str()); }   // ⚠ r = 10 时打出 ':'
    return 0;
}

// P1055 解析页上所有数字的出处。
//   ./p1055Count        人话版
//   ./p1055Count csv    给 check:viz 用
//
// ★★ 这道题只有一处不对称（余数 10 写作 `X`），而这一处正是最容易漏的。
//   ⇒ 于是最该问的一句是：**随机一个 ISBN，识别码是 `X` 的概率有多大？**
//     它决定了「忘了 X」那个错法在对拍里多久现形一次。
//
// ⚠ 这个数**不用跑对拍去估，能精确算**：九位数字的加权和 mod 11 的分布，一遍 DP 就出来了
//   （10⁹ 个九位串，逐个试太慢；而 DP 是精确的）。
// ★ 而 DP 本身**配了自检**：位数 n ≤ 6 时拿真正的暴力枚举（最多 10⁶ 个）逐档核对
//   ⇒ [第 19 章 P2240](/sol/p2240/) 那条规矩：报一个算出来的数之前，先证明算它的代码是活的。
#include <bits/stdc++.h>
using namespace std;

/** 前 n 位（权重 1..n）的加权和 mod 11 的分布 —— DP */
static array<long long, 11> dist(int n) {
    array<long long, 11> f{};
    f[0] = 1;
    for (int i = 1; i <= n; i++) {
        array<long long, 11> g{};
        for (int r = 0; r < 11; r++) {
            if (!f[r]) continue;
            for (int d = 0; d <= 9; d++) g[(r + d * i) % 11] += f[r];
        }
        f = g;
    }
    return f;
}

/** 同一件事的暴力版（只对小 n 用，给 DP 做自检） */
static array<long long, 11> brute(int n) {
    array<long long, 11> f{};
    long long total = 1;
    for (int i = 0; i < n; i++) total *= 10;
    for (long long x = 0; x < total; x++) {
        long long v = x;
        int sum = 0;
        for (int i = n; i >= 1; i--) { sum += (int)(v % 10) * i; v /= 10; }
        f[sum % 11]++;
    }
    return f;
}

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

    /* ① 自检：n = 1..6 上 DP 和暴力逐档比 */
    int mismatch = 0;
    for (int n = 1; n <= 6; n++) if (dist(n) != brute(n)) mismatch++;

    /* ② 九位的真实分布 */
    auto f9 = dist(9);
    long long total = 0;
    for (int r = 0; r < 11; r++) total += f9[r];
    double pctX = 100.0 * (double)f9[10] / (double)total;

    /* ③ 官方两组样例的余数 */
    auto rOf = [](const string& s) {
        int sum = 0, w = 1;
        for (int i = 0; i < 12; i++) if (s[i] != '-') sum += (s[i] - '0') * w++;
        return sum % 11;
    };
    int r1 = rOf("0-670-82162-4"), r2 = rOf("0-670-82162-0");

    /* ④ 加权和的上界 */
    int maxSum = 0;
    for (int i = 1; i <= 9; i++) maxSum += 9 * i;

    if (csv) {
        printf("mismatch,%d\n", mismatch);
        printf("total,%lld\ncountX,%lld\npctX,%.4f\n", total, f9[10], pctX);
        printf("minR,%lld\nmaxR,%lld\n",
               *min_element(f9.begin(), f9.end()), *max_element(f9.begin(), f9.end()));
        printf("sample1,%d\nsample2,%d\n", r1, r2);
        printf("maxSum,%d\n", maxSum);
        return 0;
    }

    printf("① 自检：n = 1..6 上 DP 和暴力枚举对不上的档数 = %d\n", mismatch);
    printf("② 九位数字一共 %lld 个，加权和 mod 11 == 10（识别码是 X）的有 %lld 个 = %.4f%%\n",
           total, f9[10], pctX);
    printf("   （11 个余数里最少的 %lld 个、最多的 %lld 个 —— 分布几乎是平的，但不完全平）\n",
           *min_element(f9.begin(), f9.end()), *max_element(f9.begin(), f9.end()));
    printf("③ 官方两组样例的余数都是 %d / %d ⇒ 两组都碰不到 X 那一档\n", r1, r2);
    printf("④ 加权和最大 %d ⇒ int 余量 %.0f 倍，这道题不用想类型\n",
           maxSum, 2147483647.0 / maxSum);
    return 0;
}

// P1055 的生成器：./p1055Gen 种子 [档位]
//
// ★ 三个错法各靠什么现形：
//   · p1055X（忘了余数 10 写作 X）→ **正确的识别码正好是 X**（加权和 mod 11 == 10）；
//   · p1055Idx（拿下标当权重）    → **两套权重算出的余数不同**；
//   · p1055Out（只打一位识别码）  → **答案不是 Right**。
//
// 档位：
//   0  ★ 顺手写的：九位随机数字 + 识别码也随机取 0~9（⚠ 它从不产生「输入里就是 X」这种串）
//   1  ⚠ 一半的轮次保证识别码是对的 ⇒ 「Right」和「要改」各占一半
//   2  ⚠ 专门档：**保证正确的识别码是 X**（p1055X 的专门档）
//   3  ★ 最终档：九位随机、识别码一半对一半随机（含 X）
//
// ⚠ rng() 一律先落到具名变量再传参（[第 24 章 P1776](/sol/p1776/) 那一跤）。
#include <bits/stdc++.h>
using namespace std;

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

    int d[9];
    for (;;) {
        for (int i = 0; i < 9; i++) { unsigned r = rng() % 10u; d[i] = (int)r; }
        int sum = 0;
        for (int i = 0; i < 9; i++) sum += d[i] * (i + 1);
        if (mode == 2 && sum % 11 != 10) continue;      // ⚠ 专门档：只要余数正好是 10 的
        break;
    }
    int sum = 0;
    for (int i = 0; i < 9; i++) sum += d[i] * (i + 1);
    int r = sum % 11;
    char right = (r == 10) ? 'X' : (char)('0' + r);

    char last;
    if (mode == 2) last = right;                        // 专门档：识别码就写对的那个（含 X）
    else if (mode == 1) { unsigned f = rng() % 2u; if (f) last = right; else { unsigned g = rng() % 10u; last = (char)('0' + g); } }
    else if (mode == 3) { unsigned f = rng() % 2u; if (f) last = right; else { unsigned g = rng() % 11u; last = (g == 10) ? 'X' : (char)('0' + g); } }
    else { unsigned g = rng() % 10u; last = (char)('0' + g); }   // ★ 顺手写的：只会产生数字

    printf("%d-%d%d%d-%d%d%d%d%d-%c\n", d[0], d[1], d[2], d[3], d[4], d[5], d[6], d[7], d[8], last);
    return 0;
}