洛谷 - 2602
dp数组的类型不一定是int，要看维护的值是什么，这道题维护的是0～9数字出现的次数。
dfs1其实只有两种情况，且都可以直接返回。
- (limit=1)时，返回pos位后的数字；
- (limit=0)时，返回(10^{pos})。
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
typedef long long ll;
int a[20];
vector<ll> dp[20][2], state(10);
ll f[20];
ll dfs1(int pos, int limit) {
if(pos < 0) return 1;
if(!limit && f[pos] >= 0) return f[pos];
int up = limit ? a[pos]: 9;
ll res = 0;
for (int i = 0 ; i <= up; i++) {
res += dfs1(pos-1, limit&&i==up);
}
if(limit) return res;
return f[pos] = res;
}
vector<ll> dfs(int pos, int limit, int lead) {
if(pos < 0) return state;
if(!limit && !dp[pos][lead].empty())
return dp[pos][lead];
vector<ll> res(10);
int up = limit ? a[pos]: 9;
for (int i = 0; i <= up; i++) {
vector<ll> arr = dfs(pos-1, limit&&i==up, lead&&!i);
if(!lead || i) res[i] += dfs1(pos-1, limit&&i==up);
for (int d = 0; d <= 9; d++) {
res[d] += arr[d];
}
}
if(limit) return res;
return dp[pos][lead] = res;
}
vector<ll> solve(ll x) {
for (int i = 0; i < 20; i++) {
dp[i][0].clear();
dp[i][1].clear();
f[i] = -1;
}
int pos = 0;
while (x) {
a[pos++] = x % 10;
x /= 10;
}
return dfs(pos-1, 1, 1);
}
int main() {
ll a, b;
scanf("%lld %lld", &a, &b);
auto arr1 = solve(b), arr2 = solve(a-1);
for (int i = 0; i <= 9; i++) {
ll num = arr1[i] - arr2[i];
printf("%lld ", num);
}
}
CF - 55D
区间内有多少能被它每一个非零的数位整除的正整数？
初步的想法是暴力维护带权和对每一位（0～9）的取模，但发现这样不知道有哪些数字出现过，哪些没出现，也就是还要维护出现的数字，这个状态设计无疑是失败的。
那怎么设计出好的（易于转移的）状态？
考虑用数学方法优化，“被出现的每一位数字整除”等价于“被每一位数字的的最小公倍数整除”。
于是乎带权和对lcm(0..9)=2520取模就是了，而”每一位数字的最小公倍数“会出现最多48种（2520的因子数），离散化一下可以减少空间的开销。
注意这里带权和的转移方法，不知道为什么用数组预处理每一位的贡献wa了。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int gcd(int a, int b) {
return b==0?a:gcd(b,a%b);
}
inline int lcm(int a, int b) {
return a*b/gcd(a, b);
}
const int N = 2520; // lcm(1..9)
int mp[N+1], a[20];
ll dp[20][N][50];
int f[20][10];
inline ll dfs(int pos, int sum, int nlcm, bool limit) {
if(pos < 0) return sum % nlcm == 0;
if(!limit && dp[pos][sum][mp[nlcm]] != -1) return dp[pos][sum][mp[nlcm]];
int up = limit? a[pos]: 9;
ll res = 0;
for (int i = 0; i <= up; i++) {
if(i == 0) res += dfs(pos-1, sum * 10 % N, nlcm, limit&&i==up);
else res += dfs(pos-1, (sum*10 + i) % N, lcm(nlcm, i), limit&&i==up);
}
if(limit) return res;
return dp[pos][sum][mp[nlcm]] = res;
}
inline ll solve(ll x) {
int pos = 0;
while(x) a[pos++] = x % 10, x /= 10;
return dfs(pos-1, 0, 1, 1);
}
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
memset(dp, -1, sizeof(dp));
int cnt = 0;
for (int i = 1; i <= N; i++)
if(N % i == 0) mp[i] = ++cnt;
int T;
cin >> T;
while (T--) {
ll l, r;
cin >> l >> r;
cout << solve(r) - solve(l-1) << endl;
}
}
HDU - 4734
为避免初始化造成TLE，要将dp数组开为dp[pos][fx]，表示当位置为pos、剩余带权和为fx的数字数量。
这样，对多组测试，他们解决的仍然是重复的子问题，有点逆向思维的味道。
注意带权和的转移方式！
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int fa = 0, a[20], dp[20][5000];
int dfs(int pos, int limit, int fx) {
if(pos < 0) return 1;
if(!limit && dp[pos][fx] != -1) return dp[pos][fx];
int res = 0;
int up = limit? a[pos]: 9;
for (int i = 0; i <= up; i++) {
if(fx < i * (1<<pos)) break;
res += dfs(pos-1, limit&&i==up, fx-i*(1<<pos));
}
if(limit) return res;
return dp[pos][fx] = res;
}
int solve(int x) {
int pos = 0;
while(x) a[pos++] = x % 10, x /= 10;
return dfs(pos-1, 1, fa);
}
int main() {
memset(dp, -1, sizeof(dp));
int t, kase = 0;
scanf("%d", &t);
while (t--) {
int a, b;
fa = 0;
scanf("%d %d", &a, &b);
int bit = 1, tmp = a;
while(tmp) {
fa += bit * (tmp % 10);
bit <<= 1;
tmp /= 10;
}
printf("Case #%d: %d
", ++kase, solve(b));
}
}
HDU - 3709
一个数字如果是balance number，那么它有且仅有一个基准。
外围枚举基准的位置，分情况数位DP，不会有重复计算的问题。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[20];
ll dp[20][20][3000]; // sum开空间考虑极限情况
ll dfs(int pos, bool limit, int pivot, int sum) {
if(pos < 0) return !sum;
if(sum < 0) return 0;
if(!limit && ~dp[pos][pivot][sum]) return dp[pos][pivot][sum];
ll res = 0;
int up = limit? a[pos]: 9;
for (int i = 0; i <= up; i++) {
res += dfs(pos-1, limit&&i==up, pivot, sum + (pos-pivot) * i);
}
if(limit) return res;
return dp[pos][pivot][sum] = res;
}
ll solve(ll x) {
int pos = 0;
while(x) a[pos++] = x % 10, x /= 10;
ll res = 0;
for (int i = 0; i < pos; i++) { // 枚举pivot
res += dfs(pos-1, 1, i, 0);
}
return res - pos + 1; // 0只能被计算一次
}
int main() {
memset(dp, -1, sizeof(dp));
int T;
scanf("%d", &T);
while (T--) {
ll x, y;
scanf("%lld %lld", &x, &y);
printf("%lld
", solve(y) - solve(x-1));
}
}
SP - 10606
状态用三进制表示
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[20], pow3[10];
ll dp[20][2][60000];
vector<int> get(int state) {
vector<int> res(10);
int pos = 0;
while (state) {
res[pos++] = state % 3;
state /= 3;
}
return res;
}
int cal(vector<int> vec) {
int res = 0;
for (int i = 0; i <= 9; i++) {
res += vec[i] * pow3[i];
}
return res;
}
int update(int state, int digit) {
vector<int> vec = get(state);
if(vec[digit] == 2) {
vec[digit] = 1;
}
else {
++vec[digit] %= 2;
}
return cal(vec);
}
bool isbalanced(int state) {
vector<int> vec = get(state);
for (int i = 0; i < 10; i++) {
if(vec[i] == 2) continue;
if(i%2==1 && vec[i] != 0) return 0;
if(i%2==0 && vec[i] != 1) return 0;
}
return 1;
}
ll dfs(int pos, bool limit, bool lead, int state) {
if(pos < 0) return isbalanced(state);
if(!limit && ~dp[pos][lead][state]) return dp[pos][lead][state];
ll res = 0;
int up = limit? a[pos]: 9;
for (int i = 0; i <= up; i++) {
if(lead && !i) {
res += dfs(pos-1, limit&&i==up, 1, state);
}
else {
res += dfs(pos-1, limit&&i==up, 0, update(state, i));
}
}
if(limit) return res;
return dp[pos][lead][state] = res;
}
ll solve(string s) {
// cout << s << endl;
int pos = 0;
while (!s.empty()) {
a[pos++] = s.back() - '0';
s.pop_back();
}
return dfs(pos-1, 1, 1, cal(vector<int>(10, 2)));
}
string minusone(string s) {
int sz = (int)s.size();
s.back()--;
for (int i = sz-1; i >= 0; i--) {
if(s[i] < '0') {
s[i] += 10;
s[i-1]--;
}
else break;
}
return s;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
pow3[0] = 1;
for (int i = 1; i <= 9; i++) pow3[i] = pow3[i-1] * 3;
memset(dp, -1, sizeof(dp));
int t;
cin >> t;
while (t--) {
string A, B;
cin >> A >> B;
cout << solve(B) - solve(minusone(A)) << endl;
}
}
HDU - 4352
LIS + 树位DP
设计状态要易于解决LIS问题。
因为最长递增子序列的长度k<=10，且只出现0～9的数字，所以可以用状态压缩表示以pos为结尾、长度为k的最长公共子串的排列state。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[20];
ll dp[20][2][2000][20];
int lower_bound(int state, int digit) {
for (int i = digit; i <= 9; i++) {
if(state & (1<<i)) return i;
}
return digit;
}
ll dfs(int pos, bool limit, bool lead, int state, int k) {
if(pos < 0) return !k;
if(!limit && ~dp[pos][lead][state][k]) return dp[pos][lead][state][k];
ll res = 0;
int up = limit? a[pos]: 9;
int last = -1;
for (int i = 9; i >= 0; i--) {
if((1<<i) & state) {
last = i;
break;
}
}
for (int i = 0; i <= up; i++) { // > last
if(i > last) {
if(lead&&!i) {
int new_state = state ^ (1<<i) ^ (1<<(lower_bound(state, i)));
res += dfs(pos-1, limit&&i==up, 1, new_state, k);
}
else {
res += dfs(pos-1, limit&&i==up, 0, (1<<i) ^ state, k-1);
}
}
else {
int new_state = state ^ (1<<i) ^ (1<<(lower_bound(state, i)));
res += dfs(pos-1, limit&&i==up, lead&&!i, new_state, k);
}
}
if(limit) return res;
return dp[pos][lead][state][k] = res;
}
ll solve(ll x, int k) {
int pos = 0;
while (x) a[pos++] = x % 10, x /= 10;
return dfs(pos-1, 1, 1, 0, k);
}
int main() {
memset(dp, -1, sizeof(dp));
int t, kase = 0;
scanf("%d", &t);
while (t--) {
ll l, r; int k;
scanf("%lld %lld %d", &l, &r, &k);
printf("Case #%d: %lld
", ++kase, solve(r, k) - solve(l-1, k));
}
}
HDU - 4507
如何在数位DP的过程中转移平方和？
-
(cnt(y) = sum{cnt(x)})
-
(sum{(y+x)} = sum{(y * cnt(x))} + sum{x})
-
(sum{(y+x)^2} = sum{(y^2*cnt(x))} + 2*sum{x}*y + sum{x^2})
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
int a[20];
struct Node {
ll segma; // ∑
ll x2; // x^2
ll plan;
Node () {
plan = 0;
x2 = 0;
segma = 0;
}
Node (ll _segma, ll _x2, ll _plan) {
segma = _segma;
x2 = _x2;
plan = _plan;
}
};
Node dp[20][7][7];
ll pow10[20];
Node dfs(int pos, int sum1, int sum2, bool limit) {
if(pos < 0) return Node(0,0,sum1&&sum2);
if(!limit && dp[pos][sum1][sum2].segma != 0)
return dp[pos][sum1][sum2];
int up = limit? a[pos]: 9;
Node res;
for (int i = 0; i <= up; i++) {
if(i == 7) continue;
Node t = dfs(pos-1, (sum1*10+i)%7, (sum2+i)%7, limit&&i==up);
ll y = (i * pow10[pos]) % mod;
(res.plan += t.plan) %= mod;
(res.segma += t.segma + y * t.plan % mod) %= mod;
ll k1 = ((y * y % mod) * t.plan) % mod;
ll k2 = (2 * y) % mod * t.segma % mod;
(res.x2 += (k1+k2)%mod+t.x2%mod) %= mod;
}
if(limit) return res;
return dp[pos][sum1][sum2] = res;
}
ll solve(ll x) {
int pos = 0;
while(x) a[pos++] = x % 10, x /= 10;
return dfs(pos-1, 0, 0, 1).x2 % mod;
}
int main() {
pow10[0] = 1;
for (int i = 1; i <= 18; i++) {
pow10[i] = pow10[i-1] * 10 % mod;
}
int T;
scanf("%d", &T);
while (T--) {
ll l, r;
scanf("%lld%lld", &l, &r);
ll ans = (solve(r) - solve(l-1) + mod) % mod;
printf("%lld
", ans);
}
}