正文

【数位dp】

IP云
IP云V管理员/2 阅读
09/15
小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

hdu5787

问：L ~ R有多少个数是K-wolf Number？其中，K-wolf Number的定义是这个数在十进制下，任意相邻的K个字符没有相同的。

dp[i][j][k]表示有i个空位可填，其中不能填j这个数字中所含有的字符，k = true(表示j有前导0)时，还不能填0.

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define mp make_pair
#define fi first
#define se second
using namespace std;
const int N = 1e5+;
ll l, r;
int k;
ll dp[][][];
int temp[], tot; ll dfs(int pos, int w, bool tag, bool flag){ if(!pos) return ;
if(flag&&~dp[pos][w][tag]) return dp[pos][w][tag];
int Max = flag? : temp[pos]; int ret[], sum = , tmp = w;
while(tmp)
ret[sum++] = tmp%, tmp /= ;
if(tag) ret[sum++] = ; ll ans = ;
for(int i = ; i <= Max; i++){
bool tag2 = true;
for(int j = ; j < sum&&j < k-; j++)
if(ret[j] == i) tag2 = false;
if(tag2){
tmp = ;
int first = min(k-, sum-);
for(int j = first; j >= ; j--)
tmp = tmp*+ret[j];
bool tag3 = false;
if(first >= &&ret[first] == ) tag3 = true;
ans += dfs(pos-, tmp*+i, tag3, flag||i != Max);
}
}
if(flag) dp[pos][w][tag] = ans;
//printf("dfs %d, %d, %d, %d %lld\n", pos, w, tag*1, flag*1, ans);
return ans;
} ll solve(ll x){
tot = ;
while(x){
temp[++tot] = x%;
x /= ;
}
return dfs(tot, , , );
}
int main(){
while(cin >> l >> r >> k){
memset(dp, -, sizeof(dp));
ll ans = solve(r)-solve(l-);
cout << ans << endl;
}
return ;
}

hdu3652

问：1~n有多少个数含有连续的“13”并且能被13整除。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int dp[][][][];
int temp[], tot; int dfs(int pos, int mod, int pre, bool tag13, bool flag){
if(!pos)
return (mod == &&tag13);
if(flag&&~dp[pos][mod][pre][tag13]) return dp[pos][mod][pre][tag13];
int Max = flag? : temp[pos]; int ans = ;
for(int i = ; i <= Max; i++)
ans += dfs(pos-, (mod*+i)%, i, tag13||(pre == &&i == ), flag||i != Max);
if(flag) dp[pos][mod][pre][tag13] = ans;
return ans;
} int solve(int x){
tot = ;
while(x){
temp[++tot] = x%;
x /= ;
}
return dfs(tot, , , , );
}
int main(){
memset(dp, -, sizeof(dp));
int n;
while(cin >> n){
ll ans = solve(n)-solve();
cout << ans << endl;
}
return ;
}

hdu4734

问：0~B中有多少数字各个数位权值和小于 f(A).

#include <bits/stdc++.h>
using namespace std;
int lim;
int dp[][<<];
int temp[], tot;
int dfs(int pos, int sum, bool flag){
if(!pos)
return ;
if(flag&&~dp[pos][sum]) return dp[pos][sum];
int Max = flag? : temp[pos];
int ans = ;
for(int i = ; i <= Max; i++){
if( (i<<(pos-)) <= sum )
ans += dfs(pos-, sum-(i << (pos-)), flag||i != Max);
}
if(flag) dp[pos][sum] = ans;
return ans;
} int solve(int x){
tot = ;
while(x){
temp[++tot] = x%;
x /= ;
}
return dfs(tot, lim, );
}
int main(){
memset(dp, -, sizeof(dp));
int t, a, b, ca = ; scanf("%d", &t);
while(t--){
scanf("%d%d", &a, &b);
lim = ;
for(int i = ; a; i++){
lim += (a%)<<i;
a /= ;
}
// lim < (9*2^9)
int ans = solve(b)-solve()+;
printf("Case #%d: %d\n", ca++, ans);
}
return ;
}

hdu4507

