Star 的档案库

Appearance

2026夏个人训练赛第二十场 ​

A. 降雨 ​

  • 前缀和

∑ai 是总降水量，然后相邻两个的降水量和是 2ai，因为保证了山的数量为奇数，每次排除掉要算的那个，用总量减去其他的的和（用每间隔一个 a_i 求和算）

cpp
#include <iostream>

using namespace std;

typedef long long LL;
const int N = 300010;
LL a[N], s[N][2];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n;
    LL tot = 0;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        tot += a[i];
    }
    s[1][1] = a[1];
    for (int i = 2; i <= n; ++i) {
        s[i][i & 1] = a[i] + s[i - 2][i & 1];
        s[i][!(i & 1)] = s[i - 1][!(i & 1)];
    }
    for (int i = 1; i <= n; ++i) {
        LL res = tot;
        if (i >= 2) res -= s[i - 2][(i - 2) & 1] << 1;
        if (i + 1 <= n) res -= s[n][(i + 1) & 1] - s[i][(i + 1) & 1] << 1;
        cout << res << ' ';
    }
    cout << '\n';
    return 0;
}

B. 穿送门 ​

  • 预处理

倍增。

cpp
#include <iostream>

using namespace std;

typedef long long LL;
const int N = 200010;
int ne[N][70];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n;
    LL k;
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) cin >> ne[i][0];
    for (int i = 1; i <= 60; ++i) {
        for (int j = 1; j <= n; ++j) {
            ne[j][i] = ne[ne[j][i - 1]][i - 1];
        }
    }
    int x = 1;
    for (int i = 60; i >= 0; --i) {
        if (k >= (1LL << i)) {
            k -= (1LL << i);
            x = ne[x][i];
        }
    }
    cout << x << '\n';
    return 0;
}

C. 循环节 ​

  • 暴力

直接暴力算。

cpp
#include <iostream>
#include <map>

using namespace std;

typedef long long LL;
const int N = 10010;
map<int, int> mp;
int res[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    LL a, b, n;
    cin >> a >> b >> n;
    a %= b;
    for (int i = 1; i <= n; ++i) {
        if (a == 0) {
            cout << "-1\n";
            return 0;
        }
        if (mp[a]) {
            for (int j = mp[a]; j < i; ++j) cout << res[j];
            cout << '\n';
            return 0;
        }
        res[i] = a / b;
        mp[a] = i;
        a = (a % b) * 10;
    }
    cout << "0\n";
    return 0;
}

D. 老鼠 ​

  • 动态规划
  • 线段树
  • 排序

只能从低往高走，有严格的拓扑序，可以 dp，维护 fi,j 表示从 i, j 位置开始吃的最大食物数量。先按照食物数量降序排序反着算，然后每行每列各开一个线段树维护每个位置的最大数量。状态转移直接查线段树相应行和列 ±k 的区间最大即可，答案是 f1,1

cpp
#include <iostream>
#include <algorithm>
#include <tuple>

using namespace std;

const int N = 1010;

struct SegmentTree {
    int val[N * 4];

    void modify(int u, int l, int r, int p, int v) {
        if (l == r) val[u] = max(val[u], v);
        else {
            int mid = l + r >> 1;
            if (p <= mid) modify(u << 1, l, mid, p, v);
            else modify(u << 1 | 1, mid + 1, r, p, v);
            val[u] = max(val[u << 1], val[u << 1 | 1]);
        }
    }

    int query(int u, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) return val[u];
        else {
            int mid = l + r >> 1, res = 0;
            if (ql <= mid) res = query(u << 1, l, mid, ql, qr);
            if (qr > mid) res = max(res, query(u << 1 | 1, mid + 1, r, ql, qr));
            return res;
        }
    }
} row[N], col[N];

tuple<int, int, int> a[N * N];
int f[N * N];
int m;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            auto &[x, y, z] = a[++m];
            cin >> x;
            y = i, z = j;
        }
    }
    sort(a + 1, a + m + 1, greater<tuple<int, int, int>>());
    for (int i = 1, j = 1; i <= m; ++i) {
        while (j <= m && get<0>(a[j]) > get<0>(a[i])) {
            auto &[_, x, y] = a[j];
            row[x].modify(1, 1, n, y, f[j]);
            col[y].modify(1, 1, n, x, f[j]);
            j++;
        }
        auto &[v, x, y] = a[i];
        f[i] = v + max(row[x].query(1, 1, n, max(1, y - k), min(n, y + k)), col[y].query(1, 1, n, max(1, x - k), min(n, x + k)));

        if (x == 1 && y == 1) {
            cout << f[i] << '\n';
            break;
        }

        // cout << '(' << x << ',' << y << ") " << v << ' ' << f[i] << endl;
        // cout << "row: " << row[x].query(1, 1, n, max(1, y - k), min(n, y + k)) << endl;
        // cout << "col: " << col[y].query(1, 1, n, max(1, x - k), min(n, x + k)) << endl;
        // cout << endl;
    }
    // cout << '\n';
    return 0;
}

