传送门

题意：

有$n$个队伍，每个队伍都有一个能力值$a_i$，每个两个队伍之间会打一场比赛，$i$打$j$胜利的概率为$\frac {a_i} {a_i+a_j}$，求能够击败所有队伍的数量的期望（如果a击败了b，b击败了c，可以视为a击败了c）。

$n\leq 14$

传送门

题意：

一个长为$n$的排列，有两个人轮流从中取数，每一轮中所取的数需要满足如下规则：

1. 取的数大于之前所有人取的数
2. 取的数的下标大于取数人之前取的数的下标
3. 如果有多种取数方案，则随机进行取数
4. 第一个人第一次取数随机
5. 如果有人没法再取数，游戏结束

求最后期望能取数多少次。

传送门

题意

给定$n，mod$，求有多少对$(p,q)$满足：

1.$p,q$是长度为n的排列

2.$p$的字典序大于$q$

3.$p$的逆序对数小于$q$

题意：

T次询问，每次给出A,B,K,W，求满足下面条件的(x,y)对数：

1.x,y是整数

2.$x \in [0,A],y\in[0,B]$

3.$|x-y|\leq K$

4.$x~ xor~ y\leq W$

$A,B,K,W\leq10^9,T\leq2000$

3134是三年前写的题，这次复习顺便再写一道3679

BZOJ3134

题意：

一个数是非回文数当且仅当不包含长度大于1的回文数。比如16276是无回文数，而17276因为含有727而不是。
求区间内有多少个非回文数。

传送门

题意：

给出$k,p_1,p_2$，一开始串为空，每次有$\frac {p_1}{p_1+p_2}$的概率在串中加一个a，$\frac {p_2}{p_1+p_2}$的概率在串中加一个b，当串中有k个为ab的子序列停止加字符，求停止加字符后串中为ab的子序列的个数的期望，假设结果为最简分数$\frac{ans_1}{ans_2}$,输出$ans_1\times ans_2^{-1}\mod(1e9+7)$。

权限题。

题意：

给一个n × m的01矩阵，求一个最大的全1矩阵，输出答案 × 3。

$n,m\leq 1000$

传送门（codeforces GYM）

题意：

​ 给你一个$n\times m$的矩形，对其进行上色，要求每个$2\times 2$的小正方形中的颜色不能相同，求方案数模p。

​ $n<=10^{100},m\leq5,p\leq10000$

传送门

新传送门

题意：

中文题，非权限题。

传送门

新传送门

一道练习综合代码能力的好题
先把被依赖的点连向依赖这个点的点，再tarjan缩点，缩点后会形成多棵树，对每棵树进行dp，最后进行一次背包即可，注意要倒着枚举。