。。。笔记
1.划分问题
点划分直线：f(n) = f(n-1) + 1
线划分平面：g(n) = g(n-1) + f(n-1)
平面划分空间：s(n) = s(n-1)+g(n-1)
具有相似的递推关心，n维空间的划分与n-1维空间相关。
2.8皇后问题
n后问题存在构造解，对于解的个数目前尚未存在定理，只能搜索
3.8数码
数码问题存在解的条件是：与逆序对相关，观察移动过程，计算时，把0看成一个元素，考虑交换两个元素时的逆序数变化，前后总是相差奇数个，故如果逆序数的变化与0元素曼哈顿变化奇偶一致，则说明可达。
具体原因如下：曼汉顿距离代表了元素如果到达目标位置必须进行的交换次数的奇偶性，而在逆序数，而交换的同时逆序数由原来的变为后来的w*h-1，而每次进行交换只能使逆序数变化奇数个。
即如果逆序数变化了偶数个，则曼汉顿距离必须为偶数才能保证，奇数*偶数=偶数
即如果逆序数变化了奇数个，则曼汉顿距离必须为奇数才能保证，奇数*奇数=奇数
4.过桥
5.数独
搜索
6.24点
7.1…n中数字0的个数
8.布尔表达式求值
9.Joseph问题
10.next permutation
11.二分查找的优化
12.名人问题
13.BM算法
14.等值首尾和（元素全为正）
15.杨氏矩阵的查找
16.表示为两数平芳和
17.排列组合生成
18.找零钱
19.最大方块1矩阵
20.和为0的段落
21.atint,inta
22.输出所有合法括号
23.最大连续和，积
24.最长递增序列
25.等量正负号段落
26.知道不知道
27.链表树栈队列
28.n！最后一个非零位
这个比较复杂：zz一篇：求大数阶乘的最后一个非零位的算法
1) n!=2^i*3^j*5^k*7^l*…
对任意的n>1，有i>k，
所以n!/(2^k*5^k)的最后一位为所求，即n!/(2^k*5^k) mod 10 －－ (a)
定义f(n!)=n!/(2^i*5^k)，则(a)式化为：(2^(i-k) mod 10 * f(n!)) mod 10
2) 求2^(i-k) mod 10
i=n/2+n/2/2+n/2/2/2+… k=n/5+n/5/5+n/5/5/5+…
又有2^1 mod 10 = 2, 2^2 mod 10 = 4, 2^3 mod 10 = 8, 2^4 mod 10 = 6,
2^5 mod 10 = 2, 2^6 mod 10 = 4, …
求出i-k之后容易得到 2^(i-k) mod 10
3) f(n!) mod 10 = ((f(1) mod 10) * (f(2) mod 10) * … * (f(n) mod 10)) － (b)
f(i) mod 10有1，3，7，9四种可能，若能得到f(i) mod 10, i=1..n中3，7，9的个数
(b)式化为：f(n!) mod 10 = (3^a mod 10)*(7^b mod 10)*(9^c mod 10) － (c)
由于3，7，9的幂的最后一位也是循环的，(c)式容易求出。
4) 求(c)式中a, b, c的值
将f(i), i=1..n按i/f(i)的值分组，
当i/f(i)=1时（即i的因子中不含2和5），3,7,9的个数为n/10+a，a=(n%10>=3或7或9)
当i/f(i)=2^u*5^v时，3,7,9的个数为n/(2^u*5^v)/10+a，a=(n/(2^u*5^v)%10>=3或7或9)
把各组3,7,9的个数分别累加可得。
原文:
For this problem we provide output files for both data sets as well as three p
rograms. The first program is very simple but also very inefficient and can be
used to solve only easy data set. The second program runs in time O(N 3) wher
e N is number of digits of a input number. Since the difficult input data set
contained numbers with N=91 digits, it is possible to use this program for sol
ving it. There is still another, more efficient program working in time O(N 2)
, which we present as well.
The first program
Consider the number N! factored into product of powers of prime numbers. It me
ans N!=2i * 3j * 5k * 7l * … Note, that for each N>1 the power i is greater
than k. It means, that the last non-zero digit of N! is the same as the last d
igit of N! / (2k * 5k). Therefore we can compute the result using the equation
:
(N! / (2k * 5k)) mod 10 = ((N! / (2i * 5k)) mod 10 * 2i-k mod 10) mod 10
Number i can be obtained easily – we will divide each a=1,2,…,N by 2 until t
he resulting number is not divisible by 2 and after each division we will add
one to the variable i. Number k can be obtained in the same manner. Let f(i) d
enotes the number which we obtain by dividing i by the 2a * 5b where a and b a
re the highest numbers such that the i is divisible by this product. Number (N
! / (2i * 5k)) mod 10 is equal to f(N!) mod 10 and can be computed as f(1) * f
(2) * … * f(N) mod 10. We will perform operation mod 10 after each multiplic
ation in order to keep the resulting number as small as possible.
The advantege of this approach is that we do not need to implement arithmetics
of large numbers. Some ideas used here are used in the second, more efficient
program, as well.
The second program
The second program also computes the result as (2i-k mod 10 * f(N!) ) mod 10.
Numbers i and k are computed much more efficiently. More precisely
i=N div 2 + (N div 2) div 2 + ((N div 2) div 2) div 2 + …
(We get zero after finite number of divisions.) Number k can be computed in th
e same way. After that we can compute i-k and we need to find 2i-k mod 10. Obs
erve, that
21 mod 10 = 2, 22 mod 10 = 4, 23 mod 10 = 8, 24 mod 10 = 6, 25 mod 10 = 2, 26
mod 10 = 4, …
i.e. the period is 4 and we need only to compute (i-k) mod 4 and then to find
corresponding last digit. This observation can help us to simplify computation
of i and k – we do not need their exact values (that can be long) but we need
only (i-k) mod 4.
We have shown how to compute 2i-k mod 10. Now let us consider f(N!) mod 10 = (
(f(1) mod 10) * (f(2) mod 10) * … * (f(N) mod 10)) mod 10. Note, that f(i) m
od 10 is always 1,3,7 or 9. If we knew, how many 3,7,9 are among (f(1) mod 10)
, (f(2) mod 10), …, (f(N) mod 10), we could compute 3a mod 10, 7b mod 10, 9c
mod 10 in the similar way as we did for 2i-k (last digits of powers of 3,7,9
are also periodical).
To compute the number of 3,7,9 among (f(1) mod 10), (f(2) mod 10), …, (f(N)
mod 10) is not so easy. We will divide numbers 1,2,…,N into groups so, that
in each group are numbers with same quotient i/f(i) and we will compute number
of 3,7,9 among (f(i) mod 10) for each such group separatelly (there are O(N2)
such groups). First, let us consider a group in which i/f(i)=1. This is the g
roup of all numbers not divisible by 2 and 5. The number of 3,7,9 in this grou
p is the same as number of 3,7,9 among 1 mod 10, 2 mod 10, …, N mod 10. This
number can be counted easily – it is N div 10 + a where a is 1 if the last di
git of N is at least 3 (resp. at least 7 or at least 9). Now let us consider a
group in which i/f(i)=L (where L=2a * 5b). We obtain this group by taking eac
h L-th number from the sequence 1,2,3,… and dividing it by L. It means that
number of 3,7,9 for this group will be the same as the number of 3,7,9 among 1
mod 10, 2 mod 10, …, (N div L) mod 10.
Now we know everything we needed for construction of a program. Since numbers
in the input file are long, we need to implement arithmetics for long numbers.
However, by careful implementation we can achieve that only division of a lon
g number by small integer is necessary.
The third program.
Description of the algorithm used in this program will be available later.