放牧代码和思想
专注自然语言处理、机器学习算法
    This thing called love. Know I would've. Thrown it all away. Wouldn't hesitate.

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

目录

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引理就能求出来,在实现的时候,发现了一个线性求逆元的方法:

可以用来高效地求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上,后者对输入的处理有所不同,敬请注意。

Reference

http://blog.csdn.net/u013625492/article/details/46787157

[数论]线性求所有逆元的方法

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » AOJ 2164 Revenge of the Round Table 题解《挑战程序设计竞赛》

评论 3

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. #2

    这个MOD改用n*1000003就可以了,正好不会溢出,最后结果再%1000003,就OK了

    oklen6年前 (2019-05-31)回复
  2. #1

    请问Hanlp训练分词模型的语料格式为什么是分好词的?就是单纯的一文章行吗?

    宽待9年前 (2015-09-22)回复

我的作品

HanLP自然语言处理包《自然语言处理入门》