心路历程

预计得分：\(100 + 100 + 30\)

实际得分：\(100 + 100 + 30\)

终于有一次没fst了哈哈哈(每个题都有大样例你还好意思fst？)

考的也是异常的浪。。

T1傻逼题。T2原题。T3一点都不会做

然后1.5h就完了。。。检查无误之后去小机房浪了一个多小时。。

Sol

T1：直接贪心即可。最优策略显然是用第一个序列的大的 和 第二个序列的小的放在一起

T2：。。\(N, M \leqslant 50\)标算\(O(n)\)可海星。。

T3：神仙容斥，标算看不懂。。弃疗弃疗

在神仙zbq的指导下我好像看懂了。

设\(f_i\)表示恰好\(i\)条边已经被染色的三元环个数

\[ans = f_0 - f_1 - f_2 - f3\]

分别考虑每一个如何计算

设\(all = M * (M - 1) * (M - 1)\)

\(f_0 = C_n^3 all\)

\(f_3\)可以在暴力枚举三元环的过程中计算

\(f_1\)可以通过统计每条边的贡献来计算

\(f_2\)也能算出来。。。

注意在求组合数的时候不能直接推逆元

需要手动把式子展开算。

放一下std。

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using std::vector;typedef unsigned int uint;const int EDGE_SIZE = 524288;const int POINT_SIZE = 131072;struct edge_list {    int point, color;    uint tri;    edge_list();    edge_list(int, int);    bool operator < (const edge_list & ) const;};struct edge_tuple {    int u, v, color;    void get();};int getint();uint comb_2(int);   // equal to C(n, 2)uint comb_3(int);   // equal to C(n, 3)void add_edge(int, int, int);void init(int);bool cmp_color(const edge_list & , const edge_list & );edge_tuple a[EDGE_SIZE];vector
         
           e[POINT_SIZE];vector
          
           
             > common;int deg[POINT_SIZE];uint tri[POINT_SIZE];uint tri0[POINT_SIZE];int main() { freopen("triangle.in", "r", stdin); freopen("triangle.out", "w", stdout); uint T, n, m, p; uint ans; for (T = getint(); T; T--) { n = getint(), m = getint(), p = getint(); uint tmp = m * (m - 1) * (m - 2); init(n); for (int i = 0; i < p; i++) { a[i].get(); deg[a[i].u]++; deg[a[i].v]++; } for (int i = 0; i < p; i++) if (deg[a[i].u] < deg[a[i].v]) add_edge(a[i].u, a[i].v, a[i].color); else add_edge(a[i].v, a[i].u, a[i].color); for (int i = 1; i <= n; i++) std::sort(e[i].begin(), e[i].end()); ans = comb_3(n) * tmp; //type3 三元环中三条边都被染过色 for (int u = 1; u <= n; u++) for (int i = 0; i < e[u].size(); i++) { int v = e[u][i].point; int j = 0, k = 0; common.clear(); while (j < e[u].size() && k < e[v].size()) { for ( ; j < e[u].size() && e[u][j].point < e[v][k].point; j++); if (j >= e[u].size()) break; for ( ; k < e[v].size() && e[v][k].point < e[u][j].point; k++); if (k >= e[v].size()) break; if (e[u][j].point == e[v][k].point) common.push_back(std::make_pair(j, k)), j++, k++; } for (int j = 0; j < common.size(); j++) { int w = e[u][common[j].first].point; int c1, c2, c3; e[u][i].tri++; e[u][common[j].first].tri++; e[v][common[j].second].tri++;//统计每条边被多少个三元环包含 c1 = e[u][i].color; c2 = e[u][common[j].first].color; c3 = e[v][common[j].second].color; tri[u]++, tri[v]++, tri[w]++;//统计每个点被多少三元环包含 if (c1 != c2 && c2 != c3 && c3 != c1) ans -= tmp - 1; else { ans -= tmp; if (c1 == c2) tri0[u]++; if (c1 == c3) tri0[v]++; if (c2 == c3) tri0[w]++;//tri0表示与第i个点相连的边中，有多少对颜色相同 } } } //type1 统计三元环中 只有一条边被指定过颜色 for (int u = 1; u <= n; u++) for (int i = 0; i < e[u].size(); i++) { int v = e[u][i].point; uint cnt = n - deg[u] - deg[v] + e[u][i].tri; ans -= cnt * (tmp - (m - 1) * (m - 2)); } //type2 for (int i = 0; i < p; i++) if (deg[a[i].u] >= deg[a[i].v]) add_edge(a[i].u, a[i].v, a[i].color); else add_edge(a[i].v, a[i].u, a[i].color);//把图补满 for (int i = 1; i <= n; i++) { std::sort(e[i].begin(), e[i].end(), cmp_color); uint cnt = comb_2(deg[i]) - tri[i]; ans -= cnt * (tmp - (m - 2));//把式子拆开会更好理解 cnt = 1; for (int j = 1; j < e[i].size(); j++) if (e[i][j].color == e[i][j - 1].color) cnt++; else { ans -= comb_2(cnt) * (m - 2); cnt = 1; } ans -= comb_2(cnt) * (m - 2); ans += tri0[i] * (m - 2); } if (m < 3) ans = 0; printf("%u\n", ans); } return 0;}edge_list::edge_list(int _point, int _color) { point = _point; color = _color; tri = 0;}bool edge_list::operator < (const edge_list & other) const { return point < other.point;}void edge_tuple::get() { u = getint(); v = getint(); color = getint();}int getint() { int num = 0; char ch; do ch = getchar(); while (ch < '0' || ch > '9'); do num = num * 10 + ch - '0', ch = getchar(); while (ch >= '0' && ch <= '9'); return num;}uint comb_2(int n) { uint f = 1; if (n < 2) return 0; if (n & 1) f = n - 1 >> 1, f *= n; else f = n >> 1, f *= n - 1; return f;}uint comb_3(int n) { uint f = 1, a = n, b = n - 1, c = n - 2; if (n < 3) return 0; if (a % 3 == 0) a /= 3; else if (b % 3 == 0) b /= 3; else c /= 3; if (a & 1) b >>= 1; else a >>= 1; f = a * b * c; return f;}void add_edge(int u, int v, int color) { e[u].push_back(edge_list(v, color));}void init(int n) { for (int i = 1; i <= n; i++) e[i].clear(); memset(tri, 0, sizeof(tri)); memset(tri0, 0, sizeof(tri0)); memset(deg, 0, sizeof(deg));}bool cmp_color(const edge_list & a, const edge_list & b) { return a.color < b.color;}