武汉工程大学第三届ACM程序设计新生赛（多校联赛）（线上赛）（正式赛）题解

前七题的题解：https://blog.csdn.net/qq_46144509/article/details/109905618?utm_source=app

C. Pokémon Go

选择每一个出口对所有的点进行bfs,然后取最小值。
如果不知道bfs，建议先学一下bfs模板题。
搬运删去部分后风竹曦的代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef pair<int, int> PII;

#define rep(i, a, n) for (int i = a; i <= n; i++)

const ll mod = (ll)1e9 + 7;
const int INF = 0x3f3f3f3f;
const int N = (int)1e3 + 10;
const int DIR[4][2] = {
   {
   1, 0}, {
   0, 1}, {
   0, -1}, {
   -1, 0}};
int a[N][N], dis[N][N], vis[N][N];
int n, m, flag = 0;
struct Node {
   
    int x, y, step;
};
void bfs(int x, int y);
inline bool check(int x, int y) {
    return x >= 1 && x <= n && y >= 1 && y <= m; }

int main() {
   
    int k;
    cin >> n >> m >> k;
    rep(i, 1, k) {
   
        int x, y;
        scanf("%d%d", &x, &y);
        a[x][y] = 1;
    }
    memset(dis, 0x3f, sizeof dis);
    int t;
    cin >> t;
    rep(i, 1, t) {
   
        int x, y;
        scanf("%d%d", &x, &y);
        bfs(x, y);
    }

    int p;
    cin >> p;
    rep(i, 1, p) {
   
        int x, y;
        scanf("%d%d", &x, &y);
        int ans = dis[x][y];
        if (ans >= INF) {
   
            ans = -1;
        }
        printf("%d\n", ans);
    }

    return 0;
}

void bfs(int x, int y) {
   
    flag++;
    queue<Node> q;
    q.push({
   x, y, 0});
    vis[x][y] = flag;
    while (!q.empty()) {
   
        Node f = q.front();
        q.pop();
        dis[f.x][f.y] = min(dis[f.x][f.y], f.step);
        rep(d, 0, 3) {
   
            int x0 = f.x + DIR[d][0], y0 = f.y + DIR[d][1];
            if (check(x0, y0) && a[x0][y0] == 0 && vis[x0][y0] != flag) {
   
                q.push({
   x0, y0, f.step + 1});
                vis[x0][y0] = flag;
            }
        }
    }
}

B. 跳棋

dfs题。如果直接全排列，12!，会超时。
所以需要剪枝。
经过12打表可以发现，棋盘处于“超平衡状态”的时候，每一条直线的和为 $\frac{1+12}{2}*4=26$ (平均值乘以棋子数)。

从序号1开始递归，递归到第6层时检测，a[2],a[3],a[4],a[5]的和不等于26就return

	if (step == 6) {
   
		if (a[2] + a[3] + a[4] + a[5] != 26) {
   
			return;
		}
	}

递归到第9层时检测，a[1],a[3],a[6],a[8]的和不等于26就return

	if (step == 9) {
   
		if (a[1] + a[3] + a[6] + a[8] != 26) {
   
			return;
		}
	}

然后12层的时候再检测一次

	if (step == 12) {
   
		if (a[8] + a[9] + a[10] + a[11] != 26) {
   
			return;
		}

		if (a[1] + a[4] + a[7] + a[11] != 26) {
   
			return;
		} 
	}

如果是红色棋盘就直接递归下一层

	if (step == 1 || step == 9) {
   
		dfs(step + 1);
		return;
	}

到第13层时

	if (step == 13) {
   
		if (a[2] + a[6] + a[9] + a[12] != 26) {
   
			return;
		}

		if (a[5] + a[7] + a[10] + a[12] != 26) {
   
			return;
		}

		/* 存储或者输出 */
		return;
	}

然后，如果直接每次询问都进行一次dfs，再输出，这个代码还是会超时。先把所有的从12个数中选2个不同的数的全排列写出来，

void init() {
   
	for (n1 = 1; n1 <= 12; n1++) {
   
		for (n2 = 1; n2 <= 12; n2++) {
   
			if (n2 != n1) {
   
				memset(vis, 0, sizeof(vis));
				a[1] = n1;
				a[9] = n2;
				vis[n1] = vis[n2] = true;

				dfs(1);
			}
		}
	}
}

然后再用一个二维数组dp[13][13]记忆每一种排列的情况。dp里面是一个二维数组，存储该排列情况的所有字典序数组。所以这是一个四维数组。

