题解 P2518 【[HAOI2010]计数】

· · 题解

这……为啥好好的数位dp题的题解里没一个是数位dp的？？？

这里上一个比较暴力但是能过跑的还挺快的纯数位dp做法。

首先这题的题意是求<n的数位里的非0位的集合是n的非0位集合的数的个数，然后我们有一个暴力的做法就是在状态里记录每个数字出现的次数，注意到总数最多只有50个，我们感性理解一下这个状态最多大概是7^7（7*7=49）级别的，也就80多万完全没问题，再按照套路在状态里加上当前是从高到低第几位，前缀是不是和n相同，就行了。

然后这状态没法用数组开下，于是我们可以使用一种最无脑的方法就是开个哈希表然后用bfs转移……具体来说，我们用一个小技巧，注意到这状态里的东西都不超过255，开2个unsigned long long“当做”char数组存，就是这样的：

((char*)&data)[x]

这个就相当于把一个unsigned long long 变量data当做char数组来用，取x下标的位置，注意x必须小于8。这个技巧在一些状态比较复杂的状压dp里配合hash表一块用会非常好用另外orz一下教会我这个的卡常之王shadowice1984

然后空间可能不太能开的下，其实可以在逐位dp的时候把hash表滚动一下就行了。

上代码~

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
#define p 1000003
#define ull unsigned long long
using namespace std;
namespace ywy {
    char str[55];
    typedef struct _zt {
        ull a, b;
        _zt() {
            a = 0;
            b = 0;
        }
        inline int get(int x) {
            if (x < 8)
                return (((char *)&a)[x]);
            x -= 8;
            return (((char *)&b)[x]);
        }
        inline void set(int x, int num) {
            if (x < 8)
                ((char *)&a)[x] = num;
            else
                ((char *)&b)[x - 8] = num;
        }
        inline int hsh() {
            ull cjr = a;
            cjr %= p;
            cjr <<= 32;
            cjr |= (b % p);
            return (cjr % p);
        }
        friend bool operator==(const _zt &a, const _zt &b) { return (a.a == b.a && a.b == b.b); }
    } zt;
    typedef struct _n {
        zt data;
        ll dp;
        int nxt;
    } node;
    typedef struct _hsh {
        node memchi[1000001];
        int heads[1000004], gn = 1;
        inline void clear() {
            memset(heads, 0, sizeof(heads));
            gn = 1;
        }
        inline ll query(zt dat) {
            int h = dat.hsh();
            for (register int i = heads[h]; i; i = memchi[i].nxt) {
                if (memchi[i].data == dat)
                    return (memchi[i].dp);
            }
            return (0);
        }
        inline int insert(zt dat, ll dp) {
            int h = dat.hsh();
            for (register int i = heads[h]; i; i = memchi[i].nxt) {
                if (memchi[i].data == dat) {
                    memchi[i].dp += dp;
                    return (0);
                }
            }
            memchi[gn].data = dat;
            memchi[gn].dp = dp;
            memchi[gn].nxt = heads[h];
            heads[h] = gn;
            gn++;
            return (1);
        }
    } hsh;
    hsh ha[2];
    int cnt[2];
    zt que[2][1000001];
    void ywymain() {
        cin >> str + 1;
        int n = strlen(str + 1);
        reverse(str + 1, str + 1 + n);
        zt ztz11;
        for (register int i = 1; i <= n; i++) {
            if (str[i] != '0') {
                int cjr = ztz11.get(str[i] - '0');
                cjr++;
                ztz11.set(str[i] - '0', cjr);
            }
        }
        cnt[n & 1] = 1;
        ztz11.set(10, 1);
        que[n & 1][0] = ztz11;
        ha[n & 1].insert(ztz11, 1);
        for (register int i = n; i >= 1; i--) {
            ha[(i & 1) ^ 1].clear();
            cnt[(i & 1) ^ 1] = 0;
            for (register int j = 0; j < cnt[i & 1]; j++) {
                zt me = que[i & 1][j];
                ll dp = ha[i & 1].query(me);
                for (register int k = 0; k <= ((me.get(10)) ? (str[i] - '0') : 9); k++) {
                    zt cjr = me;
                    if (k && !cjr.get(k))
                        continue;
                    if (k)
                        cjr.set(k, cjr.get(k) - 1);
                    if (me.get(10) && k < str[i] - '0')
                        cjr.set(10, 0);
                    if (ha[(i & 1) ^ 1].insert(cjr, dp))
                        que[(i & 1) ^ 1][cnt[(i & 1) ^ 1]] = cjr, cnt[(i & 1) ^ 1]++;
                }
            }
        }
        cout << ha[0].query(_zt()) << endl;
    }
}
int main() {
    ywy::ywymain();
    return (0);
}