E. 付款 ​

  • 动态规划

线性 DP 从高位到低位依次枚举，设当前位为 d，只有两种状态

  • 一种是正常付钱，代价直接 + d
  • 另一种是多付之后找钱，在开始多付的时候代价 + 1
    • 多付过程中（多付 → 多付）每位代价为 9 - d
    • 多付的结束（多付 → 正常）代价为 10 - d
cpp
#include <iostream>
 
using namespace std;
typedef long long LL;

const int N = 1000010;
int f[N][2];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    string s;
    cin >> s;
    int n = s.length();
    f[0][1] = 1;
    for (int i = 1; i <= n; ++i) {
        int d = s[i - 1] - 48;
        f[i][0] = min(f[i - 1][0] + d, min(f[i - 1][1], f[i - 1][0] + 1) + 10 - d);
        f[i][1] = min(f[i - 1][0] + 10 - d, f[i - 1][1] + 9 - d);
    }
    cout << f[n][0] << endl;
    return 0;
}

F. Select 2 ​

  • 哈希集合与映射
  • 数论
cpp
#include <iostream>
#include <unordered_map>
 
using namespace std;
typedef long long LL;
const int MOD = 1000000007;
 
LL power(LL n, LL p) {
    LL res = 1, base = n;
    while (p) {
        if (p & 1) res = res * base % MOD;
        base = base * base % MOD;
        p >>= 1;
    }
    return res;
}
 
unordered_map<LL, LL> mp;
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n;
    LL p;
    cin >> n >> p;
    LL res = 0, tmp = 0;
    for (int i = 1; i <= n; ++i) {
        LL t;
        cin >> t;
        t %= MOD;
        if (!t) tmp++;
        else res += mp[power(t, MOD - 2) * p % MOD], mp[t]++;
    }
    cout << res + tmp * (tmp - 1) / 2 + tmp * (n - tmp) << '\n';
    return 0;
}

G. Pole Arrangement ​

  • 状态压缩 DP
  • 组合数学

事后：原来这是让我正常的 DP 的吗

事情是这样的，我看到之后立刻想到了最大的会隔开两边，左右两边相对独立，然后考虑只做一边的 DP，然后枚举数量排列组合拼起来，然后写了一个时间复杂度高达 n22n 的 DP，然后给这个 DP 打表然后交上去莫名其妙的 RE 了，然后我又观察到一共只有不到 800 种情况，干脆都打表得了，于是就有了下面的代码。

cpp
#include <iostream>
#include <unordered_map>
 
using namespace std;
typedef long long LL;

