前置知识:生成函数、组合数
先考虑平方怎么做。\(f_{i,j}\) 表示处理了前 \(i\) 个值,逆序对有 \(j\) 个。显然可以转移到 \(f_{i+1,j},f_{i+1,j+1},f_{i+1,j+2},...,f_{i+1,j+i}\)。然后发现这个东西是个很简单的递推,而且长得很生成函数,于是可以很自然的写成
\[1\times (1+x)\times(1+x+x^2)\times(1+x+x^2+x^3)\times... \]显然每一个乘数都是一个等比数列,所以根据小学学的等比数列求和公式,得到:
\[\sum_{i=1}^{n} \frac{1-x^i}{1-x} =\frac{1}{(1-x)^n}\sum_{i=1}^{n} (1-x^i) \]然后左边那个系数是一个经典的生成函数,他相当于 \((1+x+x^2+x^3+...)^n\)。显然 \(i\) 次项的系数是 \(i\) 个物品分给 \(n\) 个人且可以不拿到的方案数,即 \(i+n-1 \choose n-1\)。
比较难处理的是右边的。
假设是 \(\sum (1+x^i)\),那么 \(k\) 次项系数就是满足:
- 互不相同
- 不大于 \(n\)
- 和为 \(k\)
的正整数集合数,且 \(n,k \le 10^5\)。
根据「互不相同」「和为 \(k\)」这两个条件,容易想到 「集合大小最大为 \(\mathcal{O}(\sqrt{k})\)」 的经典结论。
然后考虑 dp。设 \(dp_{i,j}\) 表示选了 \(i\) 个数,和为 \(j\) 的方案数。初值是 \(dp_{0,0}=1\)
对于当前转移对象 \(dp_{i,j}\):
- 若 \(1\) 没被选,则可以把通过将集合内的所有数 \(+1\) 得到,此时和增加 \(i\),即
- 若 \(1\) 被选了,则可以把通过将集合内的所有数 \(+1\),并补充一个 \(1\) 到集合内得到,此时和增加 \(i\),即
但是还有一条限制——「不大于 \(n\)」。
转移过程中可能会出现集合内有数 \(>n\) 的情况,但是由于每次只会集体 \(+1\),所以那个 \(>n\) 的数一定是 \(n+1\)。因此有:
\[dp_{i,j}\gets dp_{i,j} - dp_{i-1,j-(n+1)} (j \ge n+1) \]然后问题就都解决了。
时间复杂度 \(\mathcal{O}(k \min(n,\sqrt{k}))\)。
// Author: AquariusZhao
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5, RTN = 500, MOD = 1e9 + 7;
int n, k, fac[N], inv[N], dp[RTN][N];
int ans;
inline int madd(int x, int y) { return x + y >= MOD ? x + y - MOD : x + y; }
inline int msub(int x, int y) { return madd(x, MOD - y); }
inline int mmul(int x, int y) { return 1ll * x * y % MOD; }
inline int qpow(int x, int y) { int res = 1, t = x % MOD;
while (y) { if (y & 1) res = mmul(res, t);
t = mmul(t, t); y >>= 1; }
return res; }
inline int mdiv(int x, int y) { return mmul(x, qpow(y, MOD - 2)); }
void init(int lmt)
{
fac[0] = inv[0] = 1;
for (int i = 1; i <= lmt; i++)
fac[i] = mmul(fac[i - 1], i);
inv[lmt] = mdiv(1, fac[lmt]);
for (int i = lmt - 1; i >= 1; i--)
inv[i] = mmul(inv[i + 1], i + 1);
}
int C(int x, int y)
{
if (x < y)
return 0;
if (y == 0)
return 1;
return mmul(fac[x], mmul(inv[x - y], inv[y]));
}
int main()
{
#ifdef aquazhao
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif
init(2e5);
cin >> n >> k;
dp[0][0] = 1;
int lmt = min(n, (int)(ceil(sqrt(k + k))));
for (int i = 1; i <= lmt; i++)
for (int j = i; j <= k; j++)
{
dp[i][j] = madd(dp[i][j - i], dp[i - 1][j - i]);
if (j >= (n + 1))
dp[i][j] = msub(dp[i][j], dp[i - 1][j - (n + 1)]);
}
for (int i = 0; i <= k; i++)
{
int sum = 0;
for (int j = 0; j <= lmt; j++)
sum = j & 1 ? msub(sum, dp[j][i]) : madd(sum, dp[j][i]);
ans = madd(ans, mmul(C(k - i + n - 1, n - 1), sum));
}
cout << ans << endl;
return 0;
}
标签:return,int,题解,inv,mmul,Day7,2017,dp,MOD
From: https://www.cnblogs.com/avalaunch/p/18542570