ACM-ICPC 2012 Jinhua Online Contest

小结一下今天的金华网络赛.
由于Prowindy跑去上海和UESTC的机油们会晤去了… 于是这场比赛由我和zYc两个人打.
先放一个我们的board

前期我和zYc比较迅速地切掉了大水题, 1004 和 1006

然后zYc就开始跳1008的sum, 我开始看有大量提交的1009.

看完以后发现就是JSOI的原题. 但是把那个同权的边最多10条的限制去掉了.

我想了一下, YY出了用矩阵解决同权边计数问题的写法(就是利用Kirchhoff’s matrix tree theorem). 于是我就开始手写, 但是因为之前我自己用的求行列式的模板要求逆元的, 比较圡, 解决不了这种p非素数的情况, 所以就用了浙大模板里Navi的那种辗转相减的方法. 消元复杂度为$$O(n^3 \log x)$$. 但是这又有个新的问题, 行列式的符号不知道怎么判. 后来发现这个行列式必然是正的… 直接对行列式求模就是对的. 但是写完输出结果总是0… 稍微gdb了一下发现是同权的边的处理里面根本构不成树, 之前写沙茶了… 改完以后就1Y了.

这时候zYc写了近两个小时的sum以后, 发现样例不对… 于是才发现题目是list里面的数要和x互素, 而不是下标和x互素… :Tired: 于是他重写以后就过了…

在他发现读错题重写的这段时间, 我开了1010. 直接WA了四遍… 最后看Clarification发现有人质问a a的lca是什么, admin说就像现实生活中的那样… 顿时感到好像被玩了文字游戏, 改过以后就Y了.

刷了一下ranklist… =.= 我们很果断地分别开1005 和 1007. 我的1007也是卡了很久, sample一直不过, 原因是那个权值有两个地方忘了乘学分(吐槽:这个人已经没救了)… 改掉以后就1Y了.

接下来我再开题似乎就不怎么明智了. 于是围观zYc写1005. 发现他用了一个来路不明的模板(疑似是被网友改过的浙大模板…T_T). sample调不过去, 简直坑爹啊!!! 于是我们协商了一下, 把那个东西直接删掉了. 我来帮他敲了浙大模板… 最后改掉一个小错误, 就1Y了.

我们两个人, 打成这样还算可以接受. 不过基本上是在跟风做题… 没什么选择的余地. 如果Prowindy在的话应该会好一点吧.

吐槽:

-.-, 比赛到一半, 放出这么一个通知.

请大家遵守比赛纪律

现发现，1009提交有相同代码将近30个，请大家注意，遵守比赛纪律，不要拷贝代码，还有，需要批评的是，中国地质大学两个队交了相同的1001代码，大连理工大学，同济大学也各有两个队，交了相同的1001代码，希望类似的事情不要再发生

虽然说出原题很可耻, 但是在这种正式比赛下直接交搜到的代码. 真是…
不知道是我自己有强迫症还是干嘛, 我一直比较讨厌那种直接就贴别人例程的行为…
特别是自己根本不懂那个东西的时候, 抄别人例程和模板都心里挺难受的(OI落下的后遗症么 :Worry: )…

最后yyyyyyyyyyyyyyyyyyym 夺冠的旅游队(师父 + CLJ + GYZ).

附1009代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
template  void checkmin(T &t,T x){if (x < t) t = x;}
template  void checkmax(T &t,T x){if (x > t) t = x;}
template  void _checkmin(T &t, T x){if (t == -1) t = x; if (x < t) t = x;}
template  void _checkmax(T &t, T x){if (t == -1) t = x; if (x > t) t = x;}
typedef pair  PII;
typedef pair  PDD;
typedef long long lld;
#define foreach(it,v) for (__typeof((v).begin()) it = (v).begin();it != (v).end();it++)
#define DEBUG(a) cout << #a" = " << (a) << endl;
#define DEBUGARR(a, n) for (int i = 0; i < (n); i++) { cout << #a"[" << i << "] = " << (a)[i] << endl; }
const int N = 105;
int n, m, p;
int f[N];
int bak[N];
int ref[N];
int a[N][N];
int b[N][N];
double kir[N][N];
int v[N];
vector  vec[15];

int detMod(int n, int m, int mat[][N]);

int gf(int x) {
	if (f[x] == x) return x;
	return f[x] = gf(f[x]);
}

lld calc(int w) {
	for (int i = 0; i < n; i++) bak[i] = gf(i);
	foreach (it, vec[w]) {
		if (gf(it->first) != gf(it->second)) {
			f[f[it->first]] = f[it->second];
		}
	}
	lld ret = 1;
	for (int i = 0; i < n; i++) gf(i);
	fill(v, v + n, 0);
	for (int i = 0; i < n; i++) {
		if (v[bak[i]]) continue;
		m = 0;
		for (int j = 0; j < n; j++) {
			if (f[i] == f[j] && !v[bak[j]]) {
				ref[bak[j]] = m++;
				v[bak[j]] = 1;
			}
		}
		for (int j = 0; j < m; j++) {
			for (int k = 0; k < m; k++) {	
				a[j][k] = 0;
			}
		}
		if (m == 1) continue;
		foreach (it, vec[w]) {
			int x = it->first;
			int y = it->second;
			if (f[x] == f[i] && bak[x] != bak[y]) {
				a[ref[bak[x]]][ref[bak[y]]]--;
				a[ref[bak[y]]][ref[bak[x]]]--;
				a[ref[bak[x]]][ref[bak[x]]]++;
				a[ref[bak[y]]][ref[bak[y]]]++;
			}
		}
		ret = ret * detMod(m - 1, p, a) % p;
	}
	return ret;
}


typedef long long LL;
int detMod(int n, int m, int mat[][N]) {
	if (n == 0) return 1;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            mat[i][j] %= m;
    LL ret = 1;
	int cnt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++)
            while (mat[j][i] != 0) {
                LL t = mat[i][i] / mat[j][i];
				cnt++;
                for (int k = i; k < n; k++) {
                    mat[i][k] = (mat[i][k] - mat[j][k] * t) % m;
                    int s = mat[i][k];
                    mat[i][k] = mat[j][k];
                    mat[j][k] = s;
                }
				ret = -ret;
            }
        if (mat[i][i] == 0)
            return 0;
        ret = ret * mat[i][i] % m;
    }
	ret += m;
	ret %= m;
    if (ret < 0)
        ret += m;
    return (int)ret;
}

int main(){
#ifdef cwj
	freopen("in", "r", stdin);
#endif
	while (scanf("%d%d%d", &n, &m, &p) != EOF && n + m + p) {
		for (int i = 0; i < 15; i++) vec[i].clear();
		for (int i = 0; i < n; i++) { f[i] = i; }
		for (int i = 0; i < m; i++) {
			int x, y, w;
			scanf("%d%d%d", &x, &y, &w);
			x--; y--;
			vec[w].push_back(make_pair(x, y));
		}
		long long ans = 1;
		for (int i = 0; i < 15; i++) {
			lld tmp = calc(i);
			ans = ans * tmp % p;
		}
		set  Set;
		for (int i = 0; i < n; i++) {
			Set.insert(gf(i));
		}
		if (Set.size() != 1) {
			puts("0");
		} else {
			cout << (ans % p + p) % p << endl;
		}
	}
}