E38 数位DP 度の数量

/* 基本思路：
题意可变为：求[X,Y]中的整数转换为b进制，其中有k个1的整数有多少个
发现可以用组合计算解决，具体看下面注释
*/
#include<bits/stdc++.h> //by: hansang522
using namespace std;
const int N=35;
int c[N][N], a[N], b, K;
int calc(int x){ //[1, x]中有k个1的整数的数量
    int len=0;
    while(x>0) a[++len]=x%b, x/=b; //将x 转化为b进制
    int t=K, ans=0; //t 表示还剩多少个1
    for(int i=len; i>=1; i--){
        if(a[i]==1) ans+=c[i-1][t]; 
        //当前位置上只有一个1，可以将1～i-1都填上1，从中选t个
        if(a[i]>=2){
            ans+=c[i][t];
            //当前位置上>1，可以将1～i都填上1，从中选t个
            return ans;
            //后面再计算就重复了
        }
        if((t-=a[i])<0) return ans;
        //因为当前a[i]的答案都是建立在len～i+1的a数组上的，
        //所以每次循环最后都要-a[i]
        //不是<=0是防止i=1的情况计算错误
    }
    return ans+(!t);
    //t=0时x本身就是一个答案
}
int main(){
    //freopen("a.in", "r", stdin);
    c[0][0]=1;
    for(int i=1; i<=32; i++){
        c[i][0]=c[i][i]=1;
        for(int j=1; j<i; j++) c[i][j]=c[i-1][j-1]+c[i-1][j];
        //计算组合数
    }
    int x, y; scanf("%d%d%d%d", &x, &y, &K, &b);
    printf("%d\n", calc(y)-calc(x-1)); //[x, y]中有k个1的整数的数量
    return 0;
}

E38 数位DP 度的数量

/* 基本思路：
题意可变为：求[X,Y]中的整数转换为b进制，其中有k个1的整数有多少个
发现可以用组合计算解决，具体看下面注释
*/
#include<bits/stdc++.h> //by: hansang522
using namespace std;
const int N=35;
int c[N][N], a[N], b, K;
int calc(int x){ //[1, x]中有k个1的整数的数量
int len=0;
while(x>0) a[++len]=x%b, x/=b; //将x 转化为b进制
int t=K, ans=0; //t 表示还剩多少个1
for(int i=len; i>=1; i--){
if(a[i]==1) ans+=c[i-1][t];
//当前位置上只有一个1，可以将1～i-1都填上1，从中选t个
if(a[i]>=2){
ans+=c[i][t];
//当前位置上>1，可以将1～i都填上1，从中选t个
return ans;
//后面再计算就重复了
}
if((t-=a[i])<0) return ans;
//因为当前a[i]的答案都是建立在len～i+1的a数组上的，
//所以每次循环最后都要-a[i]
//不是<=0是防止i=1的情况计算错误
}
return ans+(!t);
//t=0时x本身就是一个答案
}
int main(){
//freopen("a.in", "r", stdin);
c[0][0]=1;
for(int i=1; i<=32; i++){
c[i][0]=c[i][i]=1;
for(int j=1; j<i; j++) c[i][j]=c[i-1][j-1]+c[i-1][j];
//计算组合数
}
int x, y; scanf("%d%d%d%d", &x, &y, &K, &b);
printf("%d\n", calc(y)-calc(x-1)); //[x, y]中有k个1的整数的数量
return 0;
}