# 「hackerrank – 101hack43」K-Inversion Permutations(「hackerrank – 101hack43」K-Inversion Permutations)-其他

## 「hackerrank – 101hack43」K-Inversion Permutations(「hackerrank – 101hack43」K-Inversion Permutations)

https://blog.csdn.net/a_crazy_czy/article/details/72862151

https://blog.csdn.net/a_crazy_czy/article/details/72862151

#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;
}

————————

The original question is: please give the number of different sequences \ (\ {a_n \} \), which meet \ (0 \ leqslant a_i & lt; I \), and \ (\ sum a_i = k \).

The answer to the ogf of writing out \ ({{a u u u n} \) in the form of a \ ({a u u u u n} \) is the following \ (\ displayststyle [x ^ k] \ left (g (x) (x (x)) left (g (x (x) (x (x)) in the past \ (\ displadisplayststyle [x ^ k [x ^ k [x {a {a u u {I = 0}} {a u u u u u u {a u u u u {a u u u u u u u u u u {I = x {u u u u u u u u u {I = 0} {{{1-x {{{1-x {{1-x {1-x {1-x {1-x ^ I {1-x {(1-x ^ I)} {(the.

The preceding bracket has a combinatorial meaning, that is, there are \ (n \) items, the \ (I \) th volume is \ (I \), and there is a knapsack with a capacity of \ (K \). Find the number of schemes that just fill the knapsack. This number of schemes should also be multiplied by a coefficient \ (- 1) ^ m \), \ (m \) is the number of selected items.

You can count the back one directly, and the front one can DP. Consider such a construction process:

There was nothing at first. For existing numbers, we have two operations: one is to add all \ (1 \), the other is to add all \ (1 \), and then add a number with a value of \ (1 \). In this way, the sequence constructed after several operations must meet the conditions.
https://blog.csdn.net/a_ crazy_ czy/article/details/72862151

There was nothing at first. For existing numbers, we have two operations: one is to add all \ (1 \), the other is to add all \ (1 \), and then add a number with a value of \ (1 \). In this way, the sequence constructed after several operations must meet the conditions.

https://blog.csdn.net/a_crazy_czy/article/details/72862151

Then set \ (f (I, J) \) as the number of selected \ (I \), and the current sum is the number of schemes of \ (J \). The transfer is very simple, which can be simulated according to two operations.

It’s so divine. I don’t have enough brains. Then the scale of the first dimension is the root sign, so it can pass.

#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;
}