Znzryb's Blog

P3390 【模板】矩阵快速幂

Posted on 2026-01-09 Edited on 2026-02-18

思路讲解

// 矩阵快速幂：必须是方阵
template <class T>
Matrix<T> mat_pow(Matrix<T> base, long long exp) {
    assert(base.n == base.m);
    Matrix<T> res = Matrix<T>::identity(base.n);
    while (exp > 0) {
        if (exp & 1) res = res * base;
        base = base * base;
        exp >>= 1;
    }
    return res;
}

AC代码

源代码

// by Gospel_rock  
// title: P3390 【模板】矩阵快速幂  
// GROUP_NAME: // ONLINE_JUDGE_NAME: Luogu  
  
#include <bits/stdc++.h>  
#define all(vec) vec.begin(),vec.end()  
#define PB push_back  
#define PF push_front  
#define EB emplace_back  
#define EF emplace_front  
#define EM emplace  
#define FI first  
#define SE second  
#define pct __builtin_popcountll  
#define ctz __builtin_ctzll  
#define SZ(a) ((long long) a.size())  
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)  
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)  
#define debug(var) cerr << #var <<":"<<var<<"\n";  
#define cend cerr<<"\n-----------\n"  
#define fsp(x) fixed<<setprecision(x)  
  
using namespace std;  
  
using  ll = long long;using ull = unsigned long long;  
using DB=double;using LD=long double;  
// using i128 = __int128;  
using CD=complex<double>;  
static constexpr ll MAXN=(ll)1e6+10,INF=(1ll<<61)-1;  
static constexpr ll mod=(ll)1e9+7; // 998244353;  
static constexpr double eps=1e-8;const double pi=acos(-1.0);  
  
ll lT;  
  
// T: 底层存储类型 (uint32_t / uint64_t)// MOD: 模数  
// Wide: 乘法时用的更宽类型  
template <class T, T MOD, class Wide = ull>  
struct modint {  
    T v;  
    modint(ll x = 0) {  
        ll t = x % (ll)MOD;  
        if (t < 0) t += MOD;  
        v = (T)t;  
    }  
  
    T val() const { return v; }  
  
    modint& operator+=(const modint &o) {  
        T x = v + o.v;  
        if (x >= MOD) x -= MOD;  
        v = x;  
        return *this;  
    }  
  
    modint& operator-=(const modint &o) {  
        T x = v >= o.v ? v - o.v : (T)(v + MOD - o.v);  
        v = x;  
        return *this;  
    }  
  
    modint& operator*=(const modint &o) {  
        Wide t = (Wide)v * (Wide)o.v;  
        v = (T)(t % MOD);  
        return *this;  
    }  
  
    // 幂  
    static modint powmod(modint a, ll e) {  
        modint r = 1;  
        while (e) {  
            if (e & 1) r *= a;  
            a *= a;  
            e >>= 1;  
        }  
        return r;  
    }  
  
    // 逆元（假定 MOD 是质数）  
    static modint inv(modint a) {  
        return powmod(a, (ll)MOD - 2);  
    }  
  
    modint& operator/=(const modint &o) {  
        return *this *= inv(o);  
    }  
  
    // 一元  
    modint operator+() const { return *this; }  
    modint operator-() const { return modint(0) - *this; }  
  
    // 二元  
    friend modint operator+(modint a, const modint &b) { return a += b; }  
    friend modint operator-(modint a, const modint &b) { return a -= b; }  
    friend modint operator*(modint a, const modint &b) { return a *= b; }  
    friend modint operator/(modint a, const modint &b) { return a /= b; }  
  
    friend bool operator==(const modint &a, const modint &b) { return a.v == b.v; }  
    friend bool operator!=(const modint &a, const modint &b) { return a.v != b.v; }  
  
    friend ostream& operator<<(ostream &os, const modint &x) {  
        return os << x.v;  
    }  
    friend istream& operator>>(istream &is, modint &x) {  
        ll t;  
        if (!(is >> t)) return is;  
        x = modint(t);  
        return is;  
    }  
};  
using modi=modint<uint32_t,mod>;  
  
// 2025/11/5 AC https://www.luogu.com.cn/record/245401024  
template <class T>  
struct Matrix {  
    int n, m;  
    vector<vector<T>> a;   // 1-based  
  
    Matrix(): n(0), m(0) {}  
  
    Matrix(int n_, int m_, const T &val = T()) {  
        assign(n_, m_, val);  
    }  
    // 新增：直接用 1-based 的 vv 构造  
    Matrix(const vector<vector<T>> &vv) {  
        load(vv);  
    }  
    // 你已经有一个 1-based 的 vv（vv.size() == n+1, vv[1].size() == m+1）  
    void load(const vector<vector<T>> &vv) {  
        n = (int)vv.size() - 1;  
        m = n ? (int)vv[1].size() - 1 : 0;  
        a = vv;    // 直接拷  
    }  
  
  
    void assign(int n_, int m_, const T &val = T()) {  
        n = n_;  
        m = m_;  
        a.assign(n + 1, vector<T>(m + 1, val));  
    }  
  
    vector<T>& operator[](int i) {  
        return a[i];          // A[i][j] -> (A.operator[](i))[j]  
    }  
    // 在const的时候调用  
    const vector<T>& operator[](int i) const {  
        return a[i];  
    }  
  
