AcWing1081 度的数量（数位dp）

题目描述

题目描述

思路

题目链接 关于数位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)。

树

细节方面详看代码。

AC代码

#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;
}