题目内容
前置知识
题目分析
分析输入与题意,本题关键即在推导有多少个不同数组的计算公式。
设当前数组最大值为 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;
}
结果