NOIP模拟赛第7场题解：
题解见：http://www.cqoi.net:2012/JudgeOnline/problemset.php?page=13
题号为2221-2224.
1.car
边界要当做建筑物。
只需要判断是否存在一个'.'，至少三面都是建筑。那么这个点就是所谓的“死胡同”.
2.gcd
利用整数唯一分解定理，求出A,B的所有质因数和该质因数出现的次数。
对A,B的公共质因数取其出现次数的最小值，再将该质因数的最小值次幂累乘起来即可。
3.pair
这是一道非常有质量的题，很考思维。
暴搜的时间复杂度是O(N^2).只能处理n较小的数据。30分应该没有问题。
一般会想到容斥原理。
要统计num和之前的多少数形成一个pair，可以这样计算：与num有一个共同数字的数之和-与num有两个共同数字的数之和+与num有三个共同数字的数之和-……
如何计算与num有k个共同数字之和呢？可以这样做：
利用一个数组bit[2^10]，如果当前数包含了数字i（出现多次算一次），则bit[1<<i]++;如果同时出现了i，j，则bit[1<<i]++,bit[1<<j]++,bit[(1<<j)|(1<<i)]++,如果包含i，j，k等多个数字，依次类推。
这样，要计算与num有一个共同数字的数的个数：sum(bit[1<<i])(0<=i<=9 &&num包含数字i)
这种方法很麻烦，而且时间复杂度为O(N*2^10).程序肯定会超时。
注意到bit[2^10]。为什么我们可以用这么小的一个数组来记录所有数“包含哪些数字”的信息？
思考后你会发现，其实对于一个数num，我们只关心它包含哪些数字，至于这些数字出现的顺序，出现的次数，都可以不用考虑。
所以我们把一个数num，转换为一个小于1024的数k。转换规则很简单，如果num包含数字i，则k中右数第i位设为1，否则第i位为0.
这样所有的数既可以映射到1个1024的区间，这样，相当于缩小了n的范围。现在可以用暴搜了解决了。
结果由两部分组成：
第一部分：设cnt[i]表示转换后得到的数i出现的次数。i和其他数形成的pair，即为cnt[i]*cnt[j].（j表示其他数，且i&j！=0）。最后将这些乘积累加，再除以2.（因为每个pair都计算了两次。）
第二部分：
i代表的是相同的一类数num，这些数对应同一个i，它们是两两成pair的，一共可以形成C(cnt[i],2)个pair。（组合计数，从cnt[i]个元素中取出两个，所以为C(cnt[i]，2)）。所有的i都可以得到一个C（cnt[i],2）,这部分全部累加起来。
两部分的和即为答案。
第四题：如果26层循环相互之间没有关系，则是一个连乘即可解决的问题。
现在有些循环变量的边界是外层循环变量，我们称这两层循环有对应关系。
我们把每个循环变量看做一个节点，有对应关系的节点连一条边。具体说：题目说了，任意一个变量的两个边界中，至少有一个为常量，
也就是说之多只有一个边界为变量。如果v2的一个边界为v1，则v1向v2连一条边。这样会得到一个森林，即多棵树。
树中的节点即一个循环变量，所有循环变量给res带来的贡献即该树的结果。
树与树之间是互相独立的。最后的res值等于每棵树代表的结果的乘积。
如何计算一棵树的结果。
设f[root]为以root为根的子树的结果，g(node,number)表示节点node表示的变量取值为number时，其子树的结果。则有下列式子
注意下式中,g(node,number)只给出了一种情形，node所表示的变量的上界为常数；还有另一种情形，即node所表示的变量的下界为常数，g（node,number）的表达式要稍作修改，但其实本质都差不多的。下面的式子中，类似于pi的符号表示取乘积。
这个时间复杂度是O(nm2)的，只能过70%的数据。
注意到，g(node,number)的计算是可以递推得到的，即
这样，时间复杂度为O(nm)了。