题目链接

被 POJ 大秀了一回

矩阵乘法一开始我是这么写的:

#define pls(a, b) ((a) + (b) < MOD ? (a) + (b) : (a) + (b) - MOD)
#define mul(a, b) ((a) * (b) % MOD)

void M_mul(int (&a)[MS][MS], int (&b)[MS][MS])
{
    static int tmp[MS][MS];
    memset(tmp, 0, sizeof(tmp));
    for (register int k = 1; k <= m; k += 1)
        for (register int i = 1; i <= m; i += 1)
            for (register int j = 1; j <= m; j += 1)
                tmp[i][j] = pls(tmp[i][j], mul(a[i][k], b[k][j]));
    memmove(a, tmp, sizeof(a));
}

于是 2000MS 都过不了

调啊改啊搞了一个小时,最后把矩阵乘法改成这样:

void M_mul(int (&a)[MS][MS], int (&b)[MS][MS])
{
    static int tmp[MS][MS];
    memset(tmp, 0, sizeof(tmp));
    for (register int k = 1; k <= m; k += 1)
        for (register int i = 1; i <= m; i += 1)
            for (register int j = 1; j <= m; j += 1)
                tmp[i][j] += a[i][k] * b[k][j];
    for (register int i = 1; i <= m; i += 1)
        for (register int j = 1; j <= m; j += 1)
            tmp[i][j] %= MOD;
    memmove(a, tmp, sizeof(a));
}

就 800MS AC 了

?????

太秀了吧?翻了一倍都不止啊?

另外在 POJ 上我从来没有 1A 过任何一道题,第一次提交绝对 CE,POJ 编译器比 CCF 的都老

彳亍口巴,还是讲正事吧

假设没有 $k$对限制那就是 polya 定理裸题

既然有这个限制那就用 Burnside 嘛,反正是一样的

首先不考虑旋转

设 $f[i][j]$为给一个长度为 $i$的数组填色,最后一位颜色为 $j$,使得相邻两项颜色不违反规定的方案数

则有:

$f[i][j] = \sum f[i – 1][k]$($j$与 $k$可以相邻)

因为第一维很大而第二维很小,所以就矩阵快速幂求咯

求长度为 $i$的数组首尾颜色可以相邻的方案数(在环上当前循环节的末尾与下一个循环节的开头相接),就等于求长度为 $i + 1$且首尾颜色相同的方案数,这个就等于结果矩阵的左上到右下的对角线之和,设这个值为 $g[i]$

接着考虑暴力做法,枚举每次旋转的位数 $x$,设 $gcd(x, n) = l$,则这种变换下不动点的个数就是 $g[l]$

但是暴力枚举会超时,想到不同的 $gcd(x, n)$的值并不会有很多,于是考虑枚举 $gcd(x, n)$的值 $l$

根据欧拉函数 $\varphi $的性质可知,小于等于 $n$且 $gcd(x, n)$等于 $l$的 $x$的个数为 $\varphi (\frac n l)$

因此 $gcd(x, n) = l$的贡献就是 $g[l] \times \varphi (\frac n l)$

具体做法就是在 $[1, \sqrt n]$内枚举 $gcd$的值 $l$,然后把 $gcd(x, n) = l$的贡献和 $gcd(x, n) = \frac n l$的贡献给加上去

求 $\varphi$我直接用的 $O(\sqrt n)$的(偷懒.jpg)

复杂度懒得算了,总之最后 800MS 能过就行啦

#include <cstdio>
#include <cctype>
#include <cstring>

#define MS (11)
#define MOD (9973)
#define pls(a, b) ((a) + (b) < MOD ? (a) + (b) : (a) + (b) - MOD)
#define mul(a, b) ((a) * (b) % MOD)

using namespace std;

template<typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

int T, n, m, k, ans, D[MS][MS], A[MS][MS], R[MS][MS];

void M_mul(int (&a)[MS][MS], int (&b)[MS][MS])
{
    static int tmp[MS][MS];
    memset(tmp, 0, sizeof(tmp));
    for (register int k = 1; k <= m; k += 1)
        for (register int i = 1; i <= m; i += 1)
            for (register int j = 1; j <= m; j += 1)
                tmp[i][j] += a[i][k] * b[k][j];
    for (register int i = 1; i <= m; i += 1)
        for (register int j = 1; j <= m; j += 1)
            tmp[i][j] %= MOD;
    memmove(a, tmp, sizeof(a));
}

void M_pow(int b)
{
    memmove(A, D, sizeof(A)), memset(R, 0, sizeof(R));
    for (int i = 1; i <= m; i += 1) R[i][i] = 1;
    while (b)
    {
        if (b & 1) M_mul(R, A);
        M_mul(A, A), b >>= 1;
    }
}

int Cal(int x)
{
    M_pow(x);
    int res = 0;
    for (int i = 1; i <= m; i += 1) res = pls(res, R[i][i]);
    return res;
}

int Phi(int x)
{
    int res = x;
    for (int i = 2; i * i <= x; i += 1)
        if (x % i == 0)
        {
            res -= res / i;
            while (x % i == 0) x /= i;
        }
    if (x > 1) res -= res / x;
    return res % MOD;
}

int qpow(int a, int b)
{
    a %= MOD;
    int res = 1;
    while (b)
    {
        if (b & 1) res = mul(res, a);
        a = mul(a, a), b >>= 1;
    }
    return res;
}

int main(int argc, char const* argv[])
{
    IN(T);
    while (T--)
    {
        IN(n), IN(m), IN(k), ans = 0;
        for (int i = 1; i <= m; i += 1)
            for (int j = 1; j <= m; j += 1)
                D[i][j] = 1;
        for (int i = 1, a, b; i <= k; i += 1)
            IN(a), IN(b), D[a][b] = D[b][a] = 0;
        for (int i = 1; i * i <= n; i += 1)
            if (n % i == 0)
            {
                ans = pls(ans, mul(Cal(i), Phi(n / i)));
                if (n / i != i) ans = pls(ans, mul(Cal(n / i), Phi(i)));
            }
        printf("%d\n", mul(ans, qpow(n, MOD - 2)));
    }
    return 0;
}
分类: 文章

Remmina

No puzzle that couldn't be solved.

发表评论

电子邮件地址不会被公开。 必填项已用*标注