    Matrix operator+(const Matrix &rhs) const {  
        assert(n == rhs.n && m == rhs.m);  
        Matrix res(n, m);  
        for (int i = 1; i <= n; ++i)  
            for (int j = 1; j <= m; ++j)  
                res.a[i][j] = a[i][j] + rhs.a[i][j];  
        return res;  
    }  
  
    Matrix& operator+=(const Matrix &rhs) {  
        return *this = *this + rhs;  
    }  
  
    Matrix operator-(const Matrix &rhs) const {  
        assert(n == rhs.n && m == rhs.m);  
        Matrix res(n, m);  
        for (int i = 1; i <= n; ++i)  
            for (int j = 1; j <= m; ++j)  
                res.a[i][j] = a[i][j] - rhs.a[i][j];  
        return res;  
    }  
  
    Matrix& operator-=(const Matrix &rhs) {  
        return *this = *this - rhs;  
    }  
  
    Matrix operator*(const Matrix &rhs) const {  
        assert(m == rhs.n);  
        Matrix res(n, rhs.m, T());  
        for (int i = 1; i <= n; ++i) {  
            for (int k = 1; k <= m; ++k) {  
                if (a[i][k] == T()) continue;  
                for (int j = 1; j <= rhs.m; ++j) {  
                    res.a[i][j] = res.a[i][j] + a[i][k] * rhs.a[k][j];  
                }  
            }  
        }  
        return res;  
    }  
  
    Matrix& operator*=(const Matrix &rhs) {  
        return *this = *this * rhs;  
    }  
  
    static Matrix identity(int n) {  
        Matrix I(n, n, T());  
        FOR(i,1,n) I.a[i][i] = T(1);  
        return I;  
    }  
    friend  ostream& operator<<(ostream &os,const Matrix& ma) {  
        FOR(i,1,ma.n) {  
            FOR(j,1,ma.m) {  
                os<<ma[i][j]<<" ";  
            }  
            os<<"\n";  
        }  
        return os;  
    }  
};  
  
// 矩阵快速幂：必须是方阵  
template <class T>  
Matrix<T> mat_pow(Matrix<T> base, long long exp) {  
    assert(base.n == base.m);  
    Matrix<T> res = Matrix<T>::identity(base.n);  
    while (exp > 0) {  
        if (exp & 1) res = res * base;  
        base = base * base;  
        exp >>= 1;  
    }  
    return res;  
}  
  
void Solve(){  
    ll n,k;  
    cin>>n>>k;  
    vector<vector<modi> > A(n+1,vector<modi>(n+1));  
    FOR(i,1,n) {  
        FOR(j,1,n) {  
            cin>>A[i][j];  
        }  
    }  
    Matrix mat(A);  
    mat=mat_pow(mat,k);  
    cout<<mat;  
}  
  
signed main()  
{  
    ios::sync_with_stdio(false);  
    cin.tie(0);cout.tie(0);  
    // cin>>lT;  
    // while(lT--)        Solve();  
    return 0;  
}  
/*  
  
*/

心路历程（WA，TLE，MLE……）

CF-Edu-186-F1. Christmas Reindeer (easy version/hard version)

Posted on 2026-01-09 Edited on 2026-02-18

思路讲解

这是问题的简单版本。版本之间唯一的区别在于 $n$ 和 $m$ 的上限。在这个版本中， $n \le 500$ 且 $m \le 500$ 。

你有一群 $n$ 只圣诞驯鹿。第 $i$ 只驯鹿的力量是 $2^{c_i}$ 。

$k$ 只圣诞驯鹿组的运载能力计算如下：

驯鹿的力量按非递增顺序排序。我们把排序后的力量列表表示为 $c'_1, c'_2, \dots, c'_k$ ，其中 $c'_i\ge c'_{i+1}$ ；
然后，这群驯鹿的运载能力等于 $c'_1 + \lfloor\frac{c'_2} {2}\rfloor + \lfloor\frac{c'_3} {4}\rfloor + \dots + \lfloor\frac{c'_k} {2^{k - 1}}\rfloor$ 。

注意，一些驯鹿可能对群体的运载能力没有贡献。

你需要处理三种类型的查询：

添加一只力量为 $2^x$ 的驯鹿到群中；
从驯鹿群中移除一只力量为 $2^x$ 的驯鹿；
计算选择一些驯鹿（可能是所有）的方式数量，使得所选群体的运载能力至少为 $x$ 。

如果群中有多只力量相同的驯鹿，它们被视为不同的驯鹿。例如，如果你有两只力量各为 $1$ 的驯鹿，并且需要计算选择运载能力至少为 $1$ 的群体的方式数量，那么有 $3$ 种选择方式：选择第一只驯鹿，选择第二只驯鹿，或者选择它们两只。

思路讲解

这个全部都和 2 的次方有关系，我们不自觉的就会往二进制的方向想，但是问题在于，我们如何处理这个进位问题？

等等，有没有一种可能，我们不需要处理进位问题？ $c'_1 + \lfloor\frac{c'_2}{2}\rfloor + \lfloor\frac{c'_3}{4}\rfloor + \dots + \lfloor\frac{c'_k}{2^{k - 1}}\rfloor$ ，由于这个 C 是非严格递减的，即便在全部相等的前提下，因为右移作用越来越强烈，其为 1 的地方也在不断往后移动，因此，其实不会发生进位。

