牛客周赛 Round 113 题解，C++ version。

A 小红取模

直接求和取模即可。

void solve() {
    string s;
    cin >> s;
    int t = 0;
    for (auto v : s) t += v - '0';
    cout << t % 9 << "\n";
}

B 小红的复数

。

typedef MInt<MOD> Z;

void solve() {
    int n;
    cin >> n;
    Z a, b;
    cin >> a >> b;
    for (int i = 1; i < n; ++i) {
        Z x, y;
        cin >> x >> y;
        Z p, q;
        p = x * a - y * b;
        q = a * y + b * x;
        a = p, b = q;
    }
    cout << a << " " << b << "\n";
}

C 小红的k次方

即求数组乘积中有多少个 ，因为 ，所以对于每个元素，统计 的个数即可，最后答案为 。

void solve() {
    int n, c1 = 0, c2 = 0, c3 = 0;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        while (x % 2 == 0) {
            c1++;
            x /= 2;
        }
        while (x % 3 == 0) {
            c2++;
            x /= 3;
        }
        while (x % 5 == 0) {
            c3++;
            x /= 5;
        }
    }
    cout << min({c1, c2, c3}) << "\n";
}

D 小红模5

对于拼接后的数字，它模 的结果就是这个排列最后一个数字模 的结果。前面数字的排列数为

void solve() {
    ll n;
    Z ans = 0;
    cin >> n;
    for (int i = 1; i <= n; ++i) ans += i % 5;
    cout << ans*C.P(n - 1, n - 1) << "\n";
}

E 二小姐取数

对数组 和 做计数

• 表示从 中选 个数，和对 取模为 的方案数。
• 表示从 中选 个数，和对 取模为 的方案数。

再对 做前缀和， 表示从 中选不超过 个数，和对 取模为 的方案数。

最后对于每个 ，把 和 做模加卷积即可。

void solve() {
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int i = 0; i < n; ++i) cin >> b[i];

    vector<vector<Z>> dp1(n + 1, vector<Z>(M));
    dp1[0][0] = 1;
    for (int x : a) {
        int v = x % M;
        for (int i = n; i >= 1; --i) {
            for (int j = 0; j < M; ++j) {
                int nj = (j + v) % M;
                dp1[i][nj] += dp1[i - 1][j];
            }
        }
    }

    vector<vector<Z>> dp2(n + 1, vector<Z>(M));
    dp2[0][0] = 1;
    for (int x : b) {
        int v = x % M;
        for (int i = n; i >= 1; --i) {
            for (int j = 0; j < M; ++j) {
                int nj = (j + v) % M;
                dp2[i][nj] += dp2[i - 1][j];
            }
        }
    }

    vector<vector<Z>> pre(n + 1, vector<Z>(M));
    for (int j = 0; j < M; ++j) {
        Z s = 0;
        for (int i = 0; i <= n; ++i) {
            s += dp2[i][j];
            pre[i][j] = s;
        }
    }

    vector<Z> ans(M);
    for (int i = 0; i <= n; ++i) {
        bool f1 = true, f2 = true;
        for (int j = 0; j < M; ++j) {
            if (dp1[i][j].val() != 0) {
                f1 = false;
                break;
            }
        }
        if (f1) continue;
        for (int j = 0; j < M; ++j) {
            if (pre[i][j].val() != 0) {
                f2 = false;
                break;
            }
        }
        if (f2) continue;

        for (int rA = 0; rA < M; ++rA) {
            if (dp1[i][rA].val() == 0) continue;
            for (int rB = 0; rB < M; ++rB) {
                if (pre[i][rB].val() == 0) continue;
                int t = (rA + rB) % M;
                ans[t] += dp1[i][rA] * pre[i][rB];
            }
        }
    }

    for (int i = 0; i < M; ++i) cout << ans[i] << " ";
    cout << "\n";
}

F 二小姐的区间查询

，总共有 种类型，区间内只要统计每种类型的出现次数 ，答案就等于对所有类型对 枚举。

int encode(ll x) {
    int c1 = 0, c2 = 0, c3 = 0;
    while (c1 < 2 && x % 3 == 0) {
        x /= 3;
        c1++;
    }
    if (x % 5 == 0) c2 = 1;
    if (x % 11 == 0) c3 = 1;
    return c1 * 4 + c2 * 2 + c3;
}