struct save {
   
	std::vector<std::vector<int> > v;
};

save dp[13][13];

完整代码就是：

# include <iostream>
# include <cstdio>
# include <cstring>
# include <vector>

int a[13];
bool vis[13];

int n1, n2;

struct save {
   
	std::vector<std::vector<int> > v;
};

save dp[13][13];

void dfs(int step) {
   
	if (step == 13) {
   
		if (a[2] + a[6] + a[9] + a[12] != 26) {
   
			return;
		}

		if (a[5] + a[7] + a[10] + a[12] != 26) {
   
			return;
		}

		std::vector<int> vp;
		for (int i = 1; i <= 12; i++) {
   
			vp.push_back(a[i]);
		}
		dp[n1][n2].v.push_back(vp);
		return;
	}

	if (step == 6) {
   
		if (a[2] + a[3] + a[4] + a[5] != 26) {
   
			return;
		}
	}

	if (step == 9) {
   
		if (a[1] + a[3] + a[6] + a[8] != 26) {
   
			return;
		}
	}

	if (step == 12) {
   
		if (a[8] + a[9] + a[10] + a[11] != 26) {
   
			return;
		}

		if (a[1] + a[4] + a[7] + a[11] != 26) {
   
			return;
		} 
	}

	if (step == 1 || step == 9) {
   
		dfs(step + 1);
		return;
	}


	for (int i = 1; i <= 12; i++) {
   
		if (!vis[i]) {
   
			vis[i] = true;
			a[step] = i;
			dfs(step + 1);

			vis[i] = false;
		}
	}
}

void solve() {
   
	if (dp[n1][n2].v.size() == 0) {
   
		puts("-1");
	} else {
   
		for (int i = 0; i < dp[n1][n2].v.size(); i++) {
   
			for (int j = 0; j < dp[n1][n2].v[i].size(); j++) {
   
				printf("%d ", dp[n1][n2].v[i][j]);
			}
			puts("");
		}
	}

	puts("");
}

void init() {
   
	for (n1 = 1; n1 <= 12; n1++) {
   
		for (n2 = 1; n2 <= 12; n2++) {
   
			if (n2 != n1) {
   
				memset(vis, 0, sizeof(vis));
				a[1] = n1;
				a[9] = n2;
				vis[n1] = vis[n2] = true;

				dfs(1);
			}
		}
	}
}

int main() {
   
	init();
	while (~scanf("%d%d", &n1, &n2)) {
   
		solve();
	}

	return 0;
}

此题解的数组维度有点高，并且vector和普通数组混用，因此看懂有点难度。

但似乎有大佬没有记忆化，并且和我的思路差不多，也过了？~~难道字符串比数组处理要快？~~
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=45659756

~~本以为超过10000字符的代码牛客不允许提交，结果后来发现可以。暴力打表。~~
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=45655689
一千多行代码怎么敲？先把打表的数据输出到txt，然后复制txt里面的内容，粘贴到代码上。
本来一开始我想出事先放三个棋子的，后来想降低难度就只出了放两个棋子的。不知道如果是放三个棋子，打表会不会超过牛客规定的提交代码大小上限。

J. 魔改斐波那契

$\begin{pmatrix} f_{n+1} & f_{n} & 0 \\ f_{n} & f_{n-1} & 0 \\ c & c & 0 \end{pmatrix} = \begin{pmatrix} a & b & 1 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix} * \begin{pmatrix} f_{n} & f_{n-1} & 0 \\ f_{n-1} & f_{n-2} & 0 \\ c & c & 0 \end{pmatrix} =...$

$\begin{pmatrix} a & b & 1 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix}}^n * \begin{pmatrix} f_{1} & f_{0} & 0 \\ f_{0} & f_{-1} & 0 \\ c & c & 0 \end{pmatrix}$
~~如果没有计算 $f_{-1}$ 可以允许出现 $f_{-1}$ 。个人观点，如有不对请指正。~~

如果先将十进制转为二进制再矩阵快速幂可能会超时。所以用10进制的矩阵快速幂。 $I$ 是单位矩阵。

Node decpow(Node x) {
   
	int len = strlen(s + 1);

	Node base = x;
	Node ans = I;
	for (int i = len; i; i--) {
   
		ans  = ans * qpow(base, s[i] - '0');
		base = qpow(base, 10);
	}

	return ans;
}