那么既然不会发生进位，第一个堵点就消失了。

接着我们就手玩一下样例，用组合计数的方式解决一下这个问题。

注意，在设计这个计数算法的过程当中，尽量让每层保持独立，即该层只考虑选了该层的数字的情况，这样子前面的数字因为选了他们的组合已经选过了，就不用考虑了，会轻松一点。

不过这道题目能不能做到这一点呢？就让我们看看解法吧。（是可以的，但需要一个关键观察，特别是对于前缀相等情况）

为了方便描述这个过程，令 $freq_i$ 为输入数组中 i 的频数， $pre_i$ 为 i 位置前（包括自己）最晚的 1 出现位置（描述的是查询数字 x）， $rem$ 这个数字指的是 i 之后所有的数字的频数之和。

答案 $ans\gets0$ ，等于（前缀相同）情况下的辅助统计量 $eqAns\gets1$ 。

其实，在做这道题目的时候，我也不止一次的想过，要是这道题目是 $>x$ 就好了。那所以说，我们为什么不这么做呢？ $eqAns$ 维护等于情况， $ans$ 维护严格大于情况，最后 $ans\gets ans+eqAns$ 不就行了？

从高到低遍历，遇到一位 $freq_i>0$ ，有这么几种情况。

Case 1： $i=pre_i$ $i = p r e_{i}$
- 如果 $freq_i=1$ ，不需要进行任何操作。
- 如果 $freq_i>1$ $f r e q_{i} > 1$ ，这个是最复杂的情况。面对这种情况，我还想过~~记忆化搜索，dp~~ 等等，以解决这个问题，不过最后发现，其实都不用，只需要一个关键观察：即需要选择多少个 i 达到这个等于状态是唯一确定的。你需要选择的数量，就是（自这位开始的）连续 1 的数量，令其为 $\text{conti1}$ $conti1$ 。
  - 首先，如果你选择的数量超过了（自这位开始的）连续 1 的数量，那么你就已经超过了，超过的时候至少要驻守 $\text{conti1}+1$ 个，才能保证超过，当然，除了 $i-\text{conti1}=0$ 的特殊情况，这种特殊情况因为相等，所以只能更新 $eqAns$ ***。***当然，写出这里的统计式子需要有这么一个想法，就是把 $rem$ 和这个前面这部分分开来看。

i-\text{conti1}=0:eqAns\gets eqAns\times(\sum^{freq_i}_{j=\text{conti}}C_{freq_i}^{j})\times2^{rem} \\ i-\text{conti1}>0:ans\gets ans+eqAns\times(\sum^{freq_i}_{j=\text{conti+1}}C_{freq_i}^{j})\times2^{rem} \\ eqAns\gets eqAns \times C^{conti1}_{freq_i}

  因为 $\text{conti1}$ 很小，这个式子中间的求和可以用从全组合减去东西的方式优化，达到 $O(W) $ 级别。
- 那么，你如果选的数量小于连续 1 的数量，那么你直接就没有资格相等（以第一个样例为例，$2\ 1\ 1$，只能凑出 $5={(101)}_{2}$，没法凑出 $6={(110)}_{2}$ 这样连续的 1，因为 2 的数量没有达到这个连续段 1 的数量要求）。因此如果 i 的频数小于连续的 1 的数量，直接 break 整个计数过程，并且使得  $eqAns\gets 0$。
- 当然，我们还需要进行**全局右移操作**，即：

auto right_move=[&](ll step) {   //  传入参数 step = conti1
    for (int j=1;j<i;++j) {
        freq[max(0ll,j-step)]+=freq[j];
        freq[j]=0;
    }
};

Case 2： $i>pre_i$
注意，思路要清楚， $ans$ 一定要保证这个答案 $>x$ ， $eqAns$ （统计的）一定要保证前缀严格相等。还是一样， $i=0$ 代表运载能力为 0，只能更新 $eqAns$ 。 $i>0$ 的时候更新 $ans$ 从 $j=1$ 开始是因为至少你要选一个才超过是吧。

i=0:eqAns\gets eqAns \times 2^{freq_i} \\ i>0:ans\leftarrow ans+eqAns\times(\sum^{freq_i}_{j=1}C_{freq_i}^{j})\times2^{rem}

如果说 $freq_i=0$ ，需要进行这个合法性检验，即如果 $i=pre_i$ ，直接 break 整个计数过程，并且使得 $eqAns\gets 0$ 。

⚠️ 注意：我们从高到低遍历，我们要遍历到 -1（就是代表这些驼鹿的运载能力归零了），因此，我们会给整个系统加一个偏移量，0 代表指数为 -1，1 代表为 0，以此类推。

⚠️ 注意：所有的 break 之前，都要使得 $eqAns\gets 0$ 。

AC代码

AC，解法可以通过 F2。

https://codeforces.com/contest/2182/submission/357349404

源代码

/**
 * Problem: F1. Christmas Reindeer (easy version)
 * Contest: Educational Codeforces Round 186 (Rated for Div. 2)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2182/problem/F1
 * Created: 2026-01-11 11:57:55
 * Author: Gospel_rock
 */

