題意：x、y、k、b。在[x,y]范圍內的b進制數能分成k個b進制位權和的數有多少個。
思路：
dp[site][n][k][b] n就代表已經分成了幾個。
其實就是把數轉換成對應的進制
然後這時候len不再是原來的那麼簡單。
應該是如果是邊界的話取 當前位和1的最小值
不是的話 就取1
因為這位上有數說明這位可以被分走 所以這位上的數多少他都是1
然後就是判斷是否是邊界 要判斷到是不是等於這個位上的數
而不是等於len。
代碼：
#include"cstdlib"
#include"cstdio"
#include"cstring"
#include"cmath"
#include"queue"
#include"algorithm"
#include"iostream"
using namespace std;
//2014年9月24日19:51:00
int dp[35][22][22][12];
int num[35];
int dfs(int site,int n,int k,int m,int f)
{
if(site==0) return n==k;
if(!f&&~dp[site][n][k][m]) return dp[site][n][k][m];
int len=f?min(num[site],1):1;
int ans=0;
for(int i=0;i<=len;i++)
{
if(i) ans+=dfs(site-1,n+1,k,m,f&&i==num[site]);
else ans+=dfs(site-1,n,k,m,f&&i==num[site]);
}
if(!f) dp[site][n][k][m]=ans;
return ans;
}
int solve(int x,int k,int m)
{
int cnt=0;
while(x)
{
num[++cnt]=x%m;
x/=m;
}
return dfs(cnt,0,k,m,1);
}
int main()
{
int x,y,k,m;
memset(dp,-1,sizeof(dp));
while(scanf("%d%d%d%d",&x,&y,&k,&m)!=-1)
{
printf("%d\n",solve(y,k,m)-solve(x-1,k,m));
}
return 0;
}
//2014年9月24日19:58:31
