POJ 1150 The Last Non-zero Digit 数论+容斥
题目地址:
POJ 1150
题意：
求排列P(n, m)后面第一个非0的数。
分析：
为了熟悉题目中的理论。我先做了俩0基础的题目：
POJ 1401。题解见：POJ
1401 && ZOJ 2202 Factorial 阶乘N!的末尾零的个数
NYOJ 954。题解见：NYOJ
954 求N!二进制末尾几个0
这题想了一下。十进制末尾几个0能够转化为几个5因子。二进制最后一位非0能够转化为2因子。可是10进制就不行了，并且这个不是单单N!。而是n!/m!。orz。
实在太弱仅仅能研究题解，推荐SCAU_Lyon巨巨的题解和abilitytao巨巨的题解。
然后我坐在电脑前面看了一晚上题解，最终。我发现我太弱了，我好不easy有点看懂了。
大概讲一下吧。
我们要把排列转化成前面两题的形式。
P(n, m) = n!/(n-m)!，我们让m = n - m直接按n!/m!做，也就是求m∗(m+1)∗(m+2)∗....∗n了。
这时候，我们仅仅要统计在[m, n]这个范围里面的数的最后一位即可了，假设直接去暴力会跪。由于我们不仅要统计每一个数的最后一位，另一些2和5因子混在数中，我们还要消掉那些因子，然后取末位。
于是要把2和5抽出来，然后就仅仅剩3,7,9，统计抽完后的3,7,9，然后还得记得：由于这里面2可能会比5多，所以要把多出来的2算出来。
仅仅要知道怎样统计n!，就能统计排列。
个中计算有非常厉害的技巧，表示orz。
一、计算n!中消除2,5后末位为x的公式为：
f(n, x) = n/10 + (n%10>=x) + f(n/2, x) + f(n/2, 5) - f(n/10, x).
解释下：
1. x限定3,7,9。
2. n/10 + (n%10>=x)也就是：每十个数以内末数字是3,7,9在没有除去2和5两种因子前都仅仅会出现一次。
3. 加上抽出2和5后的子问题。（这里跟前面两题原理一样）
4. 抽出2和5的时候，会多抽出了一次10，这时候就要用容斥定理减去。
二、然后计算多余的2就比較easy理解了。就跟前面俩题一样。求出2的个数和5的个数。减一下就是n!中多出来的2的个数了。
三、然后我们就能得到[m,n]中抽出2,5后末位为3,7,9的个数，以及多出来的2的个数了。
这时候假设直接while(cnt--)去算可能会超时+爆范围。
我们能够发现2^n,3^n,7^n,9^n的末位都是有规律可寻的。于是就能直接算了。
具体细节见代码。
代码：
/*
* Author: illuz <iilluzen[at]gmail.com>
* File: 1150.cpp
* Create Date: 2014-05-26 22:28:45
* Descripton:
*/
#include <cstdio>
#include <cstring>
const int N = 2e5;
int cnt3, cnt7, cnt9, cnt2;
int n, m;
int rec[10][N];
// 计算n!中消除2,5后末位为x的数量
int f(int n, int k) {
if (n < 1)
return 0;
if (n < N && rec[k][n] != -1)
return rec[k][n];
int ret = n / 10 + (n % 10 >= k) + f(n / 2, k) + f(n / 5, k) - f(n / 10, k);
if (n < N)
rec[k][n] = ret;
return ret;
}
// 多出来的2的个数
int more(int n) {
int num2 = 0, num5 = 0;
int t = n;
while (t != 0) {
num2 += t / 2;
t /= 2;
}
while (n != 0) {
num5 += n / 5;
n /= 5;
}
return num2 - num5;
}
int main()
{
memset(rec, -1, sizeof(rec));
while (~scanf("%d%d", &n, &m)) {
if (m == 0) {
puts("1");
continue;
}
m = n - m;
cnt2 = more(n) - more(m);
cnt3 = f(n, 3) - f(m, 3);
cnt7 = f(n, 7) - f(m, 7);
cnt9 = f(n, 9) - f(m, 9);
// printf("%d %d %d %d
", cnt2, cnt3, cnt7, cnt9);
// 2 4 8 6
if (cnt2-- == 0)
cnt2 = 1;
else if (cnt2 % 4 == 0)
cnt2 = 2;
else if (cnt2 % 4 == 1)
cnt2 = 4;
else if (cnt2 % 4 == 2)
cnt2 = 8;
else
cnt2 = 6;
// 1 3 9 7
if (cnt3 % 4 == 0)
cnt3 = 1;
else if (cnt3 % 4 == 1)
cnt3 = 3;
else if (cnt3 % 4 == 2) cnt3 = 9;
else
cnt3 = 7;
// 1 7 9 3
if (cnt7 % 4 == 0)
cnt7 = 1;
else if (cnt7 % 4 == 1)
cnt7 = 7;
else if (cnt7 % 4 == 2)
cnt7 = 9;
else
cnt7 = 3;
// 1 9
if (cnt9 % 2 == 0)
cnt9 = 1;
else
cnt9 = 9;
printf("%d
", cnt2 * cnt3 * cnt7 * cnt9 % 10);
}
return 0;
}