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#

解释：#

第一组数据的方案是： $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$ 出的值
在乘上因为前后数目不同而形成的不同方案
就算完了一个

1
#include <cstdio>
2
#include <cstring>
3
#include <algorithm>
4
using namespace std;
5
inline int read()
6
{
7
    int x=0,f=1;char ch=getchar();
8
    while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
9
    while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
10
    return x*f;
11
}
12
const int MOD = 100000007;
13
int phi[2005], prime[2005], cnt;
14
bool isnprime[2005];
15
void Get_phi()
16
{
17
    isnprime[1] = 1;
18
    for (int i = 2; i <= 2000; i++)
19
    {
20
        if (!isnprime[i]) prime[++cnt] = i, phi[i] = i - 1;
21
        for (int j = 1; j <= cnt; j++)
22
        {
23
            if (i * prime[j] > 2000) break;
24
            isnprime[i * prime[j]] = 1;
25
            if (i % prime[j] == 0)
26
            {
27
                phi[i * prime[j]] = phi[i] * prime[j];
28
                break;
29
            }
30
            phi[i * prime[j]] = phi[i] * phi[prime[j]];
31
        }
32
    }
33
    phi[1] = 1;
34
}
35
long long DP[2005][2005];
36
int n, k;
37
long long Calc(int x)
38
{
39
    int m = min(x, k);
40
    long long ans = 0;
41
    for (int i = 0; i <= m; i++)
42
    {
43
        if (i != x) ans = (ans + DP[x - i - 1][0] * (i + 1) % MOD) % MOD;
44
        if (i == x && n <= k) ans = (ans + 1) % MOD;
45
    }
46
    return ans;
47
}
48
long long pow_mod(long long a, int b)
49
{
50
    long long ans = 1;
51
    while (b)
52
    {
53
        if (b & 1) ans = ans * a % MOD;
54
        b >>= 1;
55
        a = a * a % MOD;
56
    }
57
    return ans;
58
}
59
int main()
60
{
61
    Get_phi();
62
    int T = read();
63
    while (T--)
64
    {
65
        n = read(), k = read();
66
        memset (DP, 0, sizeof (DP));
67
        DP[0][0] = 1;
68
        for (int i = 0; i < n; i++)
69
            for (int j = 0; j <= k; j++)
70
            {
71
                if (j < k) (DP[i + 1][j + 1] += DP[i][j]) %= MOD;
72
                (DP[i + 1][0] += DP[i][j]) %= MOD;
73
            }
74
        long long ans = 0;
75
        for (int i = 1; i * i <= n; i++)
76
            if (n % i == 0)
77
            {
78
                ans = (ans + Calc(i) * phi[n / i] % MOD) % MOD;
79
                if (i * i != n) ans = (ans + Calc(n / i) * phi[i] % MOD) % MOD;
80
            }
81
        printf ("%d\n", ans * pow_mod(n, MOD - 2) % MOD);
82
    }
83
}