生成函数 + DP ，或者容斥，一道好题。
下面皆视 $n,k$ 同阶。
生成函数 $\mathcal O(k\sqrt{k})$
首先根据题意，得到答案得生成函数：
前面一部分是简单的，我们有 $\displaystyle \frac{1}{(1-x)^n}=\sum_{i\ge 0}\binom{n+i-1}{i}x^i$。于是考虑分子即可，注意到我们最多只会选出 $\mathcal O(\sqrt {k})$ 个 $-x^i$。再利用好每个 $-x^i$ 仅能选择一次这一点，我们进行 DP。设 $f(i,j)$ 表示选择了 $i$ 个，其和为 $j$ 的方案数。我们考虑两种转移：
- 前 $i$ 个数全部 $+1$： $f(i,j)\gets f(i,j-i)$。
- 前 $i-1$ 全部 $+1$，插入一个新的 $1$：$f(i,j)\gets f(i-1,j-i)$。
需要注意的是，若 $k>n$ ，那么其中的数可能会大于 $n$，我们减掉这一部分的答案即可。
- 若 $j>n$，$f(i,j)\gets -f(i-1,j-n-1)$。
DP 之后在乘上系数即可，时间复杂度 $\mathcal O(k\sqrt{k})$。
容斥 $\mathcal O(k\sqrt{k})$
有 $n$ 个数 $x_i$ 满足限制条件 $x_i\in[0,i-1]$，现在求满足 $\displaystyle \sum_{i=1}^{n} x_i=k$ 的 方案数。
真正限制我们的是 $x_i\in [0,i-1]$ 这一条件，我们考虑容斥去掉。钦定 $j\in S$ 中 $x_j$ 满足 $x_j\ge j$，我们将这些 $x_j$ 减去 $j$，那么所有的限制就变成了 $x_i\ge 0$，使用插板法即可直接算出答案。
现在我们相当于求从 $1,2,\cdots,i-1, i$ 选出若干个，使其和为 $j$。问题转化为与上面一模一样的 DP！！！这样时间复杂度也是 $\mathcal O(k\sqrt{k})$。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=1e5+10,M=500+10,mod=1e9+7;
template<class T>
inline void read(T &x)
{
x=0;bool f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
int n,m,k;
int f[M][N];
int fac[N<<1],ifac[N<<1];
inline int adj(int x){return x>=mod?x-mod:x;}
inline int qpow(int x,int k=mod-2)
{
int res=1;
while(k)
{
if(k&1)res=1ll*res*x%mod;
x=1ll*x*x%mod;
k>>=1;
}
return res;
}
inline void init(int n)
{
fac[0]=1;
for(int i=1;i<=n;i++)fac[i]=1ll*fac[i-1]*i%mod;
ifac[n]=qpow(fac[n]);
for(int i=n;i;i--)ifac[i-1]=1ll*ifac[i]*i%mod;
}
inline int C(int n,int m)
{
if(m>n)return 0;
return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
int main()
{
read(n,k);
init(n+k);
m=sqrt(k<<1)+1;
f[0][0]=1;
for(int i=1;i<=m;i++)
for(int j=i;j<=k;j++)
f[i][j]=adj(adj(f[i][j-i]+f[i-1][j-i])+((j>n)?(mod-f[i-1][j-n-1]):0));
int ans=0;
for(int i=0;i<=k;i++)
{
int res=0;
for(int j=0;j<=m;j++)
res=adj(res+((j&1)?(mod-f[j][k-i]):f[j][k-i]));
ans=adj(ans+1ll*C(n+i-1,i)*res%mod);
}
printf("%d\n",ans);
return 0;
}
|
能不能再给力一点？
生成函数 + 多项式 exp $\mathcal O(n\log n)$
我们还是写出其生成函数：
前一部分还是一样，我们有 $\displaystyle \frac{1}{(1-x)^n}=\sum_{i\ge 0}\binom{n+i-1}{i}x^i$。考虑后一部分，利用 P4389 付公主的背包 一样的技巧，先对其取 $\ln$ 将其转化为加法。我们有下面的式子：
这个式子可以通过泰勒展开得到，当然也可以通过对两边求导得到。
所以我们得到：
右边暴力 $\mathcal O(n\ln n)$ 枚举，再做一次多项式 $\exp $ 即可，最后乘上 $\displaystyle \frac{1}{(1-x)^n}=\sum_{i\ge 0}\binom{n+i-1}{i}x^i$ 即可。时间复杂度为 $\mathcal O(n\log n)$。需要用到任意模数 NTT。