#include <bits/stdc++.h>
#include <ranges>

#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using LD = long double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll) 1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT;

/*
 *
 */
namespace Comb {
    // 组合数加逆元，依赖于这个MAXN（初始化）
    vector<ll> frac, infrac;
    int ln = 1;
    bool initialized = false;

    inline ll binpow(ll a, ll k) {
        ll res = 1;
        a %= mod;
        while (k > 0) {
            if (k & 1) res = (res * a) % mod;
            a = (a * a) % mod;
            k >>= 1;
        }
        return res;
    }

    void Comb(int n) {
        ln = n;
        frac.assign(n + 5, 1);
        infrac.assign(n + 5, 1);
        for (int i = 1; i <= ln; ++i) {
            frac[i] = (frac[i - 1] * i) % mod;
        }
        infrac[ln] = binpow(frac[ln], mod - 2);
        for (int i = ln - 1; i >= 0; --i) {
            infrac[i] = (infrac[i + 1] * (i + 1)) % mod;
        }
    }

    inline ll CC(ll k, ll n) {
        if (k < 0 || k > n) {
#ifdef LOCAL
            cerr << "CC 组合数传入参数不合法，可能是传入顺序错了\n";
#endif
            return 0; // Return 0 if k is out of range [0, n]
        }
        if (!initialized) {
            Comb(MAXN);
            initialized = true;
        }
        ll res = frac[n];
        res = (res * infrac[n - k]) % mod;
        res = (res * infrac[k]) % mod;
        return res;
    }

    inline ll PP(ll k, ll n) {
        if (k < 0 || k > n) {
#ifdef LOCAL
            cerr << "PP 排列数传入参数不合法，可能是传入顺序错了\n";
#endif
            return 0;
        }
        if (!initialized) {
            Comb(MAXN);
            initialized = true;
        }
        ll res = frac[n] * infrac[n - k];
        res %= mod;
        return res;
    }
}

using namespace Comb;

void Solve() {
    ll N, M;
    cin >> N >> M;
    vector<ll> C(N);
    vector<ll> freq(65);
    for (int i = 0; i < N; ++i) {
        cin >> C[i];
        freq[C[i] + 1]++;
    }
    vector<ll> pow_2(N + M +2);
    pow_2[0] = 1;
    for (int i = 1; i <= N+M; ++i) {
        pow_2[i] = pow_2[i - 1] << 1;
        pow_2[i] %= mod;
    }
    for (int _ = 1; _ <= M; ++_) {
        ll op, x;
        cin >> op >> x;
        if (op == 1) {
            freq[x + 1]++;
            continue;
        }
        if (op == 2) {
            freq[x + 1]--;
            continue;
        }
        x <<= 1;
        bitset<70> bix(x);
        vector<ll> pre_1(70, -2);
        for (int i = 0; i <= 65; ++i) {
            if (bix[i]) {
                pre_1[i] = i;
            } else {
                pre_1[i] = (i - 1 < 0 ? -2 : pre_1[i - 1]);
            }
        }
        /*******下面是核心计数部分***********/
        vector<ll> freq_back_up = freq;
        ll ans = 0, eqAns = 1;
        bool reachEq=false;
        for (int i = 63; i >= 0; --i) {
            if (freq[i] == 0) {
                if (i == pre_1[i]) {
                    eqAns=0;
                    break;
                }
                continue;
            }

            /**********辅助函数***********/
            auto cnt_rem = [&]() {
                ll rem = 0;
                for (int j = 0; j < i; ++j) {
                    rem += freq[j];
                }
                return rem;
            };

            auto cnt_conti1 = [&]() {
                ll res = 0;
                for (int j = i; j >= 0; --j) {
                    if (bix[j]) {
                        ++res;
                        pre_1[j] = -2;
                    } else {
                        break;
                    }
                }
                return res;
            };
            auto right_move = [&](ll step) {
                for (int j = 1; j < i; ++j) {
                    freq[max(0ll, j - step)] += freq[j];
                    freq[j] = 0;
                }
            };
            auto cal_comb_sum = [&](ll st) {
                ll res = pow_2[freq[i]];
                for (int j = 0; j < st; ++j) {
                    res -= CC(j, freq[i]);
                    res %= mod;
                }
                return res;
            };
            // auto is_spec=[&](ll rem) {
            //     if (i<=lowbit && reachEq && rem==0) {
            //         return true;
            //     }
            //     return false;
            // };
            /**********************/

            if (i > pre_1[i]) {
                ll rem = cnt_rem();
                ll lans = 0;
                if (i==0) {
                    eqAns*=cal_comb_sum(0);
                    eqAns%=mod;
                }else if (i>=1){
                    // 只要不是 0，都一定有贡献能力（完全不选的情况让后面的值考虑）
                    lans=cal_comb_sum(1);
                    lans*=pow_2[rem];
                    lans%=mod;
                    lans *= eqAns;
                    lans %= mod;
                    ans += lans;
                    ans %= mod;
                }
            } else if (i == pre_1[i]) {
                /******等于的情况，最复杂******/
                ll conti1 = cnt_conti1();
                if (conti1 > freq[i]) {
                    eqAns=0;
                    break;
                }
                right_move(conti1);
                ll rem = cnt_rem();
                if (conti1 == freq[i] && i-conti1>=1) {
                    continue;
                }
                ll lans = 0;
                ll upEq=eqAns;
                if (i-conti1<1) {
                    eqAns*=cal_comb_sum(conti1);
                    eqAns %= mod;
                } else {
                    lans = cal_comb_sum(conti1 + 1);
                    eqAns *= CC(conti1, freq[i]);
                    eqAns %= mod;
                }
                lans *= pow_2[rem];
                lans %= mod;
                lans *= upEq;
                lans %= mod;
                ans += lans;
                ans %= mod;
            }
        }
        ans+=eqAns;
        ans %= mod;
        if (ans < 0) ans += mod;
        cout << ans << "\n";
        swap(freq, freq_back_up);
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // cin >> lT;
    // while(lT--)
    Solve();
    return 0;
}

/*
AC
https://codeforces.com/contest/2182/submission/357349404

3 3
2 1 1
1 2
2 1
3 5

6 1
3 3 0 2 4 3
3 21

3 1
3 4 4
3 19


*/

心路历程（WA，TLE，MLE……）

一开始的算法得出来的答案不太对，因为计数条件和题目规定有不同，题目的 C 数组是排好序的，因此就不在乎顺序了，求的就是组合数。

如果 $freq_i>1$ ，还好办吗？我们先想一种，即 $ans\leftarrow ans+2^{rem}\times freq_i$ ，毕竟有 $freq_i$ 种选择嘛，这种自然是没什么问题。但是，选了一个 i 以后，其他的 i 我们直接放任不管吗？这是不行的，我们还需要进行右移操作，即 $freq_{i-1}\gets freq_{i-1}+freq_i-1$ （先右移，再统计这个 $rem$ 数量）。
如果 $freq_i>1$ ，这个是最复杂的情况，我们需要求出来新的 $eqAns$ 。 $eqAns\gets eqAns \times freq_i$ ，然后，我们要进行右移操作，我们进行的是全局右移操作，即对 $\forall\ i'< i$ ， $freq_{i'-1}\gets freq_{i'-1}+freq_{i'}$ ， $freq_{i-1}\gets freq_{i-1}+freq_i-1$ 。

