#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));
}


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));
}


？？？？？

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

#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.