问：l~r中与7无关的数的平方和。与7无关的数定义为：不含数字7，不是7的倍数，且各位数和不是7的倍数。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int P = 1e9+;
ll f[];
ll l, r;
struct p{
ll x, y, z;
p(){}
p(ll x, ll y, ll z):x(x), y(y), z(z){}
};
p dp[][][];
int temp[], tot;
void ad(ll& a, ll b){
a += b;
if(a < ) a = a%P+P;
if(a >= P) a %= P;
}
p dfs(int pos, int add, int mod, bool flag){
if(!pos)
return p(add&&mod, , );
if(flag&&dp[pos][add][mod].x != -) return dp[pos][add][mod]; int Max = flag? : temp[pos];
ll ans = , sum = , sum2 = ;
for(int i = ; i <= Max; i++) if(i != ){
p ret = dfs(pos-, (add+i)%, (mod*+i)%, flag||i != Max);
//i*10^(pos-1)+x
ll tmp = f[pos-]*i%P;
ans += ret.x;
ad(sum, (ret.y+ret.x%P*tmp)%P);
ad(sum2, (ret.x%P*tmp%P*tmp%P+*tmp*ret.y%P+ret.z)%P);
}
if(flag) dp[pos][add][mod] = p(ans, sum, sum2);
//printf("pos %d, add %d, mod %d, flag %d: %lld %lld %lld\n", pos, add, mod, flag*1, ans, sum, sum2);
return p(ans, sum, sum2);
} ll solve(ll x){
tot = ;
while(x){
temp[++tot] = x%;
x /= ;
}
return dfs(tot, , , ).z;
}
int main(){
f[] = ;
for(int i = ; i <= ; i++) f[i] = f[i-]*%P;
memset(dp, -, sizeof(dp));
int t, a, b, ca = ; scanf("%d", &t);
while(t--){
scanf("%lld%lld", &l, &r);
ll ans = solve(r)-solve(l-);
ans %= P;
if(ans < ) ans += P;
printf("%lld\n", ans);
}
return ;
}

hdu3709

问：l~r中有多少数字是平衡数？ 平衡数的定义为能在数字中找到某一个点作为支点使左边的力矩和右边的力矩相等？如4139，以3为支点时左边是4*2+1*1 = 9， 右边是9*1 = 9.

#include <bits/stdc++.h>
#define ll unsigned long long
using namespace std;
ll dp[][][+];
ll l, r; int temp[], tot; ll dfs(int pos, bool pre, int pivot, int now, bool flag){
if(!pos)
return now == ;
if(flag&&~dp[pos][pivot][+now]) return dp[pos][pivot][+now]; int Max = flag? : temp[pos];
ll ans = ;
for(int i = ; i <= Max; i++){
if(!pre&&pivot == pos&&!i) continue ;
int ret = now+(pos-pivot)*i;
if(ret > ||ret < -) continue ;
ans += dfs(pos-, pre||i, pivot, ret, flag||i != Max);
} if(flag) dp[pos][pivot][+now] = ans;
return ans;
} ll solve(ll x){
tot = ;
while(x){
temp[++tot] = x%;
x /= ;
}
ll ans = ;
for(int i = ; i <= tot; i++)
ans += dfs(tot, , i, , );
return ans;
}
int main(){
memset(dp, -, sizeof(dp));
int t, ca = ; scanf("%d", &t);
while(t--){
cin >> l >> r;
ll ans = ;
if(l == ) l++, ans++;
ans += solve(r)-solve(l-);
cout << ans << endl;
}
return ;
}

SPOJ Balanced Numbers

问：l~r有多少数字满足奇数数字出现偶数次偶数数字出现奇数次。

#include <bits/stdc++.h>
#define ll unsigned long long
using namespace std;
//3^10 = 59049
ll f[];
ll dp[][][];
ll l, r; int temp[], tot;
bool judge(int x){
bool tag = true;
while(x){
int ret = x%;
if(ret){
ret &= ;
if(ret != tag) return false;
}
tag = !tag;
x /= ;
}
return true;
}
ll dfs(int pos, bool pre, int now, bool flag){//pre == true 1
// printf("%d %d %d %d\n", pos, pre*1, now, flag*1);
if(!pos)
return judge(now);
if(flag&&~dp[pos][pre][now]) return dp[pos][pre][now]; int Max = flag? : temp[pos];
ll ans = ;
for(int i = ; i <= Max; i++){
int ret = ;//3^j
if(i||pre){
ret = (now/f[i])%;
if(ret < ) ret = now+f[i];
else ret = now-f[i];
}
ans += dfs(pos-, pre||i, ret, flag||i != Max);
} if(flag) dp[pos][pre][now] = ans;
//printf("pos %d, add %d, mod %d, flag %d: %lld %lld %lld\n", pos, add, mod, flag*1, ans, sum, sum2);
return ans;
} ll solve(ll x){
tot = ;
while(x){
temp[++tot] = x%;
x /= ;
}
return dfs(tot, , , );
}
int main(){
f[] = ;
for(int i = ; i < ; i++) f[i] = f[i-]*;
memset(dp, -, sizeof(dp));
int t, ca = ; scanf("%d", &t);
while(t--){
cin >> l >> r;
ll ans = solve(r)-solve(l-);
cout << ans << endl;
}
return ;
}

