【51nod 1251】 Fox序列的数量（以及带限制插板法讲解）

为什么网上没有篇详细的题解【雾

可能各位聚聚觉得这道题太简单了吧 /kk

题意

首先题目是求满足条件的序列个数，条件为：出现次数最多的数仅有一个

分析

感谢 刚睡醒的 JZ姐姐在咱写题解忽然陷入自闭的时候为咱知道迷津 QwQ

那么套路来说第一想到的其实就是容斥辣 然后懒得想去网上黈力【雾

在然后，发现网上要么没推导公式（虽说是直接列不用化简的）要么就是推导公式是错的...

于是坐下来冷静分析：首先，我们考虑最高的出现次数为 x 的情况下，有多少个序列是满足条件的

容斥一发发现式子长这个样子（用到了隔板法，然后容斥顺便也能把有数字出现次数高于 x 的情况给容掉）

\[ans(x)=m\sum_{j=0}^{m-1} (-1)^j \binom{n-x*(j+1) + m-2 }{m-2}
\]

大概是说，我们确定最高次数为 x ，那么我们先钦定一个数为恰好出现 x 次的数，然后剩下 m-1 个数插板容斥求方案 QwQ ，于是我们就可以递推求解辣：

\[ANS=\sum_{i=\lceil \frac{n}{m} \rceil }^n m\sum_{j=0}^{m-1} (-1)^j \binom{n-i*(j+1)+m-2} {m-2}
\]

然后我们发现复杂度爆炸了呢 Σ(⊙▽⊙"a 管他呐，交上去就好辣

然后咱发现后面那个式子如果 \(n-i*(j+1)+m-2\) 大于 \(m-2\) 的话贡献为 0 ，一顿计算发现 j 要小于 n/i 才有贡献，那么第二个枚举的上界的 m-1 改一改就好咯...

\[ANS=\sum_{i=\lceil \frac{n}{m} \rceil }^n m\sum_{j=0}^{min(m-1,n/i-1)} (-1)^j \binom{n-i*(j+1)+m-2} {m-2}
\]

然后调和级数分析一波，发现复杂度是 \(n·H(n)\) 的，能过...

顺便稍微讲讲带限制的板怎么插好了 QAQ

注意这里说的限制是对于任意两个隔板之间的元素数量而言，如果隔板间元素数量的限制是不同，可能需要什么黑科技（反正咱只会指数级别容斥【逃）

那么假设现在有 n 个元素，要分成 m 堆元素，也就是有 m-1 个插板

0.不带限制的插板

显然是 \(\binom{n+m-1}{m-1}\)

意思就是我们把 n 个元素和 m-1 个插板排成一列，计算方案数

那么我们只要计算 m-1 个插板有多少种摆法就好了，隔板确定完了，元素的放法自然就确定了

说白了就是求了个 m-1 个插板在所有 n+m-1 个物品中的位置方案数

1.带下界的插板

假设下界为 x ，即隔出来的每堆元素数量不小于 x

答案是 \(\binom{n+m-m·x-1}{m-1}\)

我们发现这玩意儿比较简单，只要把原本要拿来插板的元素先减去 \(m*x\) （也就是预先给每堆元素分掉这个下界 ） 然后再去插板就好辣

2.（JZ 姐姐教的QwQ）带上界的插板

假设上界为 x ，即隔出来的每堆元素数量不大于 x

答案是 \(\sum_{i=0}^{m} (-1)^i \binom{m}{j} \binom{n+m-i*(x+1)-1}{m-1}\)

有容斥呢 QwQ 解释一下，就是说我们枚举超出上限的元素堆个数，然后强制他们选了 (x+1) 个，这样不管它们接下来怎么选都已经超限了，然后我们加个 \((-1)\) 的幂次容斥一下就好辣

如果康不懂的话请重修容斥 QvQ

这样咱发现上面的那个式子一下子就很明了了呢 QvQ

Code

注意阶乘及逆元的 1e5 数组是假的，要两倍的！花了咱 5 点头盾 get 到的细节 【枯

//by Judge

#define HGS_AK_IOI true

#include<bits/stdc++.h>

#define mod 1000000007

#define Rg register

#define fp(i,a,b) for(Rg int i=(a),I=(b)+1;i<I;++i)

#define fd(i,a,b) for(Rg int i=(a),I=(b)-1;i>I;--i)

#define go(u) for(Rg int i=head[u],v=e[i].to;i;v=e[i=e[i].nxt].to)

#define open(S) freopen(S".in","r",stdin),freopen(S".out","w",stdout)

#define ll long long

using namespace std;

const int M=2e5+3;

typedef int arr[M];

#ifndef Judge

#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)

#endif

char buf[1<<21],*p1=buf,*p2=buf;

template<class T>inline T Min(T x,T y){return x<y?x:y;}

template<class T>inline T Max(T x,T y){return x>y?x:y;}

template<class T>inline bool cmax(T& a,T b){return a<b?a=b,1:0;}

template<class T>inline bool cmin(T& a,T b){return a>b?a=b,1:0;}

inline int read(){ int x=0,f=1; char c=getchar();

	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;

	for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f;

} int n,m,ans; arr fac,inv;

inline int mul(int x,int y){return 1ll*x*y%mod;}

inline void Pls(int& x,int y){if((x+=y)>=mod)x-=mod;}

inline int qpow(int x,int p=mod-2){ Rg int s=1;

	for(;p;p>>=1,x=mul(x,x)) if(p&1) s=mul(s,x); return s;

}

inline void prep(int n=2e5){

	fac[0]=1; fp(i,1,n) fac[i]=mul(fac[i-1],i);

	inv[n]=qpow(fac[n]); fd(i,n,1) inv[i-1]=mul(inv[i],i);

}

inline int Ceil(int x,int y){ return x%y>0?x/y+1:x/y; }

inline int C(int n,int m){ if(n<m) return 0;

	return mul(fac[n],mul(inv[m],inv[n-m]));

}

inline void Solv(){ n=read(),m=read(),ans=0;

	if(m==1) return printf("1\n"),void();

	if(n==1) return printf("%d\n",m),void();

	fp(i,Ceil(n,m),n) fp(j,0,Min(n/i-1,m-1))

		Pls(ans,mul(j&1?(mod-1):1, mul(C(m-1,j),C(n+m-i*(j+1)-2,m-2)) ));

	printf("%d\n",mul(ans,m));

}

int main(){

#ifdef Judge

freopen("1.in","r",stdin);

#endif

	int T=read(); prep();

	while(T--) Solv(); return 0;

}