const int N = 25;
// LL f[2][1 << N][N + 1];
// LL biao[N][N] = {
//     {1},
//     {0, 1},
//     {0, 1, 1},
//     {0, 2, 3, 1},
//     {0, 6, 11, 6, 1},
//     {0, 24, 50, 35, 10, 1},
//     {0, 120, 274, 225, 85, 15, 1},
//     {0, 720, 1764, 1624, 735, 175, 21, 1},
//     {0, 5040, 13068, 13132, 6769, 1960, 322, 28, 1},
//     {0, 40320, 109584, 118124, 67284, 22449, 4536, 546, 36, 1},
//     {0, 362880, 1026576, 1172700, 723680, 269325, 63273, 9450, 870, 45, 1},
//     {0, 3628800, 10628640, 12753576, 8409500, 3416930, 902055, 157773, 18150, 1320, 55, 1},
//     {0, 39916800, 120543840, 150917976, 105258076, 45995730, 13339535, 2637558, 357423, 32670, 1925, 66, 1},
//     {0, 479001600, 1486442880, 1931559552, 1414014888, 657206836, 206070150, 44990231, 6926634, 749463, 55770, 2717, 78, 1},
//     {0, 6227020800, 19802759040, 26596717056, 20313753096, 9957703756, 3336118786, 790943153, 135036473, 16669653, 1474473, 91091, 3731, 91, 1},
//     {0, 87178291200, 283465647360, 392156797824, 310989260400, 159721605680, 56663366760, 14409322928, 2681453775, 368411615, 37312275, 2749747, 143325, 5005, 105, 1},
//     {0, 1307674368000, 4339163001600, 6165817614720, 5056995703824, 2706813345600, 1009672107080, 272803210680, 54631129553, 8207628000, 928095740, 78558480, 4899622, 218400, 6580, 120, 1},
//     {0, 20922789888000, 70734282393600, 102992244837120, 87077748875904, 48366009233424, 18861567058880, 5374523477960, 1146901283528, 185953177553, 23057159840, 2185031420, 156952432, 8394022, 323680, 8500, 136, 1},
//     {0, 355687428096000, 1223405590579200, 1821602444624640, 1583313975727488, 909299905844112, 369012649234384, 110228466184200, 24871845297936, 4308105301929, 577924894833, 60202693980, 4853222764, 299650806, 13896582, 468180, 10812, 153, 1},
//     {0, 6402373705728000, 22376988058521600, 34012249593822720, 30321254007719424, 17950712280921504, 7551527592063024, 2353125040549984, 557921681547048, 102417740732658, 14710753408923, 1661573386473, 147560703732, 10246937272, 549789282, 22323822, 662796, 13566, 171, 1},
//     {0, 121645100408832000, 431565146817638400, 668609730341153280, 610116075740491776, 371384787345228000, 161429736530118960, 52260903362512720, 12953636989943896, 2503858755467550, 381922055502195, 46280647751910, 4465226757381, 342252511900, 20692933630, 973941900, 34916946, 920550, 16815, 190, 1},
// };
// LL p[N];

// void dabiao() {
//     int n = 20;
//     f[0][0][0] = 1;
//     for (int i = 1; i <= n; ++i) {
//         int cur = i & 1;
//         for (int k = 1; k <= n; ++k) {
//             for (int msk = 0; msk < (1 << n); ++msk) {
//                 for (int l = 0; l < i; ++l) {
//                     if (msk >> k - 1 & 1) {
//                         bool flg = false;
//                         for (int j = n; j; --j) {
//                             if (msk >> j - 1 & 1) {
//                                 if (j == k) flg = true;
//                                 break;
//                             }
//                         }
//                         if (flg) f[cur][msk][l + 1] += f[cur ^ 1][msk ^ 1 << k - 1][l];
//                         else f[cur][msk][l] += f[cur ^ 1][msk ^ 1 << k - 1][l];
//                     }
//                 }
//             }
//         }
//         cout << "{0";
//         for (int j = 1; j <= i; ++j) {
//             biao[i][j] = f[cur][(1 << i) - 1][j];
//             cout << ", " << biao[i][j];
//         }
//         cout << "},\n";
//     }
// }

// void init() {
//     p[0] = 1;
//     for (int i = 1; i <= 20; ++i) p[i] = p[i - 1] * i;
// }

// LL comb(int n, int m) {
//     return p[n] / p[m] / p[n - m];
// }