Case 2： $i=pre_i$ $i = p r e_{i}$
- 如果 $freq_i=1$ ，不需要进行任何操作。
- 如果 $freq_i>1$ $f r e q_{i} > 1$ ，这个是最复杂的情况。我们发现，这里，如果我们选了第一个数，可以下放 $freq_{i}-1$ $f r e q_{i} - 1$ 个数字到 $freq_{i-1}$ $f r e q_{i - 1}$ ，但是选了第二个数字以后，只能下放 $freq_{i}-2$ $f r e q_{i} - 2$ 个数字到 $freq_{i-1}$ $f r e q_{i - 1}$ ，这种下放，好像不能用公式法做出来，难道每一个都要重新算吗？
  - 其实我们会有一个感觉，就是好像，这个是可以记忆化搜索，或者说是 dp 的。可以发现我们的这个状态由这几个因素决定：
  - 其实我们会发现这个 dp 和询问的 x 没什么关系，可以放在一起做？不过你说还有操作增删操作？呃，这个确实是一个问题，不过由于整个东西是离线的，我们可以得到每个位置的 $freq_i$ 的最大值，按照这个 dp，就不会出现问题了。
  - 不过还有一个问题，就是如何将查询做到 $O(1)$ 呢？其实这个的话前缀和即可。不过折腾来，

⚠️ 注意：注意有限右移操作和全局右移操作。

那么这个上面是我们脑内模拟了一下这个过程，得出来的计数结论，我们实现一下，看看对不对？

哈哈，我们会发现，这样子操作，得出来的答案不对，这是为什么呢？。

以这个第一个样例的第一个询问为例，我们会发现，其实这个答案并不在乎顺序。

那我们的计算要怎么样搞？其实，我们发现我们上面的思路还是比较混乱的，即有的时候认为是组合，有的时候又认为是排列。

不过，我们发现，题目中的 $c'_i\ge c'_{i+1}$ 是非常重要的，这意味着，只要是为了这个相等作用，无论

⚠️ 注意：我们从高到低遍历，我们要遍历到 -1（就是代表这些驼鹿的运载能力归零了），因此，我们会给整个系统加一个偏移量。

rem=0:ans\gets ans+eqAns\times((2^{rem+freq_{i}-\text{conti1}}+\cdots+2^{rem})+ \\ (2^{rem+freq_{i}-\text{conti1}-1}+\cdots+2^{rem})+\cdots+2^{rem}) \\ rem≠0:ans\gets ans+eqAns\times((2^{rem+freq_{i}-\text{conti1}-1}+\cdots+2^{rem})+ \\ (2^{rem+freq_{i}-\text{conti1}-2}+\cdots+2^{rem})+\cdots+2^{rem})

Case 1： $i>\text{MSB}$ $i > MSB$ （MSB 即查询数字 x 最大二进制位的位数）
- 如果 $freq_i=1$ ，那么好办，直接 $ans\leftarrow ans+2^{rem}$ 即可。
- 如果 $freq_i>1$ ，还好办吗？这里需要有这么一个想法，就是把 $rem$ 和这个前面这部分分开来看，即：

