2015-C19-team2

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

||Run ID||Time||Size||Problem||Language||Result||Failed test||
||147||5:00:00||1656||J||g++0x||Wrong answer||5||
||146||4:59:10||1656||J||g++0x||Wrong answer||5||
||145||4:52:10||1651||J||g++0x||Wrong answer||5||
||144||4:51:04||2309||L||g++0x||Wrong answer||5||
||143||4:48:59||1650||J||g++0x||Time-limit exceeded||3||
||140||4:40:57||1645||J||g++0x||Wrong answer||5||
||139||4:38:48||1622||J||g++0x||Time-limit exceeded||3||
||133||4:24:11||1002||K||g++0x||OK||N/A||
||132||4:20:55||1633||J||g++0x||Wrong answer||5||
||131||4:16:43||948||K||g++0x||Wrong answer||8||
||130||4:13:35||860||K||g++0x||Wrong answer||5||
||127||3:45:45||1228||E||g++0x||OK||N/A||
||123||3:33:08||1393||J||g++0x||Wrong answer||4||
||120||3:14:36||1188||J||g++0x||Wrong answer||4||
||114||2:26:38||790||A||g++0x||OK||N/A||
||110||2:14:09||775||A||g++0x||Wrong answer||4||
||103||1:46:56||680||A||g++0x||Time-limit exceeded||13||
||90||1:13:52||598||D||g++0x||OK||N/A||
||86||1:03:33||709||B||g++||OK||N/A||
||81||0:54:54||817||C||g++||OK||N/A||
||78||0:43:26||838||M||g++0x||OK||N/A||
||73||0:32:08||199||G||g++||OK||N/A||
||71||0:29:51||682||B||g++||Wrong answer||2||
||67||0:20:50||470||F||g++||OK||N/A||
||66||0:18:39||435||F||g++||Wrong answer||3||

== 流水账 ==

=== Patchouli_Go ===
L题的模型很眼熟，看了看数据范围以为能用最小环+一些乱搞方法做出来，浪费了大量时间。

K题开始往带log方向想，耽误了一些时间；想出来做法的时候不是很自信，sf和jtjl手上也有题，所以拖到很后面才开始写。最后单调队列优化的姿势也不对，强行加了个暴力访问队列元素才勉强过了，赶紧偷窥一发闽爷代码学习学习。


== 小结 ==



== 补题 ==

=== Patchouli_Go ===
~~L~~

== 题解 ==

=== H. Hero's Quest [Akalm] ===
f[state][i]表示当前连通状态为state，位于节点i的期望结束步数。由于题目选边方式随机，且和已有连通状态无关，所以同构的图一样，state的数量只有n的拆分数那么多。于是可以列出不同状态之间的转移方程，由于存在同状态内转移所以需要使用高斯消元。由于连通状态的转移是有向的，排序之后就只用做cnt_state次n元方程组的求解。

=== J. Joining Powers [Akalm] ===
二分答案，容斥，然后对于不同次数开方算答案。lcm大于60的集合都只有1。不知道哪里吃瘪了用__int128才能过。

Run ID	Time	Size	Problem	Language	Result	Failed test
147	5:00:00	1656	J	g++0x	Wrong answer	5
146	4:59:10	1656	J	g++0x	Wrong answer	5
145	4:52:10	1651	J	g++0x	Wrong answer	5
144	4:51:04	2309	L	g++0x	Wrong answer	5
143	4:48:59	1650	J	g++0x	Time-limit exceeded	3
140	4:40:57	1645	J	g++0x	Wrong answer	5
139	4:38:48	1622	J	g++0x	Time-limit exceeded	3
133	4:24:11	1002	K	g++0x	OK	N/A
132	4:20:55	1633	J	g++0x	Wrong answer	5
131	4:16:43	948	K	g++0x	Wrong answer	8
130	4:13:35	860	K	g++0x	Wrong answer	5
127	3:45:45	1228	E	g++0x	OK	N/A
123	3:33:08	1393	J	g++0x	Wrong answer	4
120	3:14:36	1188	J	g++0x	Wrong answer	4
114	2:26:38	790	A	g++0x	OK	N/A
110	2:14:09	775	A	g++0x	Wrong answer	4
103	1:46:56	680	A	g++0x	Time-limit exceeded	13
90	1:13:52	598	D	g++0x	OK	N/A
86	1:03:33	709	B	g++	OK	N/A
81	0:54:54	817	C	g++	OK	N/A
78	0:43:26	838	M	g++0x	OK	N/A
73	0:32:08	199	G	g++	OK	N/A
71	0:29:51	682	B	g++	Wrong answer	2
67	0:20:50	470	F	g++	OK	N/A
66	0:18:39	435	F	g++	Wrong answer	3

流水账

Patchouli_Go

L题的模型很眼熟，看了看数据范围以为能用最小环+一些乱搞方法做出来，浪费了大量时间。

K题开始往带log方向想，耽误了一些时间；想出来做法的时候不是很自信，sf和jtjl手上也有题，所以拖到很后面才开始写。最后单调队列优化的姿势也不对，强行加了个暴力访问队列元素才勉强过了，赶紧偷窥一发闽爷代码学习学习。

小结

补题

Patchouli_Go

L

题解

H. Hero's Quest [Akalm]

f[state][i]表示当前连通状态为state，位于节点i的期望结束步数。由于题目选边方式随机，且和已有连通状态无关，所以同构的图一样，state的数量只有n的拆分数那么多。于是可以列出不同状态之间的转移方程，由于存在同状态内转移所以需要使用高斯消元。由于连通状态的转移是有向的，排序之后就只用做cnt_state次n元方程组的求解。

J. Joining Powers [Akalm]

二分答案，容斥，然后对于不同次数开方算答案。lcm大于60的集合都只有1。不知道哪里吃瘪了用__int128才能过。

附加文件

201509221615 Summer2015Team Siunaus-contest19.tar.gz by jtjl
l.cpp by akalm