hdu4352

问：l~r有多少数字的严格最长上升子序列是k？

题解：状压。dp[还剩i位][k][二进制位下的最长上升子序列]

#include <bits/stdc++.h>
#define ll unsigned long long
using namespace std;
const int N = 1e5+;
const int P = 1e9+;
ll dp[][][<<];
ll l, r, k; int temp[], tot;
ll dfs(int pos, int k, int now, bool flag){
if(!pos)
return __builtin_popcount(now) == k;
if(flag&&~dp[k][pos][now]) return dp[k][pos][now]; int Max = flag? : temp[pos];
ll ans = ;
for(int i = ; i <= Max; i++) {
if(!now&&!i) {
ans += dfs(pos-, k, now, flag||i != Max);
continue ;
}
int ret = now;
if( !((ret>>i)&) ){//ret[i] : 0
if( ret>>i ){
for(int j = i+; j; j++)
if((ret>>j)&){
ret ^= <<j;
break;
}
}
ret |= <<i;
}
ans += dfs(pos-, k, ret, flag||i != Max);
} if(flag) dp[k][pos][now] = ans;
return ans;
} ll solve(ll x){
tot = ;
while(x){
temp[++tot] = x%;
x /= ;
}
return dfs(tot, k, , );
}
int main(){
memset(dp, -, sizeof(dp)); int t, ca = ; scanf("%d", &t);
while(t--){
cin >> l >> r >> k;
ll ans = solve(r)-solve(l-);
printf("Case #%d: ", ca++);
cout << ans << endl;
}
return ;
}

Codeforces 55D

问：l~r有多少数字可以被各个位上的非0数字整除？

#include <bits/stdc++.h>
#define ll unsigned long long
using namespace std;
const int P = ;
ll dp[][<<][];
ll l, r;
int w[][] = {
{, , , },
{, , , },
{, , , },
{, , , },
{, , , },
{, , , },
{, , , },
{, , , },
{, , , },
{, , , }
};
int temp[], tot;
ll dfs(int pos, int k, int now, bool flag){
//printf("%d %d %d\n", pos, k, now);
if(!pos){
int a2 = k&, a3 = (k>>)&, a5 = (k>>)&, a7 = k>>;
if(a2 == &&now%) return ;
if(a2 == &&now%) return ;
if(a2 == &&now%) return ;
if(a3 == &&now%) return ;
if(a3 == &&now%) return ;
if(a5&&now%) return ;
if(a7&&now%) return ;
return ;
}
if(flag&&~dp[pos][k][now]) return dp[pos][k][now]; int Max = flag? : temp[pos];
ll ans = ;
int ret[], ret2[];
ret[] = k&, ret[] = (k>>)&, ret[] = (k>>)&, ret[] = k>>;
for(int i = ; i <= Max; i++) {
for(int j = ; j < ; j++)
ret2[j] = max(ret[j], w[i][j]);
int r = ret2[]+(ret2[]<<)+(ret2[]<<)+(ret2[]<<);
ans += dfs(pos-, r, (now*+i)%, flag||i != Max);
} if(flag) dp[pos][k][now] = ans;
//printf("%d %d %d: %lld\n", pos, k, now, ans);
return ans;
} ll solve(ll x){
tot = ;
while(x){
temp[++tot] = x%;
x /= ;
}
return dfs(tot, , , );
}
int main(){
memset(dp, -, sizeof(dp));
int t, ca = ; scanf("%d", &t);
while(t--){
cin >> l >> r;
ll ans = solve(r)-solve(l-);
cout << ans << endl;
}
return ;
}