计数问题

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

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

题目链接 题意：有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。。。然后乘法原理。。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年07月18日 星期一 12时32分22秒 4File Name :code/2016whust/A.cpp 5************************************************ */ 6 7#include <cstdio> 8#include <cstring> 9#include <iostream> 10#include <algorithm> 11#include <vector> 12#include <queue> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <ctime> 19#define fst first 20#define sec second 21#define lson l,m,rt<<1 22#define rson m+1,r,rt<<1|1 23#define ms(a,x) memset(a,x,sizeof(a)) 24typedef long long LL; 25#define pi pair < int ,int > 26#define MP make_pair 27 28using namespace std; 29const double eps = 1E-8; 30const int dx4[4]={1,0,0,-1}; 31const int dy4[4]={0,-1,1,0}; 32const int inf = 0x3f3f3f3f; 33const int N=1E6+7; 34int n,m; 35LL a[N],b[N]; 36int main() 37{ 38 #ifndef ONLINE_JUDGE 39 freopen("code/in.txt","r",stdin); 40 #endif 41 42 cin>>n>>m; 43 ms(a,0); 44 ms(b,0); 45 for ( int i = 1 ; i <= n ; i++) 46 { 47 int x = i % 5; 48 a[x]++; 49 } 50 for ( int i = 1 ; i <= m ; i++) 51 { 52 int x = i % 5; 53 b[x]++; 54 } 55 LL ans = 0; 56 ans = a[0]*b[0]+a[1]*b[4]+a[2]*b[3]+a[3]*b[2]+a[4]*b[1]; 57 cout<<ans<<endl; 58 59 #ifndef ONLINE_JUDGE 60 fclose(stdin); 61 #endif 62 return 0; 63}

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 ) 正方形格子的 。某些格子上有惊人的坚固的莲花，还有一些岩石，其余的只是美丽，纯净，湛蓝的水。 贝茜正在练习芭蕾舞，她从一个莲花跳跃到另一个莲花，当前位于一个莲花。她希望在莲花上一个一个的跳，目标是另一个给定莲花。她能跳既不入水，也不到一个岩石上。 令门外汉惊讶的是，贝茜的每次的跳跃像中国象棋的马一样：横向移动1，纵向移动2，或纵向移动1，横向移动2。贝茜有时可能会有多达8个选择的跳跃。 Farmer John 在观察贝茜的芭蕾舞联系，他意识到有时候贝茜有可能跳不到她想去的目的地，因为路上有些地方没有莲花。于是他想要添加几个莲花使贝茜能够完成任务。一贯节俭的Farmer John想添加最少数量的莲花。当然，莲花不能放在石头上。 请帮助Farmer John确定必须要添加的莲花的最少数量。在添加的莲花最少基础上，算出贝茜从起始点跳到目标点需要的最少的步数。最后，还要算出满足添加的莲花的最少数量时，跳跃最少步数的跳跃路径的条数。

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)，每一个都可以任意取p种值。

dp 方程想错了。果然还是欠练啊。 如果我们不考虑坏点，那么从 (0,0) 到 (x,y) 的方案数是 c(x+y,x) 或者 c(x+y,y)。 因为有坏点的存在，我们可以逆向思维，先求出总数，然后减去那些由于坏点的影响不能走的方案数。