数位dp（二）

[[ slider_text ]]

[[ item.c ]]

发布时间 2024-06-13 作者：zhangminchen 来源：算法小站

数位dp

## 数位 dp 解决乘法问题
**问题描述**
**[快速乘法](http://hihocoder.com/contest/challenge29/problem/2)**
将$$x \times a$$替换成若干个二进制幂的混合运算
$$(x \ll a_0) op_1(x \ll a_1) op_2 (x \ll a_2) \cdots op_n(x \ll a_n)$$，$$op$$是`+ 或者 -`
`移位，+，-`三种运算都需要一个单位的时间，现在给定$$a$$的二进制形式
求实现$$x \times a$$**最少**需要多少单位的时间

### 算法分析
![](/media/content_img/digitdp2-01-1.png)
根据以上分析，这启发我们根据**数位 dp**来设计算法

![](/media/content_img/digitdp2-01-2.png)
### 算法实现
```bash
int main() {
	// 以字符串形式输入数，省略输入
	
    vector<int> dp(maxn, inf);
    dp[0] = 0;

vector<int> s(maxn, 0);
    for (int i = 1; i <= n; i++) s[i] = s[i-1] + (str[i] == '0');
    
    int j = -1;
    for (int i = 1; i <= n; i++) {
        if (str[i] == '0') {
            chmin(dp[i], dp[i-1]);
        }
        else {
            chmin(dp[i], dp[i-1] + 1);
            if (j-1 >= 0) chmin(dp[i], dp[j-1] + s[i] - s[j-1] + 2);

if (j == -1 ||
                dp[i-1]+s[i+1]-s[i-1]+2 <= dp[j-1]+s[i+1]-s[j-1]+2) j = i;
        }
    }
    int ans = dp[n]*2 - 1;
    printf("%d\n", ans);
}
```

## CCPC Changchun 2020 D
**[CCPC Changchun 2020 D. Meaningless Sequence](https://codeforces.com/gym/102832/problem/D)**
**问题描述**
`cnt(n)`表示`n`的二进制中`1`的个数，$$a_n = c^{cnt(n)}$$

求$$\sum_{i = 0}^{n} a_i$$，其中$$n$$按二进制给出，不超过$$2^{3000}$$

### 算法分析

原题意给出 $$a\_{n} = c \cdot \max\_{0\leqslant i < n} a\_{n \textbf{ and } i}$$，要先考虑一下$$a_n$$等于多少

![](/media/content_img/digitdp2-02-1.png)

实际上就是看**有几个满足条件的数**，对答案的贡献就是多少
![](/media/content_img/digitdp2-02-2.png)

### 算法实现
```bash
int main() {
    freopen("input.txt", "r", stdin);
    string str;
    int c;
    cin >> str >> c;

int n = str.size();
    vector<mint> pw(maxn, 0);
    pw[0] = 1;
    for (int i = 1; i <= n; i++) pw[i] = pw[i-1] * mint(c+1);

mint ans = 0, pre = 1;
    for (int i = 0; i < n; i++) {
        if (str[i] == '1') {
            ans += pre * pw[n-1-i];
            pre *= mint(c);
        }
    }
    ans += pre;
    printf("%d\n", ans.val());
}
```

## CCPC Jinan 2020
**[CCPC Jinan 2020 L. Bit Sequence](https://ac.nowcoder.com/acm/contest/10662/L)**
**问题描述**
令$$f(x)$$表示$$x$$二进制表示中$$1$$的个数
现在给你一个序列$$a\_0, a\_1, \cdots, a\_{m-1}$$，问你有多少个数$$x \in [0, L]$$满足
$$\forall i \in [0, m-1], f(x+i) \bmod 2 = a\_i$$

### 算法分析
先翻译一下题目讲什么事情，给你一些数`a[0], a[1], ..., a[m-1]`，对应成一个**无穷序列**
`0 1 1 0 1 0 0 1 0 1 1 0 ....`，每一个`0/1`表示$$a_i$$二进制中`1`的个数的**奇偶性**
然后给你一段值，`x+i = 0 1 0 0`，问这段值在满足$$x \leqslant [0, L]$$的条件下，**出现了几次**

>  这是一个 Thue-Morse 序列，只需要关心 1 出现的次数的奇偶性

![](/media/content_img/digitdp2-03-1.png)
![](/media/content_img/digitdp2-03-2.png)
![](/media/content_img/digitdp2-03-3.png)
![](/media/content_img/digitdp2-03-4.png)

### 算法实现
```bash
typedef pair<ll, vector<int> > PII;

void solve() {
    int m;
    ll L;
    scanf("%d%lld", &m, &L);
    vector<int> a(m, 0);
    for (int i = 0; i < m; i++) scanf("%d", &a[i]);

function<vector<int>(vector<int>)> reduce = [&](vector<int> a) -> vector<int> {
        vector<int> b;
        for (int i = 0; i < a.size(); i += 2) {
            b.push_back(a[i]);
            if (i+1 < a.size() && a[i] == a[i+1]) return vector<int> (0);
        } 
        return b;
    };

// dp memory
    map<pair<ll, vector<int> >, ll> dp;

function< ll(ll, vector<int> ) > calc = [&](ll L, vector<int> a) -> ll {
        if (a.empty()) return 0;
        if (dp.count(PII( L, a ))) return dp[ PII(L, a) ];

if (L <= 0) {
            ll res = 1;
            for (int i = 0; i < a.size(); i++) {
                if (__builtin_parity(i) != a[i]) {
                    res = 0;
                    break;
                }
            }

return dp[PII(L, a)] = res;
        }

// reduce a
        ll ans = 0;
        ans += calc(L/2, reduce(a));

auto b = a;
        b.insert(b.begin(), a[0] ^ 1);
        ans += calc((L-1)/2, reduce(b));

return dp[PII(L, a)] = ans;
    };

ll ans = calc(L, a);
    printf("%lld\n", ans);
}
```

上一篇：数位dp（一）下一篇：区间dp在算法竞赛中的应用

看完文章有啥想法