Beautiful numbers[数位dp+状压]
将0~9数字否存在状压到s
再将数字膜上(1，2，3，4，5，6，7，8，9，)和20位数放入(dp)。
这样空间会有(9！ imes2^{10} imes20)很明显会超时。
再往每个膜数上优化。
首先如果一个数x % 8为(0，2，4，6)那么x%2为(0)（即(2)的倍数）。
膜上2这个可以去除。
一个数x%9为0，3，6，那么x%3为(0)（即(3)的倍数）。
膜上3这个可以去除。
一个数x%8为(0，4)那么x%4为(0)（即(4)的倍数）。
膜上4这个可以去除。
如果一个数x % 8为(0，2，4，6)并且x%9为(0，3，6)（即既是2的倍数，又是3的倍数），那么x%6为(0)。
膜上6这个可以去除。
即可以将膜上(1，2，3，4，5，6，7，8，9，)优化为膜上(5,7,8,9)
且只需要存上是否存在2~9的数字（0和1不需要判断）。
这样空间会有(5 imes7 imes8 imes9 imes2^8 imes20=12,902,400)勉强能开下。
#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
ll t,l,r,a[20];
ll dp[20][5][7][8][9][307];
ll lin;
ll ksm(ll x,ll p){
ll res=1;
while(p){
if(p%2==1) res=res*x;
p/=2;
x=x*x;
}
return res;
}
ll dfs(ll p,ll wu,ll qi,ll ba,ll jiu,ll s,ll lim){
if(p==0){
ll ok=1;
for(ll i=0;i<=7;i++){
if(s&(1<<i)){
if(i==0){
if(!(ba==0||ba==2||ba==4||ba==6)){
ok=0;
}
}
if(i==1){
if(!(jiu==0||jiu==3||jiu==6)){
ok=0;
}
}
if(i==2){
if(!(ba==0||ba==4)){
ok=0;
}
}
if(i==3){
if(wu!=0){
ok=0;
}
}
if(i==4){
if(!(ba==0||ba==2||ba==4||ba==6)){
ok=0;
}
if(!(jiu==0||jiu==3||jiu==6)){
ok=0;
}
}
if(i==5){
if(qi!=0){
ok=0;
}
}
if(i==6){
if(ba!=0){
ok=0;
}
}
if(i==7){
if(jiu!=0){
ok=0;
}
}
}
}
return ok;
}
if(lim==0&&dp[p][wu][qi][ba][jiu][s]!=-1){
return dp[p][wu][qi][ba][jiu][s];
}
ll up=lim? a[p]:9;
ll ans=0;
for(ll i=0;i<=up;i++){
if(i>=2){
ans+=dfs(p-1,(wu+ksm(10,p-1)*i)%5,(qi+ksm(10,p-1)*i)%7,(ba+ksm(10,p-1)*i)%8
,(jiu+ksm(10,p-1)*i)%9,s|(1<<(i-2)),lim&&i==up);
}
else{
ans+=dfs(p-1,(wu+ksm(10,p-1)*i)%5,(qi+ksm(10,p-1)*i)%7,(ba+ksm(10,p-1)*i)%8
,(jiu+ksm(10,p-1)*i)%9,s,lim&&i==up);
}
}
if(lim==0)return dp[p][wu][qi][ba][jiu][s]=ans;
else return ans;
}
ll solve(ll num){
ll tot=0;
while(num){
a[++tot]=num%10;
num/=10;
}
return dfs(tot,0,0,0,0,0,1);
}
int main(){
scanf("%lld",&t);
memset(dp,-1,sizeof(dp));
while(t--){
scanf("%lld %lld",&l,&r);
printf("%lld
",solve(r)-solve(l-1));
}
}