fr大佬的原创题，菜鸡受教了
给出两个数字集合S和T，其中元素均为0到9之间的整数。
定义“完美数字”为数位中包含S中所有的数且不包含T中任意一个数的数字。
例如S={1,3,4}，T={7,8}，则1345、341166、4133129都是完美数字。
而13、8431、34171都不是完美数字（因为13数位中不包含44，8431和34171中虽然包含了1、3、4这三个数但又包含88和77）。
求[l,r]中所有完美数字的和。
对于100%的数据，t<=2000，1<=l<=r<\(10^{9}\)，保证S和T中的元素均为[0,9]中的整数且互不相同。
这道题，数位dp可以一眼就看出来，状压也能在思考过程中顺势带出来
规定如下:
\(state\)存状态，\(1<<i\)表示数字\(i\)存在于该状态下
\(move(k)\)表示\(1<<k\)
\(g[state][k]\)表示状态为state的k位数的个数，且零可以任意摆放
\(hg[state][k]\)表示状态为state的k位数的和，且零可以任意摆放
\(hf[state][k]\)表示状态为state的k位数的和，且零符合通则
由于求解hf的过程的时候需要利用到g和hg，因此我们顺序求出来
接下来会出现大量的"state中1的位置"与"state中1的个数"，提前解释一下。前者根据state的定义方法可知，\((1<<k)\)存的是\(数字k\)存在；后者指的是该状态的数字由几种数字构成(如134，由1、3、4构成)
由于dp求解，因此在求\(g[state][k]\)的时候\(g[][k-1]\)一定已经求解出来了。因此可以理解为在\(k-1\)位数的基础上再添加一个数字。
假设新添加的数字在\(k-1\)位数中出现过，那么\(state\)中每一个数字都可以带来\(g[state][k-1]\)种可能，因此
假设新添加的数字在\(k-1\)位数中没有出现过，那么每一个数字带来\(state-move()\)种可能，因此
同样道理分类讨论
假设新添加的数字在\(k-1\)位数中出现过，那么\(state\)中每一个数字都可以带来\(g[state][k-1]\)种可能,因此
新添加的数字：
原来的\(k-1\)位数字：
假设新添加的数字在\(k-1\)位数中没有出现过，那么每一个数字带来\(state-move()\)种可能，因此:
新添加的数字：
原来的\(k-1\)位数字：
还是分类讨论~~其实与\(hg[state][k]\)大同小异，只是由于零不能前置，由略微地更改。为了严谨还是完整叙述一遍
假设新添加的数字在\(k-1\)位数中出现过，那么\(state\)中每一个数字都可以带来\(g[state][k-1]\)种可能,因此
新添加的数字：
原来的\(k-1\)位数字：
假设新添加的数字在\(k-1\)位数中没有出现过，那么每一个数字带来\(state-move()\)种可能，因此:
新添加的数字：
原来的\(k-1\)位数字：
呼，dp推完了~~
\(f[state][k]\)是在思路不清地时候瞎推的
手写版：
代码版：
code:
void init(){
for(register int i=0;i<=9;++i) g[move(i)][1]=1;
for(register int p=2;p<=9;++p){
for(register int i=1;i<=move(10)-1;++i){
int sum=0;
for(register int j=0;j<=9;++j) if(i&move(j)) sum++;
g[i][p]=sum*g[i][p-1];
for(register int j=0;j<=9;++j){
if(i&move(j)){
g[i][p]+=g[i-move(j)][p-1];
}
}
}
}
for(register int i=1;i<=9;++i) f[move(i)][1]=1;
for(register int p=2;p<=9;++p){
for(register int i=1;i<=move(10)-1;++i){
int sum=0;
for(register int j=1;j<=9;++j) if(i&move(j)) sum++;
f[i][p]+=sum*g[i][p-1];
for(register int j=1;j<=9;++j){
if(i&move(j)){
f[i][p]+=g[i-move(j)][p-1];
}
}
}
}
for(register int i=0;i<=9;++i) hg[move(i)][1]=i;
for(register int p=2;p<=9;++p){
for(register int i=1;i<=move(10)-1;++i){
int sum=0,cnt=0;
for(int k=0;k<=9;++k){
if(i&move(k)){
sum+=k; cnt++;
}
}
hg[i][p]+=sum*tim[p-1]*g[i][p-1];
hg[i][p]+=cnt*hg[i][p-1];
for(register int k=0;k<=9;++k){
if(i&move(k)){
hg[i][p]+=k*tim[p-1]*g[i-move(k)][p-1];
hg[i][p]+=hg[i-move(k)][p-1];
}
}
}
}
for(register int i=1;i<=9;++i) hf[move(i)][1]=i;
for(register int p=2;p<=9;++p){
for(register int i=1;i<=move(10)-1;++i){
int sum=0,cnt=0;
for(register int k=1;k<=9;++k){
if(i&move(k)){
cnt++; sum+=k;
}
}
hf[i][p]+=sum*tim[p-1]*g[i][p-1];
hf[i][p]+=cnt*hg[i][p-1];
for(register int k=1;k<=9;++k){
if(i&move(k)){
hf[i][p]+=k*tim[p-1]*g[i-move(k)][p-1];
hf[i][p]+=hg[i-move(k)][p-1];
}
}
}
}
}
然后有了dp，数位dp小心点处理就ok(。???)ノ
code:
#include <ctime>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
int T;
int l,r;
int s[15],t[15];
ll tim[11]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000ll,10000000000ll};
ll f[1024][15],g[1024][15],hg[1024][15],hf[1024][15];
int ty[1024];
clock_t st,ed;
void work();
inline int read();
inline int move(int);
void init();
ll calculate(int);
bool check(int);
int main(){
#ifndef ONLINE_JUDGE
freopen("test.in","r",stdin);
#endif
init();
T=read();
while(T--) work();
return 0;
}
void work(){
l=read(); r=read();
s[0]=read(); for(int i=1;i<=s[0];++i) s[i]=read();
t[0]=read(); for(int i=1;i<=t[0];++i) t[i]=read();
s[s[0]+1]=0; for(int i=1;i<=s[0];++i) s[s[0]+1]|=move(s[i]);
t[t[0]+1]=0; for(int i=1;i<=t[0];++i) t[t[0]+1]|=move(t[i]);
ty[0]=0;
for(int i=1;i<=move(10)-1;++i) if(check(i)) ty[++ty[0]]=i;
cout<<calculate(r)-calculate(l-1)<<endl;
}
inline int read(){
char tmp=getchar(); int sum=0; bool flag=false;
while(tmp<‘0‘||tmp>‘9‘){
if(tmp==‘-‘) flag=true;
tmp=getchar();
}
while(tmp>=‘0‘&&tmp<=‘9‘){
sum=(sum<<1)+(sum<<3)+tmp-‘0‘;
tmp=getchar();
}
return flag?-sum:sum;
}
inline int move(int k){
int tmp=1;
return tmp<<k;
}
void init(){
for(register int i=0;i<=9;++i) g[move(i)][1]=1;
for(register int p=2;p<=9;++p){
for(register int i=1;i<=move(10)-1;++i){
int sum=0;
for(register int j=0;j<=9;++j) if(i&move(j)) sum++;
g[i][p]=sum*g[i][p-1];
for(register int j=0;j<=9;++j){
if(i&move(j)){
g[i][p]+=g[i-move(j)][p-1];
}
}
}
}
for(register int i=1;i<=9;++i) f[move(i)][1]=1;
for(register int p=2;p<=9;++p){
for(register int i=1;i<=move(10)-1;++i){
int sum=0;
for(register int j=1;j<=9;++j) if(i&move(j)) sum++;
f[i][p]+=sum*g[i][p-1];
for(register int j=1;j<=9;++j){
if(i&move(j)){
f[i][p]+=g[i-move(j)][p-1];
}
}
}
}
for(register int i=0;i<=9;++i) hg[move(i)][1]=i;
for(register int p=2;p<=9;++p){
for(register int i=1;i<=move(10)-1;++i){
int sum=0,cnt=0;
for(int k=0;k<=9;++k){
if(i&move(k)){
sum+=k; cnt++;
}
}
hg[i][p]+=sum*tim[p-1]*g[i][p-1];
hg[i][p]+=cnt*hg[i][p-1];
for(register int k=0;k<=9;++k){
if(i&move(k)){
hg[i][p]+=k*tim[p-1]*g[i-move(k)][p-1];
hg[i][p]+=hg[i-move(k)][p-1];
}
}
}
}
for(register int i=1;i<=9;++i) hf[move(i)][1]=i;
for(register int p=2;p<=9;++p){
for(register int i=1;i<=move(10)-1;++i){
int sum=0,cnt=0;
for(register int k=1;k<=9;++k){
if(i&move(k)){
cnt++; sum+=k;
}
}
hf[i][p]+=sum*tim[p-1]*g[i][p-1];
hf[i][p]+=cnt*hg[i][p-1];
for(register int k=1;k<=9;++k){
if(i&move(k)){
hf[i][p]+=k*tim[p-1]*g[i-move(k)][p-1];
hf[i][p]+=hg[i-move(k)][p-1];
}
}
}
}
}
ll calculate(int k){
ll ans=0;
if(k<10){
for(register int i=1;i<=k;++i){
if(!check(move(i))) continue;
ans+=i;
}
return ans;
}
int line[15]; line[0]=0;
int tmp=k;
while(tmp){
line[++line[0]]=tmp%10;
tmp/=10;
}
for(register int p=1;p<line[0];++p){
for(register int i=ty[1],tmpi=1;tmpi<=ty[0];++tmpi,i=ty[tmpi]){
if(!check(i)) continue;
ans+=hf[i][p];
}
}
int rec=0; ll sum=0;
for(register int p=1;p<line[line[0]];++p){
rec+=move(p);
sum+=p;
for(register int i=1;i<=move(10)-1;++i){
if(!check(rec|i)) continue;
ans+=hg[i][line[0]-1];
ans+=sum*tim[line[0]-1]*g[i][line[0]-1];
}
rec-=move(p);
sum-=p;
}
for(register int i=1;i<=t[0];++i) if(line[line[0]]==t[i]) return ans;
rec+=move(line[line[0]]); sum=line[line[0]]*10;
for(register int p=line[0]-1;p>=2;--p){
for(register int i=0;i<line[p];++i){
bool flag=false;
if(rec&move(i)) flag=true;
else rec+=move(i);
sum+=i;
for(register int j=1;j<=move(10)-1;++j){
if(!check(rec|j)) continue;
ans+=hg[j][p-1];
ans+=sum*tim[p-1]*g[j][p-1];
}
if(!flag) rec-=move(i);
sum-=i;
}
for(register int i=1;i<=t[0];++i) if(t[i]==line[p]) return ans;
rec|=move(line[p]);
sum+=line[p]; sum*=10;
}
for(register int p=0;p<=line[1];++p){
int tmprec=rec|move(p);
ll tmpsum=sum+p;
if(!check(tmprec)) continue;
ans+=tmpsum;
}
return ans;
}
bool check(int k){
if((k&s[s[0]+1])!=s[s[0]+1]) return false;
if(k&t[t[0]+1]) return false;
return true;
}
原文：https://www.cnblogs.com/ticmis/p/13210982.html