ans\leftarrow ans+2^{rem+freq_{i}-1}+2^{rem+freq_{i}-2}+ \cdots+ 2^{rem}

这个式子这样子理解，首先，这个数组 C 是倒序排序的，即 $c'_i\ge c'_{i+1}$，因此，选了排在第一个的数，就有 $2^{rem+freq_{i}-1}$ 种组合（全组合的这个公式），选了排在第二个的数，就只有 $2^{rem+freq_{i}-2}$ 种组合了（没法选第一个数），一次类推，就得到了这个式子。之后，我们就当 i 这个数字不存在就行了。

START206——Min Steps

Posted on 2025-10-03 Edited on 2026-02-18

思路讲解

你可以发现，这个式子可以写成这样：

$2^{c_1}+2^{c_2}$

AC代码

源代码

心路历程（WA，TLE，MLE……）

2025 CCPC 全国邀请赛（南昌）暨第二届江西省赛——D. 挑战图同构（分量哈希）

Posted on 2025-09-28 Edited on 2026-03-02

思路讲解

当然，我们首先看到这道题目，会想到暴力。

但是暴力显然不行，先不管这个东西要怎么求，存储上，你存都存不下来。

既然这个暴力是不行的，我们就想到，这个图上面的路径太多了，有什么东西两点之间只有一条路径呢？其实就是树。

那么这种比较复杂的题目，特别是比较复杂的图论题目，一般都要划分阶段。

因此我们就要想，这个，如何把这节点一点一点的加入这个图当中？

可以的，兄弟，是可以的。

我们假设我们现在有一张图，我们可以先把到这张图距离为 i 的点加入进来，再把 i+1 的点加入进来，… 。

我们可以使用 kruskal 进行实现，kruskal 的基本过程就是按从小到大排序，加入到图中，使用并查集判环。

划分阶段其实也很简单，就是两张图把距离为 i 的点加入进来，停住。干一些事情，再继续加入距离为 i+1 的点，… 。

我们把一个中间状态摘出来看，如果原来的图是一样的（同构的），加入进来的点的并查集划分是一样的，那么两张图就是同构的。

这么说有点抽象。比如说蓝色的点是原来的图，红色的点是新加进来的点，不难发现，这两张图是同构的。因为只要并查集划分相同，新点之间的这个 dis 就是 i，老点到新点之间的 dis 也都是 i。

然后我们就来到了最后一个问题，怎么样快速判断（ $O(1)$ ）两个图的并查集划分是相同的那？呃，其实不是那么难的。我们请出我们的老盆友，哈希。

一个联通块的签名可以理解为有什么点。有什么点的话，我们可以给每个点整一个随机值（mt19937_64），然后一个联通块有什么点，就相当于其所有拥有的点的随机值的异或起来。

把这个好几个联通块组合（异或）起来，就可以得到目前的这个并查集划分状态，然后直接比较这个哈希值即可。

AC代码

https://qoj.ac/submission/1415583

源代码

// by Gospel_rock
#include <algorithm>
#include <functional>
#include <random>
#include <vector>
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
#define all(vec) vec.begin(), vec.end()
#define PB push_back
#define PF push_front
#define EB emplace_back
#define EF emplace_front
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define lson(o) (o << 1)
#define rson(o) (o << 1 | 1)
#define SZ(a) ((long long)a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var << ":" << var << "\n";
#define cend cerr << "\n-----------\n"
#define fsp(x) fixed << setprecision(x)
#define minn(vec) *min_element(vec.begin(), vec.end())
#define maxx(vec) *max_element(vec.begin(), vec.end())

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using LD = long double;
// using i128 = __int128;
using pdd = pair<DB, DB>;
using plb = pair<ll, bool>;
using pll = pair<ll, ll>;
using vll = vector<ll>;
using vb = vector<bool>;
using tll = tuple<ll, ll, ll>;
using vii = vector<int>;
using vpll = vector<pll>;
using vtll = vector<tll>;
using vdb = vector<DB>;
using vc = vector<char>;
using arr3 = array<ll, 3>;
using arr2 = array<ll, 2>;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e5 + 10,
                    INF = (ll)1e17 + 3; // 1e17+3是素数 1e18+9是素数
