NekoMio's Blog

美しいものが起こることを常に信じている

  1. 1. Description
  2. 2. Input
  3. 3. Output
  4. 4. Sample Input
  5. 5. Sample Output
    1. 5.0.1. 解释:
    2. 5.0.2. 约束和限制:
  • 题解
  • Description

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

    Input

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

    Output

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

    Sample Input

    1
    2
    3
    4
    3
    3 1
    3 3
    4 1

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

    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
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    #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);
    }
    }

    本文作者 : NekoMio
    知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
    本文链接 : https://www.nekomio.com/2018/03/06/134/

    本文最后更新于 天前,文中所描述的信息可能已发生改变