BZOJ1547 周末晚会 | NekoMio's Blog

Description

Irena和Sirup正准备下个周末的Party。为这个Party,他们刚刚买了一个非常大的圆桌。他们想邀请每个人，但他们现在不知道如何分配座次。Irena说当有超过K个女孩座位相邻（即这些女孩的座位是连续的，中间没有男孩）的话，她们就会说一整晚的话而不和其他人聊天。 Sirup没有其他选择，只有同意她。然而，作为一名数学家，他很快地痴迷于所有可能方案。题目说明： $N$个人围绕着圆桌坐着，其中一些是男孩，另一些是女孩。你的任务是找出所有合法的方案数，使得不超过$K$个女孩座位是连续的。循环同构会被认为是同一种方案。

Input

第一行有一个数$T$，表示以下有$T$组数据，每组数据有两个整数$N$，$K$。每组数据之间有一个空行隔开。

Output

输出$T$行，每行顺次对应一组测试数据。每组数据你需要输出最后的方案数除以$100000007$的余数。

Sample Input

Sample Output

1
2
3

2
4
3

解释：

第一组数据的方案是：$MMM$，$MMW$ ($M$是男孩, $W$是女孩)。
第二组数据的方案是：$MMM$，$MMW$，$MWW$，$WWW$。
第三组数据的方案是：$MMMM$, $MMMW$, $MWMW$。

约束和限制：

对于20%的数据$T <= 20$;
对于100%的数据$T <= 50$;
对于20%的数据$N,K <= 20$;
对于100%的数据$N,K < = 2000$;

题解

这又是一道$Burnside$的题目
首先这是一个环的旋转
对于每一个$N$，$K$ 都 $DP$ 一发算出$f[i][j]$表示$i$个人最后$j$个为女生,且合法的的方案数
然后枚举$gcd$的值x，这个值为循环节个数，这是可能的旋转次数为$\phi{(\frac{n}{i})}$
对于这个循环节个数，我们枚举他前后的女生数目的和
对于中间不是女生的我们强制第一个和最后一个为男生，乘上$DP$出的值
在乘上因为前后数目不同而形成的不同方案
就算完了一个

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
const int MOD = 100000007;
int phi[2005], prime[2005], cnt;
bool isnprime[2005];
void Get_phi()
{
    isnprime[1] = 1;
    for (int i = 2; i <= 2000; i++)
    {
        if (!isnprime[i]) prime[++cnt] = i, phi[i] = i - 1;
        for (int j = 1; j <= cnt; j++)
        {
            if (i * prime[j] > 2000) break;
            isnprime[i * prime[j]] = 1;
            if (i % prime[j] == 0)
            {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
            phi[i * prime[j]] = phi[i] * phi[prime[j]];
        }
    }
    phi[1] = 1;
}
long long DP[2005][2005];
int n, k;
long long Calc(int x)
{
    int m = min(x, k);
    long long ans = 0;
    for (int i = 0; i <= m; i++)
    {
        if (i != x) ans = (ans + DP[x - i - 1][0] * (i + 1) % MOD) % MOD;
        if (i == x && n <= k) ans = (ans + 1) % MOD;
    }
    return ans;
}
long long pow_mod(long long a, int b)
{
    long long ans = 1;
    while (b)
    {
        if (b & 1) ans = ans * a % MOD;
        b >>= 1;
        a = a * a % MOD;
    }
    return ans;
}
int main()
{
    Get_phi();
    int T = read();
    while (T--)
    {
        n = read(), k = read();
        memset (DP, 0, sizeof (DP));
        DP[0][0] = 1;
        for (int i = 0; i < n; i++)
            for (int j = 0; j <= k; j++)
            {
                if (j < k) (DP[i + 1][j + 1] += DP[i][j]) %= MOD;
                (DP[i + 1][0] += DP[i][j]) %= MOD;
            }
        long long ans = 0;
        for (int i = 1; i * i <= n; i++)
            if (n % i == 0)
            {
                ans = (ans + Calc(i) * phi[n / i] % MOD) % MOD;
                if (i * i != n) ans = (ans + Calc(n / i) * phi[i] % MOD) % MOD;
            }
        printf ("%d\n", ans * pow_mod(n, MOD - 2) % MOD);
    }
}