脚本宝典收集整理的这篇文章主要介绍了「hackerrank - 101hack43」K-Inversion Permutations，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
link。
原问题即：请你给出不同的序列 ({a_n}) 的数量，满足 (0leqslant a_i<i)，且 (sum a_i=k)。
那么写出 ({a_n}) 的 ogf，可得答案为：(displaystyle [x^k]left(G(x)=sum_{i=0}^{n-1} x^i=frac{1-x^n}{1-x}right)=frac{PRod_{i=1}^n(1-x^i)}{(1-x)^n}=left(prod_{i=1}^n(1-x^i)right)left(sum_{i=0}^nbinom{n-1+i}{i} x^iright))。
前面那个括号是有组合意义的，即有 (n) 个物品，其第 (i) 个体积为 (i)，有个容量 (k) 的背包，求恰好填满背包的方案数，这个方案数还要乘一个系数 ((-1)^m)，(m) 为选的物品的个数。
后面那个你就直接算，前面的可以 dp。考虑这样一个构造过程：
一开始什么数都没有。对已有的数，我们有两种操作，一种是全部加 (1)，一种是全部加 (1) 然后再加入一个值为 (1) 的数。这样执行若干次操作之后构造出来的数列一定满足条件。
然后就设 (f(i,j)) 为选了 (i) 个数，目前的和为 (j) 的方案数，转移很简单，依照两种操作模拟即可。
太神仙了，我脑子不够用。然后第一维的规模是根号，所以能过了。
#include <bITs/stdc++.h>
constexpr int kMod = 1e9 + 7;
constexpr int kN = 1e5, kSqrt = 500;
int n, k, f[kSqrt + 5][kN + 5], fac[kN * 2 + 5], ifac[kN * 2 + 5];
inline void addeq(int& u, const int v) { (u += v) >= kMod && (u -= kMod); }
inline void muleq(int& u, const int v) { u = static_cast<long long>(u) * v % kMod; }
inline void subeq(int& u, const int v) { (u -= v) < 0 && (u += kMod); }
inline int add(int u, const int v) { return (u += v) < kMod ? u : u - kMod; }
inline int mul(const int u, const int v) { return static_cast<long long>(u) * v % kMod; }
inline int mpow(int x, int y) {
int res = 1;
for (; y; y >>= 1, muleq(x, x))
if (y & 1) muleq(res, x);
return res;
}
template <tyPEname... args>
inline int mul(const int u, const int v, const Args... args) { return mul(u, mul(v, args...)); }
inline void init(const int n) {
fac[0] = 1;
for (int i = 1; i <= n; ++i) fac[i] = mul(fac[i - 1], i);
ifac[n] = mpow(fac[n], kMod - 2);
for (int i = n - 1; ~i; --i) ifac[i] = mul(ifac[i + 1], i + 1);
}
inline int com(const int x, const int y) { return mul(fac[x], ifac[x - y], ifac[y]); }
signed main() {
init(2 * kN);
std::cin >> n >> k;
f[0][0] = 1;
const int kS = std::trunc(std::sqrt(k * 2) + 1);
for (int i = 1; i <= kS; ++i)
for (int j = 0; j <= k; ++j) {
if (j >= i) f[i][j] = add(f[i - 1][j - i], f[i][j - i]);
if (j >= n + 1) subeq(f[i][j], f[i - 1][j - n - 1]);
}
int res = 0;
for (int i = 0; i <= kS; ++i)
for (int j = 0; j <= k; ++j) addeq(res, mul((i & 1) ? kMod - 1 : 1, f[i][j], com(k - j + n - 1, k - j)));
std::cout << res << "n";
return 0;
}
以上是脚本宝典为你收集整理的「hackerrank - 101hack43」K-Inversion Permutations全部内容，希望文章能够帮你解决「hackerrank - 101hack43」K-Inversion Permutations所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。