I have no reason for giving up.
link
一道不错的题。
先考虑 \(n^2\) 做法，比较显然，将数字从小到大插入，直接做 dp 即可。
我们将上面的插入过程抽象化。记 \([l,r]\) 为在 \(l\sim r\) 中选一个数。
则即求：\(\sum_{i=1}^n[0,i-1]=k\) 的方案总数。发现这就是一个多重集排列的板子。（多重集排列例题）
但是暴力容斥时间会直接飞起来。但你考虑我们容斥 dfs 搜完总和为 \(s\)，那么贡献就要改变 \(f*\binom {n-1} {n-1+k-s}\)。既然式子都写得出来，何必爆搜算？我们能不能直接合并同类项呢？
所以现在我们的问题就转化为了如何快速求出在 \(0\sim n-1\) 中选数，使其总和为 \(s\) 的总贡献。其中如果有偶数个数，系数为 \(1\)，否则为 \(-1\)。
考虑 dp，设 \(dp[i][j]\) 为选了 \(i\) 个数，总和为 \(j\) 的方案。发现这里的第一维 \(\le 2\sqrt s\)。（因为最小为 \(0+1+2+3+...\)）
考虑一个很套路的转移，每次我们要么使当前选的数加 \(1\)，要么新加入一个 \(0\)，再全部加 \(1\)。可以证明这样弄出来的序列是单调递减的。这里运用了 dp 中直接构造答案序列的思想。
那么如果不考虑这个最大选的数 \(\le n\) 的限制，我们会容易地得到方程式：\(dp[i][j]=dp[i-1][j-i]+dp[i][j-i]\)。
考虑这个限制，发现 dp 中我们不方便快速地得到第一个数（即最大的数）\(>n\) 的数量。
但最方便地，肯定是想在最大值成为 \(n+1\) 时就将这种情况灭了。那么如果第一个数为 \(n+1\)，有多少种方案？发现方案数为 \(dp[i-1][j-(n+1)]\)，即我限制第一个必须为 \(n+1\)，剩下的必须 \(\le n\)，分配 \(j-(n+1)\) 个数，刚好符合 \(dp[i-1][j-(n+1)]\) 的定义。
则 \(dp[i][j]=dp[i][j]=dp[i-1][j-i]+dp[i][j-i]-dp[i-1][j-(n+1)]\)。
然后处理出 dp 后直接容斥即可。
时间复杂度：\(\mathcal {O}(n\sqrt n)\)。
#include <algorithm>
#include <cmath>
#include <cstring>
#define LL long long
using namespace std;
const int MAXN = 1e5 + 5, Mod = 1e9 + 7;
int n, k, dp[800][MAXN], t, jc[MAXN << 1], inv[MAXN << 1], ans;
int Qpow(int x, int y) {
int ans = 1;
for(; y; y >>= 1) {
if(y & 1) ans = (LL)ans * x % Mod;
x = (LL)x * x % Mod;
}
return ans;
}
int C(int x, int y) { return x < y ? 0 : (LL)jc[x] * inv[y] % Mod * inv[x - y] % Mod; }
int main() {
scanf("%d%d", &n, &k); t = 2 * sqrt(k); jc[0] = 1;
for(int i = 1; i <= n + k; i ++) jc[i] = (LL)jc[i - 1] * i % Mod;
inv[n + k] = Qpow(jc[n + k], Mod - 2);
for(int i = n + k - 1; i >= 0; i --) inv[i] = (LL)inv[i + 1] * (i + 1) % Mod;
dp[0][0] = 1;
for(int i = 1; i <= t; i ++) {
for(int j = 1; j <= k; j ++) {
if(j >= i) dp[i][j] += dp[i][j - i];
if(dp[i][j] >= Mod) dp[i][j] -= Mod;
if(j >= i) dp[i][j] += dp[i - 1][j - i];
if(dp[i][j] >= Mod) dp[i][j] -= Mod;
if(j >= n + 1) dp[i][j] = (dp[i][j] - dp[i - 1][j - n - 1] + Mod) % Mod;
}
}
for(int i = 0; i <= t; i ++) {
for(int j = 0; j <= k; j ++) {
ans = (ans + ((i & 1) ? -1 : 1) * dp[i][j] * (LL)C(n - 1 + k - j, n - 1)) % Mod;
}
}
printf("%d", (ans + Mod) % Mod);
return 0;
}