题解 P2518 【[HAOI2010]计数】

· · 题解

数位DP（记忆化BFS）

在文章的开始先%%教会我的@ywy_c_asm 大佬和 shadowice1984

ywy_c_asm的题解

按照数位DP的常规套路，dfs枚举每一个小于等于自己的数，再判断该数是否与原数是否有着除0以外的相同数码

那么问题来了，怎么判断该数是否与原数是否有着除0以外的相同数码呢？一种直观的想法是开一个数组记录原数中除0以外每个数码出现的次数，然而如果这么做的话时间和空间都要炸。

再想一想，如果原问题为一个不重复的集合（即每个数出现次数都是1或0），我们可以怎么做呢？一种解决方法就是开一个unsigned long long se，se|（1<<i-1）就表示将i数加入集合中

然而这道题一个数可以出现多次！这时候我们就要用到一个技巧，把unsigned long long强制转化为8个char（一个unsigned long long8个字节，char一个字节），就是这行代码

(((char *)&a)[x]

它表示把unsigned long long a转化为char后的a[x]，其中x必须小于8

一个unsigned long long只能存8个，显然是不够的，所以我们需要把两个拼接起来，而hash的key值就有这两个unsigned long long得到

然后我们就可以愉快地搜索了！我用的是宽搜，开两个队列，一个存了上一层的节点，一个存了这一层的节点，使用滚动数组的技巧节约空间，就可以AC这道题了！一个队列应该也是可以过的，有兴趣的同学可以尝试一下

#include<bits/stdc++.h>
using namespace std;
#define go(i,a,b) for(int i=(a);i<=(b);++(i))
#define com(i,a,b) for(int i=(a);i>=(b);--(i))
#define mem(a,b) memset((a),(b),sizeof(a))
typedef long long ll;
typedef unsigned long long ull;
char s[55];
const int mod=1000003;
int n,num[55];
#define inl inline
struct point{
    ull a, b;
    point(){a=b=0;}
    inline int get(int x) {
        if (x < 8) return (((char *)&a)[x]);
        return (((char *)&b)[x-8]);
    }
    inline void set(int x, int num) {
        if (x < 8) ((char *)&a)[x] = num;
        else ((char *)&b)[x - 8] = num;
    }
    inline int get_hash() {
        ull ha = a;
        ha %= mod;
        ha <<= 32;
        ha |= (b % mod);
        return (ha % mod);
    }
    friend bool operator == (point &a,point &b){
        return a.a==b.a&&a.b==b.b;
    }
};
struct edge{
    point dat;
    ll dp;int nxt;
};
struct hash{
    edge e[mod+5];
    int cnt=0,head[mod+5];
    inl void clear(){mem(head,-1),cnt=0;}
    inl ll query(int u,point x){
        for(int i=head[u];i+1;i=e[i].nxt){
            if(e[i].dat==x) return e[i].dp;
        }
        return 0;
    }
    inl bool insert(point x,ll dp){
        int u=x.get_hash();
        for(int i=head[u];i+1;i=e[i].nxt){
            if(e[i].dat==x){
                e[i].dp+=dp;
                return 0;
            }
        }
        e[cnt]=(edge){x,dp,head[x.get_hash()]};
        head[u]=cnt++;
        return 1;
    }
};
point q[2][mod+5];
hash h[2];
int cnt[2];
#define last i&1
#define now ((i&1)^1)
int main()
{
    scanf("%s",s+1);
    n=strlen(s+1);
    go(i,1,n) num[i]=s[n-i+1]-'0';
    point st;
    go(i,1,n){
        if(num[i]){
            st.set(num[i],st.get(num[i])+1);
        }
    }
    st.set(10,1);//limit=1
    cnt[n&1]=1;q[n&1][0]=st;//根节点
    h[n&1].clear();
    h[n&1].insert(st,1);
    com(i,n,1){
        cnt[now]=0;
        h[now].clear();
        go(j,0,cnt[last]-1){
            point fro=q[last][j];
            ll dp=h[last].query(fro.get_hash(),fro);
            go(k,0,fro.get(10)?num[i]:9){
                point x=fro;
                if(k&&!x.get(k)) continue;
                if(k) x.set(k,x.get(k)-1);
                if(x.get(10)&&k<num[i]) x.set(10,0);
                if(h[now].insert(x,dp)){
                    q[now][cnt[now]]=x;cnt[now]++;
                }
            }
        }
    }
    printf("%lld",h[0].query(0,point()));
    return 0;
}