【JZOJ4800】周末晚会 题解

题目大意

  n 个人围绕着圆桌坐着，其中一些是男孩，另一些是女孩。你的任务是找出所有合法的方案数，使得不超过 k 个女孩座位是连续的。循环同构会被认为是同一种方案。
  数据组数 T<=50， n, k<=2000

【20%】n,k<=20

  暴力还是有点麻烦。
  主要思想就是用最小表示法来去重。
  不多说了。。。

【100%】n,k<=2000

  模型是burnside的经典模型。。。
  对于第 i 个置换（0<=i<=n-1），只有开头的 d=gcd(i,n) 个位置的颜色选择是自由的，然后把这一段复制 n/d 份构成完整序列。

  看看这个 d 个位置有什么限制？1、连续的女孩（用0表示）不超过 k 个；2、开头连续的 0 加上末尾连续的 0 不超过 k 个，这是因为把这一段复制之后要头尾拼接。

  直接在 d 个位置上dp不好搞，因为要维护头尾的 0 加起来不超过 k 个。所以设 $f[k][i]$ 表示：我搞 i 个位置出来，这 i 个位置头尾都是 1，其内部连续的 0 不超过 k，的方案数。（实际dp中第一维可以去掉）
  这个dp很好搞，对于 i 枚举上一个 1 放在哪里就行了，这是O(n)的。

  回到题目，我现在要 d 个位置，那我们可以枚举 i，相当于枚举了 d 个中的一段，然后我们在前后补 0，总共补 d-i 个0。所以 i 的贡献就是 $f[k][i] \times (d-i+1)$。这里我们可以看出维护一个 f 的前缀和以及一个 f×i 的前缀和就行了。
  头尾加起来 <=k 就相当于 d-i<=k。如果上面用前缀和的话，减掉不合法的就行了。

  再特殊处理一下全段都是 0 就好了。

代码

//这里我的 f 是从 0 开始的，所以 f[i] 的长度实际上是 i+1

#include<cstdio>
#define fo(i,a,b) for(int i=a;i<=b;i++)
using namespace std;

typedef long long LL;

const int maxn=2005;
const LL mo=1e8+7;

int n,k;

LL f[maxn],s[maxn][maxn],sx[maxn][maxn];
void pre(int n)
{
	fo(k,1,n)
	{
		f[0]=1;
		LL t=1;
		fo(i,1,n)
		{
			f[i]=t;
			t=(t+f[i])%mo;
			if (i>k) t=(t-f[i-k-1]+mo)%mo;
		}
		
		s[k][0]=1;
		fo(i,1,n)
		{
			s[k][i]=(s[k][i-1]+f[i])%mo;
			sx[k][i]=(sx[k][i-1]+f[i]*i%mo)%mo;
		}
	}
}

int gcd(int a,int b) {return (b) ?gcd(b,a%b) :a ;}

LL mi(LL x,LL y)
{
	LL re=1;
	for(; y; y>>=1, x=x*x%mo) if (y&1) re=re*x%mo;
	return re;
}

int T;
int main()
{
	pre(2000);
	
	scanf("%d",&T);
	while (T--)
	{
		scanf("%d %d",&n,&k);
		if (n==0 || k==0) {printf("0\n"); continue;}
		
		LL ans=0;
		fo(i,0,n-1)
		{
			LL d=gcd(n,i);
			ans=(ans+s[k][d-1]*d%mo-sx[k][d-1]+mo)%mo;
			if (d-k-2>=0) ans=(ans-s[k][d-k-2]*d%mo+sx[k][d-k-2]+mo)%mo;
			if (k>=n) ans=(ans+1)%mo;
		}
		ans=ans*mi(n,mo-2)%mo;
		
		printf("%lld\n",ans);
	}
}