数位dp
数位dp是一种用于计数的dp，通常是用来求在满足某种约束条件下，求有多少个数或者各个数码的出现次数等。又因为所求范围一般都非常大，朴素的算法会超时，因此用数位dp来求解。约束条件大多都包含区间[l,r]以及其他的因题而异的约束条件。
数位dp其实也是枚举，只不过和普通的从0开始逐渐+1枚举数的大小不一样，它是在数位上进行枚举，比如在数字n的第i个位置上，在i前面的位置上的数都已经满足条件时，枚举第i位可能的取值。
你可能会发现，这数位枚举不也算是普通的枚举吗？这就是数位dp优化(dp的那种优化)的地方，它优化的话可以把当前位数之后的所有枚举状态直接跳过。
板子
在常用的dp中，把数字n用数组a逆序表示，下标从0开始。对于数组a的第pos个位置，用dp[i]表示前i-1位数字中，在无 1.前导零 2.各个位数的枚举限制 等约束条件下满足题意的解为多少。具体看代码。
对于每个题目，一定要搞清楚dp[i]的值，是在满足哪些条件，不考虑哪些条件下解的数目，
dp[i]:第i位在没有limit，pre等限制条件下的解的个数
pre:上一位的有关信息，可能为是否有前导零，也可能为其它信息(比如不要62里pre就是上一位是否为6)
limit:当前位数(即pos位)的枚举范围是否受到限制，不受限的话就是0-9；受限的话就是0-a[pos]
这是不要62的题解
#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
int l,r;
int a[20];
ll dp[20][2];
ll dfs(int pos, int pre, bool limit){ //该函数的功能：求满足各参数所约束的环境下，有多少解。
//pos表示位数， pre表示是否有前导零
//limit表示在当前函数状态下，第pos位数的枚举上限是否受限
//若不受限，则枚举范围0-9；否则位a[pos].
if (pos==-1) return 1; //各个位数都已枚举完毕，递归终止条件因题而异。
/**/if (!limit && dp[pos][pre]!=-1) return dp[pos][pre];
//前面讲过dp[i]位没有limit这个限制下的解(可能还会加上pre限制)
//前两行是优化，看能否提前结束掉该层递归
/* 递归主体 */
int up = limit? a[pos]:9; //上限
ll ans = 0;
for (int i=0;i<=up;i++){
if (i==4) continue; //4和62为约束条件
if (pre && i==2) continue; //这里的pre表示前一位是否为6，若前一位是6，这一位就不能为2了。
ans += dfs(pos-1, i==6, limit && i==a[pos]);
}
/**/if (!limit) dp[pos][pre] = ans; //ans值是否可以赋给dp？ ****
//在满足!limit还可能包含(!pre)等条件下才能赋值，这里也是数位dp的优化之处
return ans;
}
ll solve(int n){
memset (dp, -1, sizeof dp);
memset (a, 0, sizeof a);
int pos = 0;
while (n){
a[pos++] = n % 10;
n /= 10;
}
return dfs(pos-1, 0, true); //从最后一位开始枚举，固然前一位不是6， limit是true
}
int main(){
while (cin >> l >> r){
if (!l && !r) break;
cout << solve(r) - solve(l-1) << endl;
}
return 0;
}洛谷P2602 数字计数
输出区间内各个数码的出现次数，这道题目好像有特殊的简单做法，但我还是坚持用板子写了，，有很多值得注意的地方。
写的不是很好，我是对每个数码一一进行操作的，，同时还要对0特殊判别。
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long ll;
ll a[200];
ll dp[200];
ll dfs(int pos, bool pre, bool limit, ll now, int digit){ //pos位数，pre是否有前导零，now是在前面的递归中，数码digit出现的次数
if (pos==-1) return now;
if (!limit && !pre && dp[pos]!=-1) return now*pow(10,pos+1)+dp[pos];
//递归终止条件一定要多注意一下，因为求的是数码的出现次数，和求有多少个数不同。
int up = limit? a[pos]:9;
ll ans = 0;
for (int i=0;i<=up;i++){
int tmp = now;
if (digit==0){
tmp = (pre?(i==0 && pos==0):now+(i==digit));
}else tmp = now+(i==digit);
ans += dfs(pos-1, pre && (i==0) && (pos!=0), limit && i==a[pos], tmp, digit);
}
if (!limit && (digit!=0 || !pre)) dp[pos] = ans; // 这里和前两行一样重要！！！ 回想板子开头提醒的！！！！！
return ans;
}
ll solve(ll n, int base, int digit){
if (n==0){
if (digit) return 0;
else return 1;
}
memset (dp, -1, sizeof dp);
memset (a, 0, sizeof a);
int pos = 0;
while (n){
a[pos++] = n % 10;
n /= 10;
}
return dfs(pos-1, true, true, 0, digit);
}
int main(){
ll l,r;
while (cin >> l >> r){
for (int i=0;i<10;i++){
cout << solve(r, 10, i) - solve(l-1, 10, i);
if (i!=9) cout << " ";
}
}
return 0;
}P4999 烦人的数学作业
计算[l, r]内每个数的数位和。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
ll dp[25], a[25], Pow[25];
ll dfs(int pos, bool limit, ll n){
if (pos==-1) return 0;
if (!limit && dp[pos]!=-1) return dp[pos];
int up = limit? a[pos]:9;
ll ans = 0;
for (int i=0; i<=up; i++){
if (limit && i==a[pos]) ans += (n%Pow[pos]+1)%mod*i%mod;
else ans += Pow[pos]%mod*i%mod;
ans += dfs(pos-1, limit && i==a[pos], n);
ans %= mod;
}
if (!limit) dp[pos] = ans;
return ans;
}
ll solve(ll n){
memset (dp, -1, sizeof dp);
ll tmp = n;
int pos = 0;
while (tmp){
a[pos++] = tmp%10;
tmp /= 10;
}
return dfs(pos-1, true, n);
}
int main(){
int t;
ll l, r;
Pow[0] = 1;
for (int i=1; i<=18; i++) Pow[i] = 10*Pow[i-1];
cin >> t;
while (t--){
cin >> l >> r;
cout << ((solve(r)-solve(l-1))%mod+mod)%mod << endl;
}
return 0;
}
/*
0 10000000000000
0 1000000000000000000
*/P4317 花神的数论题
设sum(i)表示i的二进制表示中1的个数
计算\prod_{i=1}^{N}{sum(i)}，先求出1的出现次数为x的数的个数，再快速幂求解。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 10000007;
ll n;
int a[64];
ll dp[64][64]; // dp[i][j] 表示前i位中1的个数为j的数的个数(在无limit限制的情况下)
ll sum[64];
ll pow_mod(ll a, ll b){
if (!a) return 0;
ll ans = 1;
while (b){
if (b&1) ans = ans*a%mod;
b >>= 1;
a = a*a%mod;
}
return ans;
}
ll dfs(int pos, bool limit, int x){ //1的个数为x的数的个数
if (x<0) return 0;
if (pos==-1)
return 0==x;
if (!limit && dp[pos][x]!=-1) return dp[pos][x];
int up = limit? a[pos]:1;
ll ans = 0;
for (int i=0; i<=up; i++){
ans += dfs(pos-1, limit && i==a[pos], x-(i==1));
}
if (!limit) dp[pos][x] = ans;
return ans;
}
ll solve(){
ll tmp = n, ans = 1;
int pos = 0;
while (tmp){
a[pos++] = tmp&1;
tmp >>= 1;
}
memset (dp, -1, sizeof dp);
memset (sum, 0, sizeof sum);
for (int i=2; i<=pos; i++){
sum[i] = dfs(pos-1, true, i);
ans = ans*pow_mod(i, sum[i])%mod;
}
return ans;
}
int main(){
while (cin >> n){
cout << solve() << endl;
}
return 0;
}
0 条评论