LL biao[N][N][N] = {{{1},},{{0,1},{1,0},},{{0,1,1},{1,2,0},{1,0,0},},{{0,2,3,1},{2,6,3,0},{3,3,0,0},{1,0,0,0},},{{0,6,11,6,1},{6,22,18,4,0},{11,18,6,0,0},{6,4,0,0,0},{1,0,0,0,0},},{{0,24,50,35,10,1},{24,100,105,40,5,0},{50,105,60,10,0,0},{35,40,10,0,0,0},{10,5,0,0,0,0},{1,0,0,0,0,0},},{{0,120,274,225,85,15,1},{120,548,675,340,75,6,0},{274,675,510,150,15,0,0},{225,340,150,20,0,0,0},{85,75,15,0,0,0,0},{15,6,0,0,0,0,0},{1,0,0,0,0,0,0},},{{0,720,1764,1624,735,175,21,1},{720,3528,4872,2940,875,126,7,0},{1764,4872,4410,1750,315,21,0,0},{1624,2940,1750,420,35,0,0,0},{735,875,315,35,0,0,0,0},{175,126,21,0,0,0,0,0},{21,7,0,0,0,0,0,0},{1,0,0,0,0,0,0,0},},{{0,5040,13068,13132,6769,1960,322,28,1},{5040,26136,39396,27076,9800,1932,196,8,0},{13068,39396,40614,19600,4830,588,28,0,0},{13132,27076,19600,6440,980,56,0,0,0},{6769,9800,4830,980,70,0,0,0,0},{1960,1932,588,56,0,0,0,0,0},{322,196,28,0,0,0,0,0,0},{28,8,0,0,0,0,0,0,0},{1,0,0,0,0,0,0,0,0},},{{0,40320,109584,118124,67284,22449,4536,546,36,1},{40320,219168,354372,269136,112245,27216,3822,288,9,0},{109584,354372,403704,224490,68040,11466,1008,36,0,0},{118124,269136,224490,90720,19110,2016,84,0,0,0},{67284,112245,68040,19110,2520,126,0,0,0,0},{22449,27216,11466,2016,126,0,0,0,0,0},{4536,3822,1008,84,0,0,0,0,0,0},{546,288,36,0,0,0,0,0,0,0},{36,9,0,0,0,0,0,0,0,0},{1,0,0,0,0,0,0,0,0,0},},{{0,362880,1026576,1172700,723680,269325,63273,9450,870,45,1},{362880,2053152,3518100,2894720,1346625,379638,66150,6960,405,10,0},{1026576,3518100,4342080,2693250,949095,198450,24360,1620,45,0,0},{1172700,2894720,2693250,1265460,330750,48720,3780,120,0,0,0},{723680,1346625,949095,330750,60900,5670,210,0,0,0,0},{269325,379638,198450,48720,5670,252,0,0,0,0,0},{63273,66150,24360,3780,210,0,0,0,0,0,0},{9450,6960,1620,120,0,0,0,0,0,0,0},{870,405,45,0,0,0,0,0,0,0,0},{45,10,0,0,0,0,0,0,0,0,0},{1,0,0,0,0,0,0,0,0,0,0},},{{0,3628800,10628640,12753576,8409500,3416930,902055,157773,18150,1320,55,1},{3628800,21257280,38260728,33638000,17084650,5412330,1104411,145200,11880,550,11,0},{10628640,38260728,50457000,34169300,13530825,3313233,508200,47520,2475,55,0,0},{12753576,33638000,34169300,18041100,5522055,1016400,110880,6600,165,0,0,0},{8409500,17084650,13530825,5522055,1270500,166320,11550,330,0,0,0,0},{3416930,5412330,3313233,1016400,166320,13860,462,0,0,0,0,0},{902055,1104411,508200,110880,11550,462,0,0,0,0,0,0},{157773,145200,47520,6600,330,0,0,0,0,0,0,0},{18150,11880,2475,165,0,0,0,0,0,0,0,0},{1320,550,55,0,0,0,0,0,0,0,0,0},{55,11,0,0,0,0,0,0,0,0,0,0},{1,0,0,0,0,0,0,0,0,0,0,0},},{{0,39916800,120543840,150917976,105258076,45995730,13339535,2637558,357423,32670,1925,66,1},{39916800,241087680,452753928,421032304,229978650,80037210,18462906,2859384,294030,19250,726,12,0},{120543840,452753928,631548456,459957300,200093025,55388718,10007844,1176120,86625,3630,66,0,0},{150917976,421032304,459957300,266790700,92314530,20015688,2744280,231000,10890,220,0,0,0},{105258076,229978650,200093025,92314530,25019610,4116420,404250,21780,495,0,0,0,0},{45995730,80037210,55388718,20015688,4116420,485100,30492,792,0,0,0,0,0},{13339535,18462906,10007844,2744280,404250,30492,924,0,0,0,0,0,0},{2637558,2859384,1176120,231000,21780,792,0,0,0,0,0,0,0},{357423,294030,86625,10890,495,0,0,0,0,0,0,0,0},{32670,19250,3630,220,0,0,0,0,0,0,0,0,0},{1925,726,66,0,0,0,0,0,0,0,0,0,0},{66,12,0,0,0,0,0,0,0,0,0,0,0},{1,0,0,0,0,0,0,0,0,0,0,0,0},},{{0,479001600,1486442880,1931559552,1414014888,657206836,206070150,44990231,6926634,749463,55770,2717,78,1},{479001600,2972885760,5794678656,5656059552,3286034180,1236420900,314931617,55413072,6745167,557700,29887,936,13,0},{1486442880,5794678656,8484089328,6572068360,3091052250,944794851,193945752,26980668,2509650,149435,5148,78,0,0},{1931559552,5656059552,6572068360,4121403000,1574658085,387891504,62954892,6692400,448305,17160,286,0,0,0},{1414014888,3286034180,3091052250,1574658085,484864380,94432338,11711700,896610,38610,715,0,0,0,0},{657206836,1236420900,944794851,387891504,94432338,14054040,1255254,61776,1287,0,0,0,0,0},{206070150,314931617,193945752,62954892,11711700,1255254,72072,1716,0,0,0,0,0,0},{44990231,55413072,26980668,6692400,896610,61776,1716,0,0,0,0,0,0,0},{6926634,6745167,2509650,448305,38610,1287,0,0,0,0,0,0,0,0},{749463,557700,149435,17160,715,0,0,0,0,0,0,0,0,0},{55770,29887,5148,286,0,0,0,0,0,0,0,0,0,0},{2717,936,78,0,0,0,0,0,0,0,0,0,0,0},{78,13,0,0,0,0,0,0,0,0,0,0,0,0},{1,0,0,0,0,0,0,0,0,0,0,0,0,0},},{{0,6227020800,19802759040,26596717056,20313753096,9957703756,3336118786,790943153,135036473,16669653,1474473,91091,3731,91,1},{6227020800,39605518080,79790151168,81255012384,49788518780,20016712716,5536602071,1080291784,150026877,14744730,1002001,44772,1183,14,0},{19802759040,79790151168,121882518576,99577037560,50041781790,16609806213,3781021244,600107508,66351285,5010005,246246,7098,91,0,0},{26596717056,81255012384,99577037560,66722375720,27683010355,7562042488,1400250852,176936760,15030015,820820,26026,364,0,0,0},{20313753096,49788518780,50041781790,27683010355,9452553110,2100376278,309639330,30060030,1846845,65065,1001,0,0,0,0},{9957703756,20016712716,16609806213,7562042488,2100376278,371567196,42084042,2954952,117117,2002,0,0,0,0,0},{3336118786,5536602071,3781021244,1400250852,309639330,42084042,3447444,156156,3003,0,0,0,0,0,0},{790943153,1080291784,600107508,176936760,30060030,2954952,156156,3432,0,0,0,0,0,0,0},{135036473,150026877,66351285,15030015,1846845,117117,3003,0,0,0,0,0,0,0,0},{16669653,14744730,5010005,820820,65065,2002,0,0,0,0,0,0,0,0,0},{1474473,1002001,246246,26026,1001,0,0,0,0,0,0,0,0,0,0},{91091,44772,7098,364,0,0,0,0,0,0,0,0,0,0,0},{3731,1183,91,0,0,0,0,0,0,0,0,0,0,0,0},{91,14,0,0,0,0,0,0,0,0,0,0,0,0,0},{1,0,0,0,0,0,0,0,0,0,0,0,0,0,0},},{{0,87178291200,283465647360,392156797824,310989260400,159721605680,56663366760,14409322928,2681453775,368411615,37312275,2749747,143325,5005,105,1},{87178291200,566931294720,1176470393472,1243957041600,798608028400,339980200560,100865260496,21451630200,3315704535,373122750,30247217,1719900,65065,1470,15,0},{283465647360,1176470393472,1865935562400,1597216056800,849950501400,302595781488,75080705700,13262818140,1679052375,151236085,9459450,390390,9555,105,0,0},{392156797824,1243957041600,1597216056800,1133267335200,504326302480,150161411400,30946575660,4477473000,453708255,31531500,1431430,38220,455,0,0,0},{310989260400,798608028400,849950501400,504326302480,187701764250,46419863490,7835577750,907416510,70945875,3578575,105105,1365,0,0,0,0},{159721605680,339980200560,302595781488,150161411400,46419863490,9402693300,1270383114,113513400,6441435,210210,3003,0,0,0,0,0},{56663366760,100865260496,75080705700,30946575660,7835577750,1270383114,132432300,8588580,315315,5005,0,0,0,0,0,0},{14409322928,21451630200,13262818140,4477473000,907416510,113513400,8588580,360360,6435,0,0,0,0,0,0,0},{2681453775,3315704535,1679052375,453708255,70945875,6441435,315315,6435,0,0,0,0,0,0,0,0},{368411615,373122750,151236085,31531500,3578575,210210,5005,0,0,0,0,0,0,0,0,0},{37312275,30247217,9459450,1431430,105105,3003,0,0,0,0,0,0,0,0,0,0},{2749747,1719900,390390,38220,1365,0,0,0,0,0,0,0,0,0,0,0},{143325,65065,9555,455,0,0,0,0,0,0,0,0,0,0,0,0},{5005,1470,105,0,0,0,0,0,0,0,0,0,0,0,0,0},{105,15,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},},{{0,1307674368000,4339163001600,6165817614720,5056995703824,2706813345600,1009672107080,272803210680,54631129553,8207628000,928095740,78558480,4899622,218400,6580,120,1},{1307674368000,8678326003200,18497452844160,20227982815296,13534066728000,6058032642480,1909622474760,437049036424,73868652000,9280957400,864143280,58795464,2839200,92120,1800,16,0},{4339163001600,18497452844160,30341974222944,27068133456000,15145081606200,5728867424280,1529671627484,295474608000,41764308300,4320716400,323375052,17035200,598780,12600,120,0,0},{6165817614720,20227982815296,27068133456000,20193442141600,9548112373800,3059343254968,689440752000,111371488800,12962149200,1077916840,62462400,2395120,54600,560,0,0,0},{5056995703824,13534066728000,15145081606200,9548112373800,3824179068710,1034161128000,194900105400,25924298400,2425312890,156156000,6586580,163800,1820,0,0,0,0},{2706813345600,6058032642480,5728867424280,3059343254968,1034161128000,233880126480,36294017760,3880500624,281080800,13173160,360360,4368,0,0,0,0,0},{1009672107080,1909622474760,1529671627484,689440752000,194900105400,36294017760,4527250728,374774400,19759740,600600,8008,0,0,0,0,0,0},{272803210680,437049036424,295474608000,111371488800,25924298400,3880500624,374774400,22582560,772200,11440,0,0,0,0,0,0,0},{54631129553,73868652000,41764308300,12962149200,2425312890,281080800,19759740,772200,12870,0,0,0,0,0,0,0,0},{8207628000,9280957400,4320716400,1077916840,156156000,13173160,600600,11440,0,0,0,0,0,0,0,0,0},{928095740,864143280,323375052,62462400,6586580,360360,8008,0,0,0,0,0,0,0,0,0,0},{78558480,58795464,17035200,2395120,163800,4368,0,0,0,0,0,0,0,0,0,0,0},{4899622,2839200,598780,54600,1820,0,0,0,0,0,0,0,0,0,0,0,0},{218400,92120,12600,560,0,0,0,0,0,0,0,0,0,0,0,0,0},{6580,1800,120,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{120,16,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},},{{0,20922789888000,70734282393600,102992244837120,87077748875904,48366009233424,18861567058880,5374523477960,1146901283528,185953177553,23057159840,2185031420,156952432,8394022,323680,8500,136,1},{20922789888000,141468564787200,308976734511360,348310995503616,241830046167120,113169402353280,37621664345720,9175210268224,1673578597977,230571598400,24035345620,1883429184,109122286,4531520,127500,2176,17,0},{70734282393600,308976734511360,522466493255424,483660092334240,282923505883200,112864993037160,32113235938784,6694314391908,1037572192800,120176728100,10358860512,654733716,29454880,892500,16320,136,0,0},{102992244837120,348310995503616,483660092334240,377231341177600,188108321728600,64226471877568,15620066914452,2766859180800,360530184300,34529535040,2400690292,117819520,3867500,76160,680,0,0,0},{87077748875904,241830046167120,282923505883200,188108321728600,80283089846960,23430100371678,4842003566400,721060368600,77691453840,6001725730,324003680,11602500,247520,2380,0,0,0,0},{48366009233424,113169402353280,112864993037160,64226471877568,23430100371678,5810404279680,1009484516040,124306326144,10803106314,648007360,25525500,594048,6188,0,0,0,0,0},{18861567058880,37621664345720,32113235938784,15620066914452,4842003566400,1009484516040,145024047168,14404141752,972011040,42542500,1089088,12376,0,0,0,0,0,0},{5374523477960,9175210268224,6694314391908,2766859180800,721060368600,124306326144,14404141752,1110869760,54697500,1555840,19448,0,0,0,0,0,0,0},{1146901283528,1673578597977,1037572192800,360530184300,77691453840,10803106314,972011040,54697500,1750320,24310,0,0,0,0,0,0,0,0},{185953177553,230571598400,120176728100,34529535040,6001725730,648007360,42542500,1555840,24310,0,0,0,0,0,0,0,0,0},{23057159840,24035345620,10358860512,2400690292,324003680,25525500,1089088,19448,0,0,0,0,0,0,0,0,0,0},{2185031420,1883429184,654733716,117819520,11602500,594048,12376,0,0,0,0,0,0,0,0,0,0,0},{156952432,109122286,29454880,3867500,247520,6188,0,0,0,0,0,0,0,0,0,0,0,0},{8394022,4531520,892500,76160,2380,0,0,0,0,0,0,0,0,0,0,0,0,0},{323680,127500,16320,680,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{8500,2176,136,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{136,17,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},},{{0,355687428096000,1223405590579200,1821602444624640,1583313975727488,909299905844112,369012649234384,110228466184200,24871845297936,4308105301929,577924894833,60202693980,4853222764,299650806,13896582,468180,10812,153,1},{355687428096000,2446811181158400,5464807333873920,6333255902909952,4546499529220560,2214075895406304,771599263289400,198974762383488,38772947717361,5779248948330,662229633780,58238673168,3895460478,194552148,7022700,172992,2601,18,0},{1223405590579200,5464807333873920,9499883854364928,9092999058441120,5535189738515760,2314797789868200,696411668342208,155091790869444,26006620267485,3311148168900,320312702424,23372762868,1264588962,49158900,1297440,20808,153,0,0},{1821602444624640,6333255902909952,9092999058441120,7380252984687680,3857996316447000,1392823336684416,361880845362036,69350987379960,9933444506700,1067709008080,85700130516,5058355848,213021900,6054720,104040,816,0,0,0},{1583313975727488,4546499529220560,5535189738515760,3857996316447000,1741029170855520,542821268043054,121364227914930,19866889013400,2402345268180,214250326290,13910478582,639065700,19677840,364140,3060,0,0,0,0},{909299905844112,2214075895406304,2314797789868200,1392823336684416,542821268043054,145637073497916,27813644618760,3843752429088,385650587322,27820957164,1405944540,47226816,946764,8568,0,0,0,0,0},{369012649234384,771599263289400,696411668342208,361880845362036,121364227914930,27813644618760,4484377833936,514200783096,41731435746,2343240900,86582496,1893528,18564,0,0,0,0,0,0},{110228466184200,198974762383488,155091790869444,69350987379960,19866889013400,3843752429088,514200783096,47693069424,3012738300,123689280,2975544,31824,0,0,0,0,0,0,0},{24871845297936,38772947717361,26006620267485,9933444506700,2402345268180,385650587322,41731435746,3012738300,139150440,3719430,43758,0,0,0,0,0,0,0,0},{4308105301929,5779248948330,3311148168900,1067709008080,214250326290,27820957164,2343240900,123689280,3719430,48620,0,0,0,0,0,0,0,0,0},{577924894833,662229633780,320312702424,85700130516,13910478582,1405944540,86582496,2975544,43758,0,0,0,0,0,0,0,0,0,0},{60202693980,58238673168,23372762868,5058355848,639065700,47226816,1893528,31824,0,0,0,0,0,0,0,0,0,0,0},{4853222764,3895460478,1264588962,213021900,19677840,946764,18564,0,0,0,0,0,0,0,0,0,0,0,0},{299650806,194552148,49158900,6054720,364140,8568,0,0,0,0,0,0,0,0,0,0,0,0,0},{13896582,7022700,1297440,104040,3060,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{468180,172992,20808,816,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{10812,2601,153,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{153,18,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},},{{0,6402373705728000,22376988058521600,34012249593822720,30321254007719424,17950712280921504,7551527592063024,2353125040549984,557921681547048,102417740732658,14710753408923,1661573386473,147560703732,10246937272,549789282,22323822,662796,13566,171,1},{6402373705728000,44753976117043200,102036748781468160,121285016030877696,89753561404607520,45309165552378144,16471875283849888,4463373452376384,921759666593922,147107534089230,18277307251203,1770728444784,133210184536,7697049948,334857330,10604736,230622,3078,19,0},{22376988058521600,102036748781468160,181927524046316544,179507122809215040,113272913880945360,49415625851549664,15621807083317344,3687038666375688,661983903401535,91386536256015,9739006446312,799261107216,50030824662,2344001310,79535520,1844976,26163,171,0,0},{34012249593822720,121285016030877696,179507122809215040,151030551841260480,82359376419249440,31243614166634688,8603090221543272,1765290409070760,274159608768045,32463354821040,2930624059792,200123298648,10157339010,371165760,9224880,139536,969,0,0,0},{30321254007719424,89753561404607520,113272913880945360,82359376419249440,39054517708293360,12904635332314908,3089258215873830,548319217536090,73042548347340,7326560149480,550339071282,30472017030,1206288720,32287080,523260,3876,0,0,0,0},{17950712280921504,45309165552378144,49415625851549664,31243614166634688,12904635332314908,3707109859048596,767646904550526,116868077355744,13187808269064,1100678142564,67038437466,2895092928,83946408,1465128,11628,0,0,0,0,0},{7551527592063024,16471875283849888,15621807083317344,8603090221543272,3089258215873830,767646904550526,136346090248368,17583744358752,1651017213846,111730729110,5307670368,167892816,3174444,27132,0,0,0,0,0,0},{2353125040549984,4463373452376384,3687038666375688,1765290409070760,548319217536090,116868077355744,17583744358752,1886876815824,143653794570,7582386240,263831568,5441904,50388,0,0,0,0,0,0,0},{557921681547048,921759666593922,661983903401535,274159608768045,73042548347340,13187808269064,1651017213846,143653794570,8530184520,329789460,7482618,75582,0,0,0,0,0,0,0,0},{102417740732658,147107534089230,91386536256015,32463354821040,7326560149480,1100678142564,111730729110,7582386240,329789460,8314020,92378,0,0,0,0,0,0,0,0,0},{14710753408923,18277307251203,9739006446312,2930624059792,550339071282,67038437466,5307670368,263831568,7482618,92378,0,0,0,0,0,0,0,0,0,0},{1661573386473,1770728444784,799261107216,200123298648,30472017030,2895092928,167892816,5441904,75582,0,0,0,0,0,0,0,0,0,0,0},{147560703732,133210184536,50030824662,10157339010,1206288720,83946408,3174444,50388,0,0,0,0,0,0,0,0,0,0,0,0},{10246937272,7697049948,2344001310,371165760,32287080,1465128,27132,0,0,0,0,0,0,0,0,0,0,0,0,0},{549789282,334857330,79535520,9224880,523260,11628,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{22323822,10604736,1844976,139536,3876,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{662796,230622,26163,969,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{13566,3078,171,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{171,19,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},},};
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    // init();
    // int T;
    // cin >> T;
    // while (T--) {
    //     int n, l, r;
    //     cin >> n >> l >> r;
    //     l--, r--;
    //     __int128_t res = 0;
    //     for (int i = l; i <= n - r; ++i) {
    //         // cout << "qaq" << comb(n - 1, i) << ' ' << biao[i][l] << ' ' << biao[n - i - 1][r] << endl;
    //         res += (__int128_t)comb(n - 1, i) * biao[i][l] * biao[n - i - 1][r];
    //     }
    //     if (!res) cout << 0;
    //     else print(res);
    //     cout << '\n';
    // }
    // for (int n = 1; n <= 20; ++n) {
    //     cout << "{";
    //     for (int l = 0; l < n; ++l) {
    //         cout << "{";
    //         for (int r = 0; r < n; ++r) {
    //             LL res = 0;
    //             for (int i = l; i <= n - r; ++i) {
    //                 // cout << "qaq" << comb(n - 1, i) << ' ' << biao[i][l] << ' ' << biao[n - i - 1][r] << endl;
    //                 res += comb(n - 1, i) * biao[i][l] * biao[n - i - 1][r];
    //             }
    //             cout << res;
    //             if (r != n - 1) cout << ",";
    //         }
    //         cout << "},";
    //     }
    //     cout << "},";
    // }
    int T;
    cin >> T;
    while (T--) {
        int n, l, r;
        cin >> n >> l >> r;
        cout << biao[n - 1][l - 1][r - 1] << '\n';
    }
    return 0;
}

H. 【数论】C Looooops ​

  • 扩展欧几里得算法
  • 模逆元

线性同余方程 cx≡b−amod2k，直接用扩展欧几里得解一下即可。

cpp
#include <iostream>
 
using namespace std;
typedef long long LL;

LL ex_gcd(LL a, LL b, LL& x, LL& y) {
    if (!b) {
        x = 1;
        y = 0;
        return a;
    } else {
        int d = ex_gcd(b, a % b, y, x);
        y -= a / b * x;
        return d;
    }
}

LL solve(LL a, LL b, LL n) {
    LL x, y;
    LL d = ex_gcd(a, n, x, y);
    if (b % d) return -1;
    n /= d;
    return (x * (b / d) % n + n) % n;
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    LL a, b, c, k;
    while (cin >> a >> b >> c >> k, a || b || c || k) {
        LL n = 1LL << k;
        LL res = solve(c, (b - a + n) % n, n);
        if (res == -1) cout << "FOREVER\n";
        else cout << res << '\n';
    }
    return 0;
}

没人开的题

  • I. Typing practice
  • J. Longest Common Subsequence II
  • K. Prefix Sum
  • L. Juggernaut
  • M. Nocow Maze