数位 dp
总结
-
值域巨大的题目，考虑分治、矩乘、数位 dp 和规律。
-
数位 dp 通常需要将对数的描述转化成对每个数位的描述，从而按位 dp，尤其是等式。
-
关于不等式的刻画，通常是记录是否处于危险态，本质上也是刻画到每一位上。
例题
Codechef Nov. Lunch 2020 C - Xor Compare
分析
明示二进制数位 dp，直接记两个状态分别表示两个不等式是否处于危险态，16 种情况分类讨论。
入门套路题！
bool g(int x,int i){return x>>i&1;}
int f(int i,bool j,bool k){
if(F[i][j][k]!=-1) return F[i][j][k];
int t=0; bool N=g(n,i),X=g(x,i),Y=g(y,i);
if(!i){
if(!j&&!N) t=k?1:X<Y;
else t=k?2:X^Y;
}else{
if(j==0){
if(k==0){
if(N==0) t=X<=Y?f(i-1,0,X<Y):0;
else{
t=X<=Y?f(i-1,1,X<Y):0;
t+=X>=Y?f(i-1,0,X>Y):0;
}
}else{
t=f(i-1,0,1);
if(N) t+=f(i-1,1,1);
}
}else{
if(k==0){
t=X<=Y?f(i-1,1,X<Y):0;
t+=X>=Y?f(i-1,1,X>Y):0;
}else t=2*f(i-1,1,1);
}
}return F[i][j][k]=t;
}
实现比较痛苦。
小结
- 关于不等式的刻画，通常是记录是否处于危险态。
2022.9.19 T2 与之国
分析
发现值域巨大，考虑分治、矩乘和规律。此题显然是要找规律，先把表打出来。
n=2**4
for i in range(n):
for j in range(n):
if (i&j)==0:
print('#',end=' ')
else:
print('.',end=' ')
print()
# # # # # # # # # # # # # # # #
# . # . # . # . # . # . # . # .
# # . . # # . . # # . . # # . .
# . . . # . . . # . . . # . . .
# # # # . . . . # # # # . . . .
# . # . . . . . # . # . . . . .
# # . . . . . . # # . . . . . .
# . . . . . . . # . . . . . . .
# # # # # # # # . . . . . . . .
# . # . # . # . . . . . . . . .
# # . . # # . . . . . . . . . .
# . . . # . . . . . . . . . . .
# # # # . . . . . . . . . . . .
# . # . . . . . . . . . . . . .
# # . . . . . . . . . . . . . .
# . . . . . . . . . . . . . . .
这是直角分形！我们可以递归定义这个图形，但我们关注的是一个矩形的连通块数。
但我们看到 sub4 部分分：
保证矩形满足 \(l_x=r_x\)。
这不就是一条线吗？一条线的连通块数量好像好做一些。
我们观察图形，我们似乎可以从一个点向下或向右走遍一大块，根据这是一个分形，可以很好理解，只要小的一块是对的，不断分形下去依然成立。
那么对于一个矩形，中间一大片会不会是连通的呢？将上面的结论反过来，中间的一个点一定会向左或向上连通，中间也就会和上边界或左边界连通了，也就是说矩形连通块数等于上边界和左边界形成的折线的连通块数。
折线的连通块数可以由横着的和竖着的线段拼起来。
int l1,l2,r1,r2;io>>l1>>r1>>l2>>r2;
printf("%d\n",calc(l1,r1,r2)+calc(r1,l1,l2)-z(l1,r1));
而线段的连通块数又可以差分成前缀，
bool z(int a,int b){
return (a&b)==0?1:0;
}
int calc(int a,int l,int r){
::a=a;int ans=pre(r);
if(l)ans+=z(a,l)*z(a,l-1)-pre(l-1);
return ans;
}
前缀的连通块数就是统计这个式子
\[\sum\limits_{i=0}^{x}z(a,i)z(a,i-1) \]特别的 z(a,-1)=1。此时我们考虑二进制数位 dp 计算答案。
dp it
如果只要求 \(\sum_{i=1}^xz(a,i)\)，十分 easy，记录是否处于危险态就可以了。但我们还希望 \(z(a,i-1)\) 成立，通常这个时候，我们需要将关系式刻画成二进制位的某种特征，把它具体化下来 dp。
\(i-1\) 意味着抹去 \(i\) 的 lowbit 位并将 lowbit 后面的位赋成 1，所以在 lowbit 位及其以前的位依然满足按位与上 \(a\) 等于 0。但我们希望 \(i-1\) 按位与 \(a\) 不为 0，只有可能是后面一段 1 按位与上 \(a\) 不为 0，也就是说 \(i\) 的 lowbit 位比 \(a\) 的 lowbit 位大，特别的 0 直接视作合法。那我们可以更简单的描述成可以在 \(a\) 的 lowbit 位之前填 1，后面只能填 0，注意这里不能差分成前缀，因为可能后面仍然有 1。
此时数位 dp 其实和 \(\sum_{i=1}^xz(a,i)\) 是一样的了
bool q(int a,int i){return a>>i&1;}
int a,x,lim,f[32][2];
int dfs(int i=30,bool j=0){
if(f[i][j]!=-1)return f[i][j];
int t;
if(i==lim)t=1;
if(i>lim){
bool b=j|q(x,i);t=dfs(i-1,b);
if(!q(a,i)&&b)t+=dfs(i-1,j);
}return f[i][j]=t;
}
int pre(int x){
if(!a)return 1;
int b=a;lim=0;
while(z(b,1))++lim,b>>=1;
memset(f,-1,sizeof f);
::x=x;return dfs();
}
小结
-
值域巨大的题目，考虑分治、矩乘、数位 dp 和规律。
-
数位 dp 通常需要将对数的描述转化成对每个数位的描述，从而按位 dp。
BZOJ 3329 Xorequ
分析
\[\because x\oplus3x=2x \]\[\therefore x\oplus2x=3x \]\[\because x+2x=3x \]\[\therefore x\oplus2x=x+2x \]什么数和它的两倍满足按位异或和等于和呢？按位异或和是二进制不进位加法，和是二进制进位加法，它们相等说明没有进位，也就是这个数没有相邻的数位是 1，直接数位 dp。
对于第二问，dp 一下可以知道这其实是斐波那契数列 ( Fibonacci )，直接矩乘。
code 被我吃了