意甲冠军：有两个查询：

q=1。在[x,y]间隔，兑换b十进制，数字和m多少个月。

q=2。在[x,y]间隔，兑换b十进制，数字是m第一k的数目是多少（十进制），没有输出由给定的主题。

思维：

和比特的平均数dp如，第几个数的话就是二分推断。

然后就是按常理要开4维，就是dp[i][sum][b][m] i位，和为sum，b进制，最后和为m

可是开不下，所以开3维每次初始化。

注意一下：

1、每次都要初始化

2、x不一定小于y

3、是[x,y]不是(x,y]

代码：

#include"cstdlib"

#include"cstdio"

#include"cstring"

#include"cmath"

#include"stack"

#include"algorithm"

#include"iostream"

using namespace std;

__int64 dp[33][320][65],num[33];  // i位 和是sum 进制b 的关于m的答案 可是再替m开一维开不下。所以不能在外面初始化

__int64 dfs(__int64 site,__int64 sum,__int64 b,int f,__int64 m)

{

    if(site==0) return sum==m?1:0;

    if(!f&&dp[site][sum][b]!=-1) return dp[site][sum][b];

    __int64 len=f?

num[site]:b-1;

    __int64 ans=0;

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

    {

        ans+=dfs(site-1,sum+i,b,f&&i==len,m);

    }

    if(!f) dp[site][sum][b]=ans;

    return ans;

}

__int64 solve(__int64 x,__int64 b,__int64 m)

{

    int cnt=0;

    if(x<0) return 0;

    while(x)

    {

        num[++cnt]=x%b;

        x/=b;

    }

    return dfs(cnt,0,b,1,m);

}

int main()

{

    int cas=1;

    int q;

    while(scanf("%d",&q)!=-1)

    {

        __int64 x,y,b,m,k;

        memset(dp,-1,sizeof(dp));  //必须放里面

        printf("Case %d:\n",cas++);

        if(q==1)

        {

            scanf("%I64d%I64d%I64d%I64d",&x,&y,&b,&m);

            if(x>y) swap(x,y);

            printf("%I64d\n",solve(y,b,m)-solve(x-1,b,m));

        }

        else

        {

            scanf("%I64d%I64d%I64d%I64d%I64d",&x,&y,&b,&m,&k);

            x--;          //注意这里是求 [x,y]区间内的！

if(x>y) swap(x,y);

            __int64 ans=-1,s;

            s=solve(x,b,m);

            s+=k;

            __int64 l=x+1,r=y;

            while(l<=r)

            {

                __int64 mid=(l+r)/2;

                if(solve(mid,b,m)>=s)

                {

                    ans=mid;

                    r=mid-1;

                }

                else l=mid+1;

            }

            if(ans!=-1) printf("%I64d\n",ans);

            else puts("Could not find the Number!");

        }

    }

    return 0;

}