[POJ 2282] The Counting Problem

[题目链接]

http://poj.org/problem?id=2282

[算法]

数位DP

[代码]

#include <algorithm>

#include <bitset>

#include <cctype>

#include <cerrno>

#include <clocale>

#include <cmath>

#include <complex>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <ctime>

#include <deque>

#include <exception>

#include <fstream>

#include <functional>

#include <limits>

#include <list>

#include <map>

#include <iomanip>

#include <ios>

#include <iosfwd>

#include <iostream>

#include <istream>

#include <ostream>

#include <queue>

#include <set>

#include <sstream>

#include <stdexcept>

#include <streambuf>

#include <string>

#include <utility>

#include <vector>

#include <cwchar>

#include <cwctype>

#include <stack>

#include <limits.h>

using namespace std;

int i;

long long a,b;

long long f[][][];

inline void dp(long long m)

{

        long long i,j,k,x;

        memset(f,,sizeof(f));

        f[][][] = ;

        for (i = ; i <= ; i++)

        {

                for (j = ; j <= ; j++)

                {

                        for (k = ; k <= i; k++)

                        {

                                if (j != m)

                                {

                                        for (x = ; x <= ; x++)

                                                f[i][j][k] += f[i - ][x][k];

                                } else if (k >= )

                                {

                                        for (x = ; x <= ; x++)

                                                f[i][j][k] += f[i - ][x][k - ];

                                }

                        }

                }

        }

}

inline long long calc(long long x,long long t)

{

        long long i,j,k,len = ;

        long long res = ;

        long long cnt = ;

        long long a[];

        memset(a,,sizeof(a));

        while (x != )

        {

                a[++len] = x % ;

                x /= ;

        }

        reverse(a + ,a + len + );

        for (i = ; i <= len; i++)

        {

                for (j = ; j <= ; j++)

                {

                        for (k = ; k <= len - i + ; k++)

                                res += f[len - i + ][j][k] * k;

                }

        }

        for (i = ; i <= len; i++)

        {

                for (j = ; j < a[i]; j++)

                {

                        if (i ==  && !j) continue;

                        for (k = cnt; k <= len; k++)

                        {

                                res += f[len - i + ][j][k - cnt] * k;

                        }

                }

                if (a[i] == t) cnt++;

        }

        return res;

}

int main()

{

        while (scanf("%lld%lld",&a,&b) && (a || b))

        {

                if (a > b) swap(a,b);

                for (i = ; i < ; i++)

                {

                        dp(i);

                        printf("%lld ",calc(b + ,i) - calc(a,i));

                }

                dp();

                printf("%lld\n",calc(b + ,) - calc(a,));

        }

        return ;

}

[POJ 2282] The Counting Problem的相关教程结束。