作者存档：edward_mj

似乎ipad上的wordpress自带刷评论功能-.-, 我就用它登陆了一下, 过了一会儿就有几条这样子的东西出现了… “Extremely helpful information specially the last part 🙂 I care for such info a lot. I was seeking this particular info for a long time. Thank you and best of luck.”

ACM-ICPC 2012 Hangzhou Online Contest

今天真心圡成狗…写写流水账.

今天一上来我直接看了第二题和第三题, 但是似乎不是特别好写. 这时候zYc学长发现了一道典型的数据结构题(1008).
告诉我题意以后马上就得出了线段树套线性表的做法, 但是刚敲完读入, 发现只要离线树状数组搞就可以了. 于是1Y.

然后zYc跳1006, prowindy跳1005.
本来1005是全场秒杀题, 但是不知道为什么prowindy的代码WA了, zYc学长似乎有各种题意上的理解偏差, 也一直卡着.
1002这时候已经有人过了, 我去看了一下就发现是费用流, 但是因为自己太圡了, 还搞了半小时才调对sample, 然后1Y.

这时board上来看, 1005已经成了万人轮的题目. 于是跑去扫了一遍prowindy的代码.
没看出有什么问题. 虽然直觉上觉得那个度数判定可能有点问题, 但是想了一下好像又是对的. 然后就让prowindy重写一遍去了… 然后重写了一遍改了点小错误就Y了.
接下来zYc学长在clarification上各种刷, prowindy去帮zYc搞1006. 于是我就去写1007的后缀数组, 一开始写的直接用sort的, 复杂度$$O(n \log^2 n)$$ TLE了.
各种尝试未果, T死在那里.
于是找个DC3 $$O(n)$$ 的模板, 怎么交怎么RE. 直接被弄出阴影来了… 上次训练也是用罗穗骞的, 结果传一个串, 什么都没干就RE了… 交了几次RE以后, 就用了小hh的倍增模板$$O(n \log n)$$. 一交直接Y了.
果然还是hh靠谱…(让你天天不整理模板, 现在出事了吧…)
关于模板这个问题, 其实被坑过很多遍, 主要是平常我自己刷题习惯不使用模板, 导致没什么模板积累. 但是这样比赛可是要吃大亏的!!!

然后在我圡爆的时候, 队友也把1006搞出来了.

于是看一下board, 剩下的分工就很明确了. 让zYc去搞1003, 我和prowindy一起想了一下1010, 未果(脑子抽了当时居然连线段树求矩形并面积都不会了)… 然后我看了一下1009, 发现似乎是很裸的求期望的题目, 先bfs求可行性, 然后gauss消出期望就好了. 搞过了sample, 一交就RTE… 然后比赛就结束了.

感觉比赛里我比较圡的有这么几点:

  1. Suffix Array 没做好模板, 别人的又不习惯. 导致1007卡了好久.
  2. 1010的那个矩形并都反应不出来怎么搞了… -.-, 习惯了平常直接传各种标记的方式. 实在是太圡了.
  3. 帮prowindy看万人轮的1005, 也没看出什么错误… challenge能力有待加强了.
  4. 平常没怎么用力刷题, 手速没7月集训快了5555, 状态略显糟糕.

BTW, prowindy同学似乎感冒了的样子, 离Regional不远了… 注意身体.

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;
		}
	}
}