题目链接 关于数位dp有两个技巧:第一是可以使用前缀和的思想,对于求区间 [ L , R ] [L,R] [L,R]内符合要求的数,我们可以使用 f [ R ] − f [ L − 1 ] f[R]-f[L-1] f[R]−f[L−1]来获得答案。第二是使用树的形式来考虑。
对于这道题来说,从高位开始,依次考虑每一位。 对于第 n − 1 n-1 n−1位来说,我们可以分成两个分支: 0 − a n − 1 − 1 0 -a_{n-1}-1 0−an−1−1和 a n − 1 a_{n-1} an−1。对于左分支来说,有两种选择,如果放1,则其他各位放1的方案数为 C ( n − 1 , k − 1 ) C(n-1,k-1) C(n−1,k−1),如果不放1,则其他各位放1的方案数为 C ( n − 1 , k ) C(n-1,k) C(n−1,k)。
细节方面详看代码。
#include "iostream"
#include "cstring"
#include "string"
#include "vector"
#include "cmath"
#include "algorithm"
#include "map"
#include "set"
#include "queue"
#include "stack"
#include "cassert"
#include "unordered_map"
using namespace std;
#define fi first
#define se second
#define PB push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) begin(a),end(a)
#define rep(x,l,u) for(ll x=l;x<u;x++)
#define rrep(x,l,u) for(ll x=l;x>=u;x--)
#define sz(x) x.size()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define seteps(N) setprecision(N)
#define uni(x) sort(all(x)), x.erase(unique(all(x)), x.end())
#define lson (ind<<1)
#define rson (ind<<1|1)
#define DEBUG(x) cout<<" "<<x<<endl;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 lll;
typedef pair<int,int> PII;
typedef pair<char,char> PCC;
typedef pair<double,double> PDD;
typedef pair<ll,ll> PLL;
const int N=35;
const int M=10;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const lll oone=1;
const double eps=1e-6;
const double pi=acos(-1);
int c[N][N];
int k,b;
//预处理组合数
void init(){
rep(i,0,N){
rep(j,0,i+1){
if(!j) c[i][j]=1;
else c[i][j]=c[i-1][j]+c[i-1][j-1];
}
}
}
int f(int n){
if(!n) return 0;//如果为0,则无法满足题意
vector<int> nums;
while(n) nums.PB(n%b),n/=b;
int res=0,last=0;
rrep(i,sz(nums)-1,0){
int x=nums[i];
if(x){
res+=c[i][k-last];
//当x>1时,才会有放1的情况,由于放1,所以走不了右分支,直接break
if(x>1){
if(k-last-1>=0) res+=c[i][k-last-1];
break;
}else last++;
}
if(last>k) break;
if(!i && last==k) res++;
}
return res;
}
void solve(){
init();
int l,r;
cin>>l>>r>>k>>b;
cout<<f(r)-f(l-1)<<endl;
}
int main(){
IOS;
//freopen("data.in", "r", stdin);
//freopen("data.out", "w", stdout);
//int t;cin>>t;
//while(t--)
solve();
return 0;
}