void solve() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];

    vector<int> type(n + 1);
    for (int i = 1; i <= n; i++) type[i] = encode(a[i]);

    vector<vector<int>> init(12, vector<int>(n + 1, 0));
    for (int i = 1; i <= n; i++) init[type[i]][i] = 1;

    vector<SegTree<int>> st;
    for (int t = 0; t < 12; t++) {
        st.eb(n);
        st[t].build(init[t]);
    }

    int c1[12], c2[12], c3[12];
    for (int t = 0; t < 12; t++) {
        c1[t] = t / 4;
        c2[t] = (t % 4) / 2;
        c3[t] = t % 2;
    }

    while (q--) {
        int op, x, y;
        cin >> op >> x >> y;
        if (op == 1) {
            int nt = encode(y);
            if (nt != type[x]) {
                st[type[x]].modify(x, 0);
                st[nt].modify(x, 1);
                type[x] = nt;
            }
        } else {
            ll cnt[12] = {0};
            for (int t = 0; t < 12; t++)
                cnt[t] = st[t].ask(x, y).val;

            ll ans = 0;
            for (int t = 0; t < 12; t++) {
                if (cnt[t] == 0) continue;
                if (c1[t] * 2 >= 2 && c2[t] * 2 >= 1 && c3[t] * 2 >= 1) {
                    ans += cnt[t] * (cnt[t] - 1) / 2;
                }
                for (int u = t + 1; u < 12; u++) {
                    if (cnt[u] == 0) continue;
                    if (c1[t] + c1[u] >= 2 && c2[t] + c2[u] >= 1 && c3[t] + c3[u] >= 1) {
                        ans += cnt[t] * cnt[u];
                    }
                }
            }
            cout << ans << "\n";
        }
    }
}

头文件

//Another
#include<bits/stdc++.h>
#include<bits/extc++.h>
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef tuple<ll, ll, ll> TLLL;
typedef __gnu_pbds::tree<PLL, __gnu_pbds::null_type, less<PLL>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update> Tree;
// typedef __gnu_pbds::tree<ll, __gnu_pbds::null_type, less<ll>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update> Tree;

constexpr int inf = (ll)1e9 + 7;
constexpr ll INF = (ll)2e18 + 9;
// constexpr ll INF = (ll)4e18;
// constexpr ll MOD = 1e9 + 7;
constexpr ll MOD = 998244353;
constexpr ld PI = acos(-1.0);
constexpr ld eps = 1e-10;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ull randint(ull l, ull r) {uniform_int_distribution<unsigned long long> dist(l, r); return dist(rng);}

void init() {

}

void solve() {
    
}

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

    init();

    int t = 1;
    cin >> t;
    for (int _ = 1; _ <= t; ++_) {
        solve();
    }
    return 0;
}

自动取模

template<int P>
struct MInt {
    int x;
    constexpr MInt() : x{} {}
    constexpr MInt(long long v) : x{norm(v % getMod())} {}

    static int Mod;
    constexpr static int getMod() {
        if (P > 0) return P;
        else return Mod;
    }
    constexpr static void setMod(int Mod_) {
        Mod = Mod_;
    }
    constexpr static int norm(long long v) {
        if (v < 0) v += getMod();
        if (v >= getMod()) v -= getMod();
        return int(v);
    }

    constexpr int val() const { return x; }
    explicit constexpr operator int() const { return x; }

    constexpr MInt operator-() const {
        return MInt(norm(getMod() - x));
    }

    constexpr MInt inv() const {
        assert(x != 0);
        return pow(getMod() - 2);
    }

    constexpr MInt pow(long long e) const {
        MInt res(1), base(*this);
        while (e > 0) {
            if (e & 1) res *= base;
            base *= base;
            e >>= 1;
        }
        return res;
    }

    constexpr MInt &operator*=(MInt rhs) & {
        x = int(1LL * x * rhs.x % getMod());
        return *this;
    }
    constexpr MInt &operator+=(MInt rhs) & {
        x = norm(x + rhs.x);
        return *this;
    }
    constexpr MInt &operator-=(MInt rhs) & {
        x = norm(x - rhs.x);
        return *this;
    }
    constexpr MInt &operator/=(MInt rhs) & {
        return *this *= rhs.inv();
    }

    friend constexpr MInt operator*(MInt lhs, MInt rhs) { return lhs *= rhs; }
    friend constexpr MInt operator+(MInt lhs, MInt rhs) { return lhs += rhs; }
    friend constexpr MInt operator-(MInt lhs, MInt rhs) { return lhs -= rhs; }
    friend constexpr MInt operator/(MInt lhs, MInt rhs) { return lhs /= rhs; }

    friend istream &operator>>(std::istream &is, MInt &a) {
        long long v;
        is >> v;
        a = MInt(v);
        return is;
    }
    friend ostream &operator<<(std::ostream &os, const MInt &a) {
        return os << a.val();
    }

    friend constexpr bool operator==(MInt lhs, MInt rhs) { return lhs.val() == rhs.val(); }
    friend constexpr bool operator!=(MInt lhs, MInt rhs) { return lhs.val() != rhs.val(); }
};

template<>
int MInt<0>::Mod = 998244353;

typedef MInt<MOD> Z;

组合数学

struct Comb {
	int n;
	vector<Z> _fac;
	vector<Z> _invfac;
	vector<Z> _inv;

