UVa 12683 Odd and Even Zeroes（数论+数字DP）

意甲冠军：要求小于或等于n号码（0<=n <= 1e18）尾数的数的阶乘0数为偶数

思考：当然不是暴力，因此，从数论。尾数0数为偶数，然后，它将使N阶乘5电源是偶数。（二指数肯定少5指数），乞讨N。阶乘5该指数是N/5+ N/25+N/125。

。

。。

以530为例。尝试着将转化为5进制即为 4110。那么5的指数就是 411+41+4 （5进制）easy发现要使这个数是偶数。就是要使5进制奇数位的个数为偶数。依据刚才那个加法，能够看出，最后结果的5进制的末位就是411+41+4 的末位即 4+1+1 即为原数最高位到最低第二位每一位的和，末二位依次类推。。。。

。

那么仅仅要做到这里。。。接下来就是数位DP的事了，DP[pos][parity][presum]

#include <iostream>

#include <cstdio>

#include <cstring>

#include <vector>

#include <string>

#include <algorithm>

#include <queue>

#include <set>

#include <map>

using namespace std;

typedef long long LL;

vector<int> digit;

#define REP(_,a,b) for(int _ = (a); _ <= (b); _++)

LL dp[30][2][2];

LL n;

LL dfs(int pos,int parity,int sum,bool done) {

    if(pos==0) {

        if(parity==0) {

            int sz = done?digit[pos]:4;

            return sz+1;

        }else{

            return 0;

        }

    }

    if(!done && dp[pos][parity][sum] != -1) return dp[pos][parity][sum];

    LL ret = 0;

    int end = done? digit[pos]:4;

    for(int i = 0; i <= end; i++) {

        ret += dfs(pos-1,(parity+(sum+i)&1)&1,(sum+i)&1,done&&i==end ) ;

    }

    if(!done) dp[pos][parity][sum] = ret;

    return ret;

}

LL solve(LL n) {

    if(n <= 4) return n+1;

    memset(dp,-1,sizeof dp);

    digit.clear();

    while(n) {

        digit.push_back(n%5);

        n /= 5;

    }

    return dfs(digit.size()-1,0,0,1);

}

int main(){

    while(~scanf("%lld",&n) && n !=-1) {

        printf("%lld\n",solve(n));

    }

    return 0;

}