代码整体就是：

# include <iostream>
# include <cstring>
# include <cstdio>

int mod;
const int N = 1e6 + 5;
char s[N];

struct Node {
   
	int a[3][3];

	Node operator * (const Node& rhs) {
   
		Node t = {
   0};
		for (int i = 0; i < 3; i++) {
   
			for (int j = 0; j < 3; j++) {
   
				for (int k = 0; k < 3; k++) {
   
					t.a[i][j] += 1ll * a[i][k] * rhs.a[k][j] % mod;

					if (t.a[i][j] >= mod) {
   
						t.a[i][j] -= mod;
					}
				}
			}
		}
		
		return t;
	}
};

const Node I = {
   1, 0, 0, 0, 1, 0, 0, 0, 1};

Node qpow(Node x, int p) {
   
	Node ans = I;
	while (p) {
   
		if (p & 1) {
   
			ans = ans * x;
		}

		x = x * x;
		p >>= 1;
	}

	return ans;
}

Node decpow(Node x) {
   
	int len = strlen(s + 1);

	Node base = x;
	Node ans = I;
	for (int i = len; i; i--) {
   
		ans  = ans * qpow(base, s[i] - '0');
		base = qpow(base, 10);
	}

	return ans;
}

int main() {
   
	int x0;
	int x1;
	int a;
	int b;

	scanf("%d%d%d%d%s%d", &a, &b, &x0, &x1, s + 1, &mod);

	Node T = {
   a, b, 1, 1, 0, 0, 0, 0, 1};
	Node ans = decpow(T);
	int res = ((1ll * ans.a[1][0] * x1 % mod + 1ll * ans.a[1][1] * x0 % mod) % mod + 1ll * ans.a[1][2] * 7 % mod) % mod;
	printf("%d\n", res);

	return 0;
}

方法二：斐波那契循环节。
斐波那契数列的模数每隔一段就会重复原来的序列，这个性质被称为皮萨诺周期。“每隔一段”的长度被称为循环节。
下面的代码求的循环节不一定是最小循环节，但也可以作为模数。~~别问我这代码的原理是什么，我是找的别人的代码~~

ll lcm(ll a, ll b) {
   
    return a / std::__gcd(a, b) * b;
}
 
ll pFac[105][2];
int getFactors(ll n) {
   
    int pCnt = 0;
    for (ll i = 2; i * i <= n; ++i) {
   
        if (n % i) {
   
            continue;
        }
 
        pFac[pCnt][0] = i;
        pFac[pCnt][1] = 0;
        while (n % i == 0) {
   
            n /= i;
            pFac[pCnt][1]++;
        }
 
        pCnt++;
    }
 
    if (n > 1) {
   
        pFac[pCnt][0] = n;
        pFac[pCnt++][1] = 1;
    }
 
    return pCnt;
}

int Legendre(ll a, ll p) {
   
    if (qpow(a, (p - 1) >> 1, p) == 1) {
   
        return 1;
    }
 
    return -1;
}
 
ll find_loop(ll n, ll a = 1, ll b = 1) {
   
    int cnt = getFactors(n);
    ll c = a * a + b * 4;
    ll ans = 1, record;
 
    for (int i = 0; i < cnt; ++i) {
   
        if (pFac[i][0] == 2) {
   
            record = 3 * 2 * 2;
        } else if (c % pFac[i][0] == 0) {
   
            record = pFac[i][0] * (pFac[i][0] - 1);
        } else if (Legendre(c, pFac[i][0]) == 1) {
   
            record = pFac[i][0] - 1;
        } else {
   
            record = (pFac[i][0] - 1) * (pFac[i][0] + 1);
        }
 
        for (int j = 1; j < pFac[i][1]; ++j) {
   
            record *= pFac[i][0];
        }
 
        ans = lcm(ans, record);
    }
 
    return ans;
}

int main() {
   
	ll p = find_loop(mod, a, b);
	return 0;
}

然后再对大数求模

ll read_mod(ll mod) {
   
	int len = strlen(s + 1);
	ll n = 0;

	for (int i = 1; i <= len; i++) {
   
		n = ksc(n, 10, mod) + s[i] - '0';
		if (n >= mod) {
   
			n -= mod;
		}
	}

	return n;
}

完整版就是：

# include <iostream>
# include <algorithm>
# include <cstdio>
# include <cstring>

typedef long long ll;
typedef __int128 lll;

const int N = 5e5 + 5;
char s[N];
ll mod;

