被 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;
}
0 条评论