标签：const 科林 明伦杯 题解 rhs int modint operator return

题目内容

传送门

前置知识

组合数
乘法逆元
Modular int模板

题目分析

分析输入与题意，本题关键即在推导有多少个不同数组的计算公式。

设当前数组最大值为 i，则有：

\[ans_i = C_{n + i - 1}^{i} \]

由于最大值的取值范围为 \(0\le x\le k\) 所以从 \(1\) 到 \(k\) 枚举 \(x\) 即可。

因此，

\[ans = \sum_{i = 0}^{k}i\times C_{n + i - 1}^{i} \]

代码实现

// URL: https://ac.nowcoder.com/acm/contest/37895/F
// Memory Limit: 524288 MB
// Time Limit: 2000 ms

#include <bits/stdc++.h>
using namespace std;

// #define int ll
using ll = long long;
using ull = unsigned long long;
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)

const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const int N = 2e6;

template <int mod>
struct modint {
    unsigned int _v;
    modint() : _v(0) {}
    template <class T>
    modint(T v) {
        ll x = (ll)(v % (ll)(umod()));
        if (x < 0) x += umod();
        _v = (unsigned int)(x);
    }
    modint(bool v) { _v = ((unsigned int)(v) % umod()); }

    static constexpr unsigned int umod() { return mod; }
    unsigned int val() const { return _v; }

    modint& operator++() {
        _v++;
        if (_v == umod()) _v = 0;
        return *this;
    }
    modint& operator--() {
        if (_v == 0) _v = umod();
        _v--;
        return *this;
    }
    modint operator++(int) {
        modint result = *this;
        ++*this;
        return result;
    }
    modint operator--(int) {
        modint result = *this;
        --*this;
        return result;
    }

    modint& operator+=(const modint& rhs) {
        _v += rhs._v;
        if (_v >= umod()) _v -= umod();
        return *this;
    }
    modint& operator-=(const modint& rhs) {
        _v -= rhs._v;
        if (_v >= umod()) _v += umod();
        return *this;
    }
    modint& operator*=(const modint& rhs) {
        ull z = _v;
        z *= rhs._v;
        _v = (unsigned int)(z % umod());
        return *this;
    }
    modint& operator/=(const modint& rhs) { return *this = *this * rhs.inv(); }

    modint operator+() const { return *this; }
    modint operator-() const { return modint() - *this; }

    modint pow(ll n) const {
        assert(n >= 0);
        modint x = *this, r = 1;
        for (; n; n >>= 1) {
            if (n & 1) r *= x;
            x *= x;
        }
        return r;
    }

    modint inv() const { return pow(umod() - 2); }

    friend modint operator+(const modint& lhs, const modint& rhs) { return modint(lhs) += rhs; }
    friend modint operator-(const modint& lhs, const modint& rhs) { return modint(lhs) -= rhs; }
    friend modint operator*(const modint& lhs, const modint& rhs) { return modint(lhs) *= rhs; }
    friend modint operator/(const modint& lhs, const modint& rhs) { return modint(lhs) /= rhs; }
    friend bool operator==(const modint& lhs, const modint& rhs) { return lhs._v == rhs._v; }
    friend bool operator!=(const modint& lhs, const modint& rhs) { return lhs._v != rhs._v; }
};
typedef modint<mod> mint;

int n, k;
mint ans, fact[N + 7], fact_inv[N + 7];
void init(int n = N + 5) {
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i;
    fact_inv[n] = fact[n].inv();
    for (int i = n - 1; i >= 0; --i) fact_inv[i] = fact_inv[i + 1] * (i + 1);
}
mint C(int n, int m) { return m > n ? 0 : fact[n] * fact_inv[n - m] * fact_inv[m]; }

signed main() {
    fastio;
    cin >> n >> k;
    init(n + k + 1);
    for (int i = 0; i <= k; ++i) ans += C(n + i - 1, i) * i;
    cout << ans.val();

    return 0;
}

结果

标签：const,科林,明伦杯,题解,rhs,int,modint,operator,return
From： https://www.cnblogs.com/ckb2008/p/solution-of-Colin-Minlon-Summer-Cup-F.html