UVALive6575OddandEvenZeroes数位dp+找规律

题目链接：

Odd and Even Zeroes

Time Limit: 3000MS
#### 问题描述
In mathematics, the factorial of a positive integer number n is written as n! and is defined as follows:
n! = 1 × 2 × 3 × 4 × . . . × (n − 1) × n =
∏n
i=1
i
The value of 0! is considered as 1. n! grows very rapidly with the increase of n. Some values of n!
are:
0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
10! = 3628800
14! = 87178291200
18! = 6402373705728000
22! = 1124000727777607680000
You can see that for some values of n, n! has odd number of trailing zeroes (eg 5!, 18!) and for some
values of n, n! has even number of trailing zeroes (eg 0!, 10!, 22!). Given the value of n, your job is to
find how many of the values 0!, 1!, 2!, 3!, . . . ,(n − 1)!, n! has even number of trailing zeroes.

#### 输入
Input file contains at most 1000 lines of input. Each line contains an integer n (0 ≤ n ≤ 1018). Input
is terminated by a line containing a ‘-1’.

For each line of input produce one line of output. This line contains an integer which denotes how

many of the numbers 0!, 1!, 2!, 3!, . . . , n!, contains even number of trailing zeroes.

sample input

2

3

10

100

1000

2000

3000

10000

100000

200000

-1

sample output

3

4

6

61

525

1050

1551

5050

50250

100126

求0!,1!,...,n!里面末尾有偶数个零的数的个数。

将n按五进制展开，发现如果只有当偶数位权上的数的和为偶数时，n的末尾有偶数个0。所以将问题转换成统计小于n的偶数位权为偶数的数有多少个。

这个用数位dp可以解决。

#include iostream
#include cstdio
#include cstring
#include vector
#include map
#define bug(x) cout #x = x endl;
using namespace std;
const int maxn = 66;
typedef long long LL;
int arr[maxn],tot;
//dp[i][0]表示前i位中偶数位上的和为偶数的数的个数
//dp[i][1]表示前i位中偶数位上的和为奇数的数的个数
LL dp[maxn][2];
LL dfs(int len, int type,bool ismax,bool iszer) {
if (len == 0) {
if(!type) return 1LL;
else return 0LL;
}
if (!ismax dp[len][type] 0) return dp[len][type];
LL res = 0;
int ed = ismax ? arr[len] : 4;
for (int i = 0; i = ed; i++) {
if(len 1){
res+=dfs(len-1,type,ismax i == ed,iszer i==0);
}
else{
if((i 1)) res+=dfs(len-1,type^1,ismax i == ed,iszer i==0);
else res+=dfs(len-1,type,ismax i == ed,iszer i==0);
}
}
return ismax ? res : dp[len][type] = res;
LL solve(LL x) {
tot = 0;
//五进制
while (x) { arr[++tot] = x % 5; x /= 5; }
return dfs(tot,0, true,true);
int main() {
LL x;
memset(dp,-1,sizeof(dp));
while (scanf( %lld , x)==1 x!=-1) {
printf( %lld\n , solve(x));
}
return 0;
}