第⑨次考试会变成baka
起床就感觉喉咙好痛，来了机房直接GG，摸了下腋下感觉药丸。
昏了头考试，崩的有点厉害（
本次考试题目顺序的设置充满恶意。。。
我一看提示原根就弃了，写了个\(O(nmmod)\)的暴力，结果一个点都没跑过。。。。
首先这是个假期望题，总方案数为\(n^m\)，求出所有情况之和就可以了
设f[i][j]为i次操作x值为j的次数，暴力转移一波。写出方程还能发现是矩阵乘法的形式，这部分就不说了，直接看正解，毕竟我考试连这几个都没写。
题目提示我们用原根， 我们就用原根。用原根的幂就可以在p-1次方内遍历整个剩余系，我们可以用原根的幂的形式代替原来的a数组。
这样，原来的\(a_i * a_j * a_k\)的形式就变成了\(g^i * g ^j * g ^ k = g ^ {i + j + k}\)，乘法变成了加法。
我们把原来的f变一下，表示i次操作变成原根的j次方的次数。
/*
______ ______
/ \ / \
| | | | | |
| | | | | |
| | | /\ | | |
\______/ \__/ \__/ \______/
*/
#include <bits/stdc++.h>
#define ll long long
const int MO = 1000000007, N = 100005;
int n, m, p, rt;
ll po[N], idx[N], a[N];
struct Matrix {
ll a[1005];
friend Matrix operator *(Matrix x, Matrix y) {
Matrix z = {};
for (int i = 0; i <= p - 1; i++)
for (int j = 0; j <= p - 1; j++)
z.a[(i + j) % (p - 1)] = (z.a[(i + j) % (p - 1)] + x.a[i] * y.a[j]) % MO;
return z;
}
inline void clear() {
for (int i = 0; i <= p - 1; i++) a[i] = 0;
}
Matrix qpow(int b) {
Matrix tmp, x = (*this);
tmp.clear(), tmp.a[idx[1]]++;
for (; b; b >>= 1, x = x * x)
if (b & 1) tmp = tmp * x;
return tmp;
}
} mtx, ans;
ll qpow(ll x, ll b, ll p) {
ll tmp = 1;
for (; b; b >>= 1, x = x * x % p)
if (b & 1) tmp = tmp * x % p;
return tmp;
}
inline int getrt(int x) {
for (int i = 2; i <= x; i++) {
ll tmp = 1; bool flg = 1;
for (int j = 1; j <= x - 2; j++) {
tmp = tmp * i % x;
if (tmp == 1) {
flg = 0;
break;
}
}
if (flg) return i;
}
}
signed main() {
scanf("%d%d%d", &n, &m, &p);
rt = getrt(p); po[0] = 1;
for (int i = 1; i <= p - 2; i++)
po[i] = po[i - 1] * (ll) rt % p, idx[po[i]] = i;
for (int i = 1; i <= n; i++)
scanf("%lld", &a[i]), mtx.a[idx[a[i]]]++;
ans = mtx.qpow(m);
ll tot = 0;
for (int i = 0; i <= p - 2; i++)
tot = (tot + po[i] * ans.a[i]) % MO;
ll inv = qpow(n, (ll) m * (MO - 2), MO);
printf("%lld\n", tot * inv % MO);
return 0;
}咕
T3最可做，wsl
科学开题顺序：C -> B -> A（
这个事情告诉我们要先把所有题看一遍，谁告诉你题目就一定要按照难度升序排列了（
题中还有坑，subtask 0,1,3都是白给75分，然而我被卡在2一直没看3。。。。
讲解按难度升序排列，不像出题人那么屑。
subtask 0:
枚举水平向右步数a，垂直向上步数c。答案为\(C_n^a C_{n - a} ^ a C_{n - 2a} ^ c = \frac{n!}{a! a! c! c!}\).
预处理阶乘和阶乘逆元，完事
subtask 1:
设向右步数a，向左步数b，这就像出入栈问题，必须保持 a >= b.所以答案就是Cat[n / 2].
subtask 3:
就是subtask 0和1合了起来，枚举水平向右步数a，可算出向上步数c，相当于在x轴和y轴都做一边subtask1。
答案就是\(C_n^{2a} Cat[a] Cat[c]\).
subtask 2:
这问组合计数不能，我在考场上疯狂尝试容斥，结果容不出来。
其实就是一个很简单的DP。设f[i]为第i步回到原点的方案数，枚举第一次回到原点的步数j，它满足subtask 1。\(f[i] = f[i - j] Cat[j / 2 - 1] * 4\).
解释细节：Cat为什么下标要减1？j步内是不能回到原点的，可以类比出入栈，我们不能让栈为空。×4就是4个方向。
看完题再开题！！！
看完题再开题！！！
/*
______ ______
/ \ / \
| | | | | |
| | | | | |
| | | /\ | | |
\______/ \__/ \__/ \______/
*/
#include <bits/stdc++.h>
#define ll long long
const int MO = 1000000007, N = 1000000 + 233;
int n, typ;
ll ans, fac[N], inv[N], cat[N];
ll Qpow(ll x, int b) {
ll ret = 1;
for (; b; b >>= 1, x = x * x % MO)
if (b & 1) ret = ret * x % MO;
return ret;
}
void init(int t) {
fac[0] = fac[1] = 1, cat[1] = 1, cat[0] = 1;
for (int i = 2; i <= t; i++) fac[i] = fac[i - 1] * i % MO;
for (int i = 0; i <= t; i++) inv[i] = Qpow(fac[i], MO - 2);
for (int i = 2; i <= t; i++) cat[i] = (cat[i - 1] * (4 * i - 2) % MO * Qpow(i + 1, MO - 2) % MO) % MO;
}
namespace case0 {
void QAQ() {
init(n);
for (int i = 0; i <= n; i += 2) {
int a = i / 2, c = (n - i) / 2;
ans = (ans + fac[n] * inv[a] % MO * inv[a] % MO * inv[c] % MO * inv[c] % MO) % MO;
}
printf("%lld\n", ans);
}
}
namespace case1 {
void QAQ() {
init(n);
printf("%lld\n", cat[n / 2]);
}
}
namespace case2 {
ll f[N];
void QAQ() {
init(n), n /= 2;
f[0] = 1, f[1] = 4;
for (int i = 2; i <= n; i++)
for (int j = 1; j <= i; j++)
f[i] = (f[i] + 4 * f[i - j] % MO * cat[j - 1]) % MO;
printf("%lld\n", f[n]% MO);
}
}
namespace case3 {
void QAQ() {
init(n);
for (int i = 0; i <= n; i += 2) {
int a = i / 2, c = (n - i) / 2;
ans = (ans + fac[n] * inv[i] % MO * inv[n - i] % MO * cat[a] % MO * cat[c] % MO) % MO;
}
printf("%lld\n", ans);
}
}
signed main() {
scanf("%d%d", &n, &typ);
if (typ == 0) case0::QAQ();
if (typ == 1) case1::QAQ();
if (typ == 2) case2::QAQ();
if (typ == 3) case3::QAQ();
return 0;
}原文：https://www.cnblogs.com/gekoo/p/11256664.html