struct Node {
   
	ll m[3][3];

	Node operator * (const Node& rhs) {
   
		Node t = {
   0};
		for (int i = 0; i < 3; i++) {
   
			for (int j = 0; j < 3; j++) {
   
				for (int k = 0; k < 3; k++) {
   
					t.m[i][j] += m[i][k] * rhs.m[k][j] % mod;

					if (t.m[i][j] >= mod) {
   
						t.m[i][j] -= mod;
					}
				}
			}
		}

		return t;
	}

};

const Node I = {
   1, 0, 0, 0, 1, 0, 0, 0, 1};

Node qpow(Node x, ll p) {
   
	Node ans = I;
	while (p) {
   
		if (p & 1) {
   
			ans = ans * x;
		}

		x = x * x;
		p >>= 1;
	}

	return ans;
}

ll qpow(ll x, ll p, int Mod = mod) {
   
	ll ans = 1 % Mod;
	x %= Mod;
	while (p) {
   
		if (p & 1) {
   
			ans = ans * x % Mod;
		}

		x = x * x % Mod;
		p >>= 1;
	}

	return ans;
}

ll lcm(ll a, ll b) {
   
    return a / std::__gcd(a, b) * b;
}
 
ll pFac[105][2];
int getFactors(ll n) {
   
    int pCnt = 0;
    for (ll i = 2; i * i <= n; ++i) {
   
        if (n % i) {
   
            continue;
        }
 
        pFac[pCnt][0] = i;
        pFac[pCnt][1] = 0;
        while (n % i == 0) {
   
            n /= i;
            pFac[pCnt][1]++;
        }
 
        pCnt++;
    }
 
    if (n > 1) {
   
        pFac[pCnt][0] = n;
        pFac[pCnt++][1] = 1;
    }
 
    return pCnt;
}

int Legendre(ll a, ll p) {
   
    if (qpow(a, (p - 1) >> 1, p) == 1) {
   
        return 1;
    }
 
    return -1;
}
 
ll find_loop(ll n, ll a = 1, ll b = 1) {
   
    int cnt = getFactors(n);
    ll c = a * a + b * 4;
    ll ans = 1, record;
 
    for (int i = 0; i < cnt; ++i) {
   
        if (pFac[i][0] == 2) {
   
            record = 3 * 2 * 2;
        } else if (c % pFac[i][0] == 0) {
   
            record = pFac[i][0] * (pFac[i][0] - 1);
        } else if (Legendre(c, pFac[i][0]) == 1) {
   
            record = pFac[i][0] - 1;
        } else {
   
            record = (pFac[i][0] - 1) * (pFac[i][0] + 1);
        }
 
        for (int j = 1; j < pFac[i][1]; ++j) {
   
            record *= pFac[i][0];
        }
 
        ans = lcm(ans, record);
    }
 
    return ans;
}

inline ll ksc(ll x, ll y, ll mod) {
   
	x %= mod;
	y %= mod;

	return (lll)x * y % mod;
// ll tmp = x * y - (ll)((long double)x / mod * y + 1.0e-8) * mod;
// return tmp < 0 ? tmp + mod : tmp > mod ? tmp -= mod : tmp;
}

ll read_mod(ll mod) {
   
	int len = strlen(s + 1);
	ll n = 0;

	for (int i = 1; i <= len; i++) {
   
		n = ksc(n, 10, mod) + s[i] - '0';
		if (n >= mod) {
   
			n -= mod;
		}
	}

	return n;
}

int main() {
   
	int a;
	int b;
	int f0;
	int f1;
	scanf("%d%d%d%d%s%lld", &a, &b, &f0, &f1, s + 1, &mod);

	if (mod == 1) {
   
		std::cout << 0;
		return 0;
	}

	ll p = find_loop(mod, a, b);
	ll n = read_mod(p);

	Node T = {
   a, b, 1, 1, 0, 0, 0, 0, 1};
	Node ans = qpow(T, n);

	int res = (ans.m[1][0] * f1 % mod + ans.m[1][1] * f0 % mod + ans.m[1][2] * 7 % mod) % mod;
	std::cout << res;

	return 0;
}

对于本校学生，我们来回顾一下劝退课程之《ACM第四次课20201107》的最后一张PPT：

其中的三个链接：
https://ac.nowcoder.com/acm/contest/885/B
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=45482960
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=45482976
发现没有？就是多加了一个7而已。论课后习题的重要性。