AOJ 2164 Revenge of the Round Table 题解《挑战程序设计竞赛》-码农场

4.1更加复杂的数学问题
计数
以B开头
以A开头
Reference

挑战程序设计竞赛

AOJ 2164 Revenge of the Round Table

圆桌基情：有男女共n人入座一个圆桌，若连续k个以上同性坐在一起就会搞基。求不搞基的坐法种数？

4.1更加复杂的数学问题

计数

大的思路还是Burnside引理,难点在于怎么计算染色种数。

在循环节长度i和k固定的时候，循环节的个数应该是gcd(i,n)。下面考虑循环节个数为i时的方案数dp[i]。

记男为A，女为B，定义：

dp_a[MAX_N][MAX_N],            // dp_a[i][j]表示以A开头，长度为i，结尾为j个A的合法方案数
dp_b[MAX_N][MAX_N],            // dp_b[i][j]表示以B开头，长度为i，结尾为j个A的合法方案数

这两种串的dp递推是很简单的，递推a的时候就用b的前缀和作为dp_a[i][1]，因为在以B开头的串前面放一个A就是以A开头的串了。同理递推B。

下面就看这两种串如何组合以满足dp[i]。

以B开头

对于所有的dp_b[i][1~k]都是满足dp[i]，因为首尾不同，将任意两个串组合后不会超出k。

以A开头

假设串前面有p个A，那么结尾的A不能超过k-p个，即dp_b[i-p][0~k-p]都是合法的，这恰好是一个dp_b的前缀和。

最后一个Burnside引理就能求出来，在实现的时候，发现了一个线性求逆元的方法：

线性求所有逆元的方法.png

可以用来高效地求Burnside引理的分子除以分母对MOD的模，于是有如下代码：

#include <iostream>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
#define MAX_N 1000 + 16
#define MOD 1000003
typedef long long LL;
int
        dp_a[MAX_N][MAX_N],         // dp_a[i][j]表示以A开头，长度为i，结尾为j个A的合法方案数
        dp_b[MAX_N][MAX_N],         // dp_b[i][j]表示以B开头，长度为i，结尾为j个A的合法方案数
        dp[MAX_N];                  // dp[i]表示有i个循环节时的染色方案数
int n, k;
LL ans, all;
LL inv[MAX_N];
 
// 线性求乘法逆元 a×b ≡ 1 (mod m)
void init_inverse()
{
    inv[1] = 1;
    for (int i = 2; i < MAX_N; i++)
        inv[i] = (MOD - (MOD / i) * inv[MOD % i] % MOD) % MOD;
}
 
void solve()
{
    memset(dp_a, 0, sizeof(dp_a));
    memset(dp_b, 0, sizeof(dp_b));
    memset(dp, 0, sizeof(dp));
    int a_sum = 1, b_sum = 0;
    if (k >= n)
    {
        k = n - 1;
        all = 2;
    }
    dp_a[1][1] = 1;
    dp_b[1][1] = 0;
 
    for (int i = 2; i <= n; i++)
    {
        dp_a[i][1] = b_sum; // 以B开头以A结尾的串开头放一个A
        dp_b[i][1] = a_sum; // 以A开头以A结尾的串开头放一个B
        swap(a_sum, b_sum);
        for (int j = 2; j <= k; j++)
        {
            dp_a[i][j] = dp_a[i - 1][j - 1];        // 在结尾加上A
            a_sum = (a_sum + dp_a[i][j]) % MOD;
            dp_b[i][j] = dp_b[i - 1][j - 1];        // 在结尾加上B
            b_sum = (b_sum + dp_b[i][j]) % MOD;
        }
    }
 
    // 对于所有的dp_b[i][1~k]都是满足dp[i]，因为首尾不同，将任意两个串组合后不会超出k
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= k; j++)
        {
            dp[i] += dp_b[i][j];
            dp[i] %= MOD;
        }
    }
 
    // 对于以A开头的串，先将dp_b前缀和求出来
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j < k; j++)
        {
            dp_b[i][j + 1] += dp_b[i][j];
            dp_b[i][j + 1] %= MOD;
        }
    }
 
    // 考虑前面有p个A，那么结尾的A不能超过k-p个，即dp_b[i-p][0~k-p]都是合法的
    for (int i = 1; i <= n; i++)
    {
        for (int p = 1; p <= min(i, k); p++)
        {
            dp[i] += dp_b[i - p][k - p];
            dp[i] %= MOD;
        }
    }
}
 
int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a % b);
}
 
///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    init_inverse();
    while (~scanf("%d%d", &n, &k))// for AOJ use while (scanf("%d%d", &n, &k) , n)
    {
        ans = 0, all = 0;
        solve();
        for (int i = 0; i < n; i++)
        {
            ans += 2 * dp[gcd(i, n)];   // 交换AB
            ans %= MOD;
        }
        ans = ans * inv[n] % MOD;
        printf("%lld\n", (ans + all) % MOD);
    }
#ifndef ONLINE_JUDGE
    fclose(stdin);
    fclose(stdout);
    system("out.txt");
#endif
    return 0;
}
///////////////////////////End Sub//////////////////////////////////
 
/**************************************************************
    Problem: 1436
    User: hankcs
    Language: C++
    Result: Accepted
    Time:76 ms
    Memory:9560 kb
****************************************************************/

我提交的时候恰逢AOJ宕机，所以提交到了CSUOJ上，后者对输入的处理有所不同，敬请注意。