Codeforces 1073 E - Segment Sum

思路:

数位dp

我们平时做的数位dp都是求满足条件的数的个数, 这里要求满足条件的数的和

只要在原来的基础上求每一位的贡献就可以了,所以传参数时要传两个

代码:

#pragma GCC optimize(2)

#pragma GCC optimize(3)

#pragma GCC optimize(4)

#include<bits/stdc++.h>

using namespace std;

#define fi first

#define se second

#define pi acos(-1.0)

#define LL long long

//#define mp make_pair

#define pb push_back

#define ls rt<<1, l, m

#define rs rt<<1|1, m+1, r

#define ULL unsigned LL

#define pll pair<LL, LL>

#define pli pair<LL, int>

#define pii pair<int, int>

#define piii pair<pii, int>

#define mem(a, b) memset(a, b, sizeof(a))

#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);

//head

const int MOD = ;

int k;

pll dp[][];

int a[], tot;

LL pw[];

pll dfs(int pos, int s, bool zero, bool limit) {

    if(!pos) return {__builtin_popcount(s) <= k, };

    if(!limit && !zero && ~dp[pos][s].fi) return dp[pos][s];

    int up = ;

    if(limit) up = a[pos];

    pll ans = {, };

    for (int i = ; i <= up; i++) {

        pll res;

        if(zero && i == ) res = dfs(pos-, s, zero, limit&&i==up);

        else res = dfs(pos-, s|(<<i), zero&&i==, limit&&i==up);

        (ans.fi = ans.fi + res.fi) %= MOD;

        (ans.se = ans.se + res.se + i*res.fi%MOD*pw[pos-]%MOD) %= MOD;

    }

    if(!limit && !zero) dp[pos][s] = ans;

    return ans;

}

void init() {

    pw[] = ;

    for (int i = ; i < ; i++) pw[i] = (pw[i-] * ) % MOD;

    for (int i = ; i < ; i++)

        for (int j = ; j < ; j++) dp[i][j].fi = dp[i][j].se = -;

}

LL solve(LL n) {

    tot = ;

    init();

    while(n) {

        a[++tot] = n % ;

        n /= ;

    }

    return dfs(tot, , , ).se;

}

int main() {

    LL l, r;

    scanf("%lld %lld %d", &l, &r, &k);

    printf("%lld\n", (solve(r) - solve(l-) + MOD) % MOD);

    return ;

}

秒客网

Codeforces 1073 E - Segment Sum

相关文章