	Comb() : n{0}, _fac{1}, _invfac{1}, _inv{0} {}
	Comb(int n) : Comb() {
		init(n);
	}

	void init(int m) {
		if (m <= n) return;
		_fac.resize(m + 1);
		_invfac.resize(m + 1);
		_inv.resize(m + 1);

		for (int i = n + 1; i <= m; i++) {
			_fac[i] = _fac[i - 1] * i;
		}
		_invfac[m] = _fac[m].inv();
		for (int i = m; i > n; i--) {
			_invfac[i - 1] = _invfac[i] * i;
			_inv[i] = _invfac[i] * _fac[i - 1];
		}
		n = m;
	}

	Z fac(int m) {
		if (m > n) init(2 * m);
		return _fac[m];
	}
	Z invfac(int m) {
		if (m > n) init(2 * m);
		return _invfac[m];
	}
	Z inv(int m) {
		if (m > n) init(2 * m);
		return _inv[m];
	}
	Z P(int n, int m) {
		if (n < m || m < 0) return 0;
		return fac(n) * invfac(n - m);
	}
	Z C(int n, int m) {
		if (n < m || m < 0) return 0;
		return fac(n) * invfac(m) * invfac(n - m);
	}
} C;

线段树

template<typename Int>
struct Tag {
    Int v = 0;
    void operator+=(const Tag<Int> &o) {
        v += o.v;
    }
    bool check() {
        return v != 0;
    }
};

template<typename Int>
struct Info {
    Int val = 0;
    int l, r;
    Info operator+(const Info<Int> &o) const {
        Info res;
        res.l = l;
        res.r = o.r;
        res.val = val + o.val;
        return res;
    }
    void operator+=(const Tag<Int> &o) {
        val += o.v * (r - l + 1);
    }
    bool check() {
        return l != r;
    }
};

template<typename Int>
class SegTree {
private:
    vector<Info<Int>> info;
    vector<Tag<Int>> tag;
    int n;

    int ls(int x) {return x << 1;}
    int rs(int x) {return x << 1 | 1;}

    void print(int x, int l, int r) {
        cout << x << ":[" << l << "," << r << "],val:" << info[x].val << ",tag:" << tag[x].v << "\n";
        if (l == r) return;
        int mid = l + r >> 1;
        print(ls(x), l, mid);
        print(rs(x), mid + 1, r);
    }

    template<typename Array>
    void build(int x, int l, int r, Array &data) {
        if (l == r) {
            info[x].l = l;
            info[x].r = r;
            info[x].val = data[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(ls(x), l, mid, data);
        build(rs(x), mid + 1, r, data);
        info[x] = info[ls(x)] + info[rs(x)];
    }

    void push_down(int x) {
        if (tag[x].check() && info[x].check()) {
            info[ls(x)] += tag[x];
            info[rs(x)] += tag[x];
            tag[ls(x)] += tag[x];
            tag[rs(x)] += tag[x];
            tag[x] = {0};
        }
    }

    void update(int x, int l, int r, int lq, int rq, Tag<Int> v) {
        if (rq < l || lq > r) return;
        if (lq <= l && r <= rq) {
            info[x] += v;
            tag[x] += v;
            return;
        }
        push_down(x);
        int mid = (l + r) >> 1;
        update(ls(x), l, mid, lq, rq, v);
        update(rs(x), mid + 1, r, lq, rq, v);
        info[x] = info[ls(x)] + info[rs(x)];
    }

    void modify(int x, int l, int r, int pos, Int v) {
        if (r < pos || l > pos) return;
        if (l == r && l == pos) {
            info[x].val = v;
            return;
        }
        int mid = (l + r) >> 1;
        modify(ls(x), l, mid, pos, v);
        modify(rs(x), mid + 1, r, pos, v);
        info[x] = info[ls(x)] + info[rs(x)];
    }

    Info<Int> ask(int x, int l, int r, int lq, int rq) {
        if (rq < l || lq > r) return {0};
        if (lq <= l && r <= rq) return info[x];
        push_down(x);
        int mid = (l + r) >> 1;
        auto ans = ask(ls(x), l, mid, lq, rq) + ask(rs(x), mid + 1, r, lq, rq);
        return ans;
    }
public:
    SegTree(int n_): n(n_), info(4 * n_ + 1), tag(4 * n_ + 1) {}

    void print() {
        print(1, 1, n);
    }

    template<typename Array>
    void build(Array &data) {
        build(1, 1, n, data);
    }

    void update(int l, int r, Tag<Int> v) {
        update(1, 1, n, l, r, v);
    }

    void modify(int pos, Int v) {
        modify(1, 1, n, pos, v);
    }

    Info<Int> ask(int l, int r) {
        return ask(1, 1, n, l, r);
    }
};