static constexpr ll mod = (ll)1e9 + 7;  // 998244353;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
const ll PI = ll(pi * 2e18) + 71;
ll N, M1, Q, X, K, T, lT, M2;
struct Edge {
    ll u, v, w;
    // bool operator<(const Edge &other) const {
    //     return w>other.w;
    // }
};
mt19937_64 rng(time(0));
ll rnd[MAXN];
hash<ll> hasher;
const ll RAN = rng();
ll mix(ll a, ll b) {
    ll res = (a ^ (b * RAN)) * PI;
    return res;
}
struct DSU {
    vll fa;
    ll N;
    vll siz;
    ll S;
    vll Sum;
    void resize(ll n) {
        this->N = n;
        fa.resize(N + 5);
        siz.resize(N + 5);
        Sum.resize(N + 5);
        S = 0;
        FOR(i, 1, N) {
            fa[i] = i;
            siz[i] = 1;
            Sum[i] = rnd[i];
            S ^= mix(Sum[i], siz[i]);
        }
    }
    ll find(ll x) {
        if (x == fa[x])
            return x;
        return fa[x] = find(fa[x]);
    }
    void merge(ll a, ll b) {
        ll faa = find(a), fab = find(b);
        if (faa == fab) return;
        S ^= mix(Sum[faa], siz[faa]);
        S ^= mix(Sum[fab], siz[fab]);
        fa[faa] = fab;
        siz[fab] += siz[faa];
        Sum[fab] ^= Sum[faa];
        S ^= mix(Sum[fab], siz[fab]);
        return;
    }
};
struct Solve {
    vll fa;
    vector<Edge> edge1, edge2;
    vll li;
    vector<vector<Edge>> g1;
    vector<vector<Edge>> g2;
    ll get(ll x) {
        ll res = lower_bound(all(li), x) - li.begin();
        return res;
    }
    DSU a, b;
    Solve() {
        cin >> N >> M1 >> M2;
        fa.resize(N + 5);
        edge1.resize(M1);
        edge2.resize(M2);
        a.resize(N);
        b.resize(N);
        FOR(i, 1, N) { fa[i] = i; }
        FOR(i, 1, M1) {
            ll u, v, w;
            cin >> u >> v >> w;
            edge1[i - 1] = {u, v, w};
            li.PB(w);
        }
        FOR(i, 1, M2) {
            ll u, v, w;
            cin >> u >> v >> w;
            edge2[i - 1] = {u, v, w};
            li.PB(w);
        }
        // sort(all(edge1));
        // sort(all(edge2));
        sort(all(li));
        li.resize(unique(all(li)) - li.begin());
        g1.resize(SZ(li) + 5);
        g2.resize(SZ(li) + 5);
        FOR(i, 1, M1) { g1[get(edge1[i - 1].w)].PB(edge1[i - 1]); }
        FOR(i, 1, M2) { g2[get(edge2[i - 1].w)].PB(edge2[i - 1]); }
        FOR(i, 0, SZ(li) - 1) {
            for (auto [u, v, w] : g1[i]) {
                a.merge(u, v);
            }
            for (auto [u, v, w] : g2[i]) {
                b.merge(u, v);
            }
            if (a.S != b.S) {
                cout << "NO\n";
                return;
            }
        }
        cout << "YES\n";
    }
};

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> lT;
    FOR(i, 0, MAXN - 5) { rnd[i] = rng(); }
    while (lT--)
        Solve a;
    return 0;
}
/*
AC
https://qoj.ac/submission/1415583

*/

心路历程（WA，TLE，MLE……）

merge 的逻辑比较复杂，容易写错，之后可以使用，Old，New，这样的命名，避免混淆。

void merge(ll a, ll b) {
    ll faa = find(a), fab = find(b);
    if (faa == fab) return;
    S ^= mix(Sum[faa], siz[faa]);
    S ^= mix(Sum[fab], siz[fab]);
    fa[faa] = fab;
    siz[fab] += siz[faa];
    Sum[fab] ^= Sum[faa];
    S ^= mix(Sum[fab], siz[fab]);
    return;
}

2025 CCPC 全国邀请赛（南昌）暨第二届江西省赛———B. 精神胜利（位集bfs）

Posted on 2025-09-27 Edited on 2026-02-18

思路讲解

dij 不能用，因为边太多了。

因为边权只有0 和 1，可以使用位集 bfs。

AC代码

https://qoj.ac/submission/1411426

判断一下是否可以两次抵达，196ms

源代码

// by Gospel_rock
#include <vector>
#ifdef LOCAL
#define  _GLIBCXX_DEBUG
#endif 
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define PB push_back
#define PF push_front
#define EB emplace_back
#define EF emplace_front 
#define EM emplace
#define FI first 
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
#define minn(vec) *min_element(vec.begin(),vec.end())
#define maxx(vec) *max_element(vec.begin(),vec.end())
#define yyy cout<<"YES\n"
#define nnn cout<<"NO\n"

using namespace std;

using  ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double; 
// using i128 = __int128;
using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;using vll=vector<ll>;using vb=vector<bool>;
using tll = tuple<ll,ll,ll>;using vii=vector<int>;
using vpll = vector<pll>;using vtll = vector<tll>;
using vdb = vector<DB>;using vc=vector<char>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
using CD=complex<double>;
static constexpr ll MAXN=(ll)5e3+10,INF=(ll)1e17+3; // 1e17+3??? 1e18+9???
static constexpr ll mod=(ll)1e9+7; // 998244353;
static constexpr double eps=1e-8;const double pi=acos(-1.0);
ll N,M,Q,X,K,T,lT;

struct Solve{
    vector<bitset<MAXN>> A;          // ???OUT?
    vector<bitset<MAXN>> IN;         // ???IN????????????
    vector<vll> Dis;                 // Dis[u][v] = (???? - 1)???? -1
    bitset<MAXN> ised;               // ????? u ?? BFS ??

    Solve(){
        cin>>N>>Q;
        A.resize(N+5);
        IN.resize(N+5);
        Dis.resize(N+5, vll(N+5, -1));

        // ??????? i ?? j=i+1..N
        FOR(i,1,N){
            FOR(j,1,N-i){
                char a; cin>>a;
                int u=i, v=i+j;
                if(a=='0'){
                    // v -> u
                    A[v].set(u);
                    IN[u].set(v);
                }else{
                    // u -> v
                    A[u].set(v);
                    IN[v].set(u);
                }
            }
        }
        FOR(_,1,Q){
            reply();
        }
    }

