缩短链接的网站郑州网站优化培训

链接
分析
题目要求我们去求出最优的染色的方法数。首先什么时候是最优的，这里只有两种颜色，不可能取到三条边，即蓝色为B，红色为R，有BBB,RRR,BBR,RRB四种组合，显然最多的就是取两条边，我们想取到所有的最大的两条该如何求组合呢，我们将染色分成2R1B,和2B1R，两者数目相同各占一半就可以了，对于所有的三角形，我们的两种染色方法的分配总共有如下方法.
$(\begin{array}{c}\frac{n}{3}\\ \frac{n}{6}\end{array})$
但是仅仅是这样还是不够的，对于这样的分配方案中，每个具体的三角形的内的染色方案还没有确定，例如如果是等边三角形，那么就可以有三种染色方案，可以保留任意两条边，根据乘法原理，对于每一种上面的三角形2R1B或者2B1R的分配方案，我们三角形内部的具体的排列方案有,我们把内部可以取的方案数记作ci,ci可以取1,2,3,看最小的边有几条
${\prod }_{i=1}^{\frac{n}{3}}{c}_i$
故最终的方法数是
$(\begin{array}{c}\frac{n}{3}\\ \frac{n}{6}\end{array}){\prod }_{i=1}^{\frac{n}{3}}{c}_i$
理论基础
1、乘法逆元：
众所周知，乘法逆元有三种计算方法，扩展欧几里得，费马小定理，还有递推求解。其中费马小定理最简单。对于正整数a,和质数b
$a^{b-1}modb\equiv 1$
这个定理在a,b互质的时候成立，b如果是素数的时候必然成立，由于我们是在乘积运算中得到的，而且所有的运算均mod b所以a必然不可能b，所以是一定成立的。
$a\cdot a^{b-2}modb\equiv 1$
可以知晓，a^b-2是a的在模b的
利用快速幂可以得到逆元，时间复杂度是O(logb)int范围30次左右

ll po(ll rad, ll idx) {ll res = 1;while (idx) {if (idx & 1) res *= id, res %= p;rad *= rad, rad %= p;idx >>= 1; }return res;
}
ll inv(ll x) {return po(x, p - 2);
}

实现

#include <bits/stdc++.h>
#define ll long long
#define ls (p << 1)
#define rs (p << 1 | 1)
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef pair<int, int> PII;
const int N = 2e5 + 5, p = 998244353;
int vis[N];
ll po(ll rad, ll idx) {ll res = 1;while (idx) {if (idx & 1) res *= rad, res %= p;rad *= rad, rad %= p;idx >>= 1; }return res;
}
ll inv(ll x) {return po(x, p - 2);
}
void solve() {int n;cin >> n;ll x = 1, y = 1;for (int i = n / 3; i >= n / 3 - n / 6 + 1; i--) {x *= i, x %= p;//从n一直乘到n-m+1 y *= n / 3 + 1 - i, y %= p;//从1一直乘到m } ll c = x * inv(y) % p;//组合数ll ans = 1;for (int i = 0; i < n / 3; i++) {int a[3];cin >> a[0] >> a[1] >> a[2];sort(a, a + 3);ll cnt = 0;for (int j = 0; j < 3; j++) {if (a[j] == a[0]) cnt++;}ans *= cnt, ans %= p;} cout << ans * c % p << '\n';
}
int main(){ios::sync_with_stdio(false);cin.tie(0);int T = 1;
//	cin >> T;while (T--) solve();return 0;
}