题意：

给出n个点，条边的无向图，无重边，无自环。现在要求把所有的无向边换成有向边，使得入度为0的点最少。问最少的入度为0的点是多少。

思路：

对于每个联通快，如果有环，我们可以顺时针连接环上的点，以指向环的方向连接联通快上的其他点，这样就可以保证所有点的入度都不为0. 如果是树形结构，则不可避免得使得一个点的入度为0.

题意：

3个岛屿群，每个岛屿群有若干岛屿。现在要在岛屿之间连桥，桥的长度是1，规定2个属于相同岛屿群的岛屿的距离要大于等于3.

思路：

一直在纠结大于等于3的距离的事情。。。其实这句话等价于，同一个岛屿，对于另外两个岛屿群，都最多只能连接1个岛屿。

题目链接

题意：有n个整点，每个点处可以什么都不画，或者画一条垂直方向的直线，或者画一条水平方向的直线。

现在给出n个点的坐标，问最多右多少种不同的图案。(只要有一处不同，就认为两个不同）

题意：给定一个有向图，问从A点恰好走k步（允许重复经过边）到达B点的方案数mod p的值

思路： ** 把给定的图转为邻接矩阵，即A(i,j)=1当且仅当存在一条边i->j。令C=A*A，那么C(i,j)=ΣA(i,k)A(k,j)，实际上就等于从点i到点j恰好经过2条边的路径数（枚举k为中转点）。类似地，CA的第i行第j列就表示从i到j经过3条边的路径数。同理，如果要求经过k步的路径数，我们只需要快速幂求出A^k即可。**

cf682A题目链接

题意：两个数组，分别为1..n和1..m。。。从两个数组中各取一个，问和能被5整除的方案数。。。

思路：傻逼题。。。统计%5。。。然后乘法原理。。

1632: [Usaco2007 Feb]Lilypad Pond

Time Limit: 5 Sec  Memory Limit: 64 MB Submit: 496  Solved: 153 [Submit][Status][Discuss]

Description

Farmer John 建造了一个美丽的池塘，用于让他的牛们审美和锻炼。这个长方形的池子被分割成了 M 行和 N 列( 1 ≤ M ≤ 30 ; 1 ≤ N ≤ 30 ) 正方形格子的 。某些格子上有惊人的坚固的莲花，还有一些岩石，其余的只是美丽，纯净，湛蓝的水。 贝茜正在练习芭蕾舞，她从一个莲花跳跃到另一个莲花，当前位于一个莲花。她希望在莲花上一个一个的跳，目标是 …

http://acm.hdu.edu.cn/showproblem.php?pid=4451 题意：N clothes, M pants and K shoes，然后给出p个不合法的搭配，形式是“clothes x pants y” or “pants y shoes z”.” 问有多少种合法的方案。 思路：一开始觉得是容斥。。当然可以。。但是实际上，不合法的搭配的形式比较简单，每种不合法的发配都是两个两个的不合法，以及每种不合法的形式都有pants,那么我们就可以通过先确定pants，对于每种pants，方案数就是能和当前pants搭配的clothes数，乘以能和当前pants搭配的shoes数，然后累加每种pants的答案即可。

http://acm.hdu.edu.cn/showproblem.php?pid=5145 题意：有n个女孩，编号1..n,第i个女孩在第a[i]个教室,m次访问，每次访问编号[L,R]的女孩，处于同一个教室的女孩一次只能访问一个，问有多少种访问方案。两个不同的方案当且仅当访问的顺序有所不同。

http://codeforces.com/contest/604/problem/D 题意：一个恒等式 f(kx%p)=kf(x)%p ,k,p为常数，且满足x对于定义域为0..p-1的p的整数，值域也在0..p-1范围（不一定一一对应）。问满足题意的f有多少个。 思路： f(0)=0,对于其他的值，当f（x）确定时，f（kx%p）也随之确定，那么把kx%p看做新的x,f（kkx%p）也随之确定...相当于【1，p-1】被分为r个小环，确定每个环可以任选一个数字，ans=p^r。环的个数可以用dfs跑一遍得到r. 注意当k=1的时候是特殊情况，f(x)恒等于f(x)那么答案应该有p的p次方种。因为对于p个f(0..p-1)，每一个 …

dp方程想错了.果然还是欠练啊.

如果我们不考虑坏点,那么从 (0,0)到(x,y)的方案数是c(x+y,x)或者c(x+y,y)

因为有坏点的存在,我们可以逆向思维,先求出总数,然后减去那些由于坏点的影响不能走的方案数.