    // ?? BFS???????? __ ????=__????? i ??Dis[u][i]=__-1
    void bfs(ll u){
        bitset<MAXN> vis, q; 
        vis.reset(); q.reset();
        q[u]=1; vis[u]=1;

        FOR(__,1,N){
            if(q.none()) break;

            // ???????????
            bitset<MAXN> sum; sum.reset();
            for(int i = q._Find_first(); i <= N; i = q._Find_next(i)){
                sum |= A[i];
            }
            // ????????
            bitset<MAXN> qq = (~vis) & sum;

            // ??????=__?????????? ??-1
            for(int i = qq._Find_first(); i <= N; i = qq._Find_next(i)){
                Dis[u][i] = __ - 1;
            }

            vis |= qq;
            q = qq;
        }
    }

    void reply(){ 
        ll u,v;
        cin>>u>>v;

        // k=0????
        if(A[u][v]){
            cout<<0<<"\n";
            return;
        }

        // k=1???????????? w: u->w && w->v?
        if ( (A[u] & IN[v]).any() ){
            cout<<1<<"\n";
            return;
        }

        // ????
        if(ised[u]){
            cout<<Dis[u][v]<<"\n";
            return;
        }

        // ???? u ???
        ised[u]=true;
        bfs(u);
        cout<<Dis[u][v]<<"\n";
    }
};

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    
    // cin>>lT;
    // while(lT--)
    Solve a;
    return 0;
}
/*

*/

不判断两次抵达，1309ms

https://qoj.ac/submission/1410868

源代码

// by Gospel_rock
#include <vector>
#ifdef LOCAL
#define  _GLIBCXX_DEBUG
#endif 
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define PB push_back
#define PF push_front
#define EB emplace_back
#define EF emplace_front 
#define EM emplace
#define FI first 
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
#define minn(vec) *min_element(vec.begin(),vec.end())
#define maxx(vec) *max_element(vec.begin(),vec.end())
#define yyy cout<<"YES\n"
#define nnn cout<<"NO\n"

using namespace std;

using  ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double; 
// using i128 = __int128;
using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;using vll=vector<ll>;using vb=vector<bool>;
using tll = tuple<ll,ll,ll>;using vii=vector<int>;
using vpll = vector<pll>;using vtll = vector<tll>;
using vdb = vector<DB>;using vc=vector<char>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
using CD=complex<double>;
static constexpr ll MAXN=(ll)5e3+10,INF=(ll)1e17+3; // 1e17+3??? 1e18+9???
static constexpr ll mod=(ll)1e9+7; // 998244353;
static constexpr double eps=1e-8;const double pi=acos(-1.0);
ll N,M,Q,X,K,T,lT;

struct Solve{
    vector<bitset<MAXN>> A;          // ???OUT?
    vector<bitset<MAXN>> IN;         // ???IN????????????
    vector<vll> Dis;                 // Dis[u][v] = (???? - 1)???? -1
    bitset<MAXN> ised;               // ????? u ?? BFS ??

    Solve(){
        cin>>N>>Q;
        A.resize(N+5);
        IN.resize(N+5);
        Dis.resize(N+5, vll(N+5, -1));

        // ??????? i ?? j=i+1..N
        FOR(i,1,N){
            FOR(j,1,N-i){
                char a; cin>>a;
                int u=i, v=i+j;
                if(a=='0'){
                    // v -> u
                    A[v].set(u);
                    IN[u].set(v);
                }else{
                    // u -> v
                    A[u].set(v);
                    IN[v].set(u);
                }
            }
        }
        FOR(_,1,Q){
            reply();
        }
    }

    // ?? BFS???????? __ ????=__????? i ??Dis[u][i]=__-1
    void bfs(ll u){
        bitset<MAXN> vis, q; 
        vis.reset(); q.reset();
        q[u]=1; vis[u]=1;

        FOR(__,1,N){
            if(q.none()) break;

            // ???????????
            bitset<MAXN> sum; sum.reset();
            for(int i = q._Find_first(); i <= N; i = q._Find_next(i)){
                sum |= A[i];
            }
            // ????????
            bitset<MAXN> qq = (~vis) & sum;

            // ??????=__?????????? ??-1
            for(int i = qq._Find_first(); i <= N; i = qq._Find_next(i)){
                Dis[u][i] = __ - 1;
            }

            vis |= qq;
            q = qq;
        }
    }

    void reply(){ 
        ll u,v;
        cin>>u>>v;

        // k=0????
        if(A[u][v]){
            cout<<0<<"\n";
            return;
        }

        // k=1???????????? w: u->w && w->v?
        if ( (A[u] & IN[v]).any() ){
            cout<<1<<"\n";
            return;
        }

        // ????
        if(ised[u]){
            cout<<Dis[u][v]<<"\n";
            return;
        }

        // ???? u ???
        ised[u]=true;
        bfs(u);
        cout<<Dis[u][v]<<"\n";
    }
};

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    
    // cin>>lT;
    // while(lT--)
    Solve a;
    return 0;
}
/*

*/