一个信竞生的trie树。
已经退役快两年啦！目前THU CS专业在读
也算没有辜负竞赛中投入的心血吧
依旧很感谢那段时光！
2018.10.30
T1: 纸牌游戏（cards）
时间限制: 1 Sec 内存限制: 512 MB Special Judge
题目描述
华华和秀秀在玩纸牌游戏，游戏的规则如下：
初始时，桌面上有n张纸牌，每张纸牌上写有一个正整数。游戏开始时华华先在黑板上写上数字0，之后秀秀和华华轮流选取纸牌（秀秀先手）。当一个人选定一张纸牌时，他需要将黑板上的数字改写成这个数和纸牌上的数的最大公约数，然后将这张纸牌丢弃。当一个人写下了1 或者无法选取纸牌时，他就输了。
现在秀秀想知道：
1. 当华华和秀秀都按照随机策略选取卡片时，秀秀获胜的概率有多少；
2. 当华华和秀秀都按照最优策略选取卡片时，秀秀获胜的概率有多少。
输入第一行，包含一个正整数n。
输入第二行，包含n个正整数，表示纸牌上的数字。
输出两个由空格隔开的实数，分别表示随机策略下的获胜概率和最优策略下的获胜概率。
4
1 2 3 4
0.583333333 1.000000000
数据范围
对于100%的数据：n≤300, 纸牌上的数≤1000
Sol:
基本思路：task1 dp，task2 乱搞
task1: 记fi,j为取了i个数，此时黑板上的数为j的概率，sj为a中是j的倍数的数的个数。那么有转移式：
fi+1,j+=fi,j*(sj-i/n-i)
fi+1,(j,ak)+=fi,j*(1/n-i)
其中(a,b)为a和b的gcd。
注意当j为1时fi,j不能用于转移了，此时应直接记录答案。
task2: 考虑游戏的过程，黑板上的数应为不升的，且在变成1之前所有出现的数有gcd=k（k!=1）。
记所有可能的数k为“最小单位”，那么筛出所有最小单位数，显然如果存在ai使得所有kj | ai，sj为奇数，那么当先手取了ai，后手无论让哪个数成为最小单位，最终都是先手必胜。
那么ki应该怎么筛呢？考虑把a中的数两两取gcd，再取每一个gcd，把其倍数全部筛去，那么最后剩下的就是最小单位。
证明正确性：最小单位应满足两个性质：
1. 两两互质
2. 在满足1. 的前提下极大
那么这种筛法首先能筛掉所有不互质的最小单位，并且因为一开始用来筛的数全部是最大公约数，所以不存在一个更大的数满足最小单位的性质。
（感性认知一下）
然后一开始有一个做法是把所有质数筛出来作为最小单位，显然这样是不满足2.的性质的，但为什么不正确呢？我们来看一组数据：
7
10 15 30 60 120 7 49
筛质数的算法告诉我们，取10先手必胜，因为10的约数中2有5个，5也有5个。但是我们通过手%发现：我们并不能通过操作把10分裂成2和5！
所以这就是2. 性质的原因：取极大的最小单位，也就是单位不能再被操作分裂。