bozoj3131: [Sdoi2013]淘金 数位dp

链接

https://www.lydsy.com/JudgeOnline/problem.php?id=3131

思路

1.

函数值的素因子只有2、3、5、7
由他们组成的状态不多，爆搜的时候即使搜不对也没关系，我们只是缩小范围而已
所以不要管呢么多，搜到几万就差不多了，包含有可能的就行

2.

\(f[i][j][0/1]\)表示后i位，乘积为j，n的i位>=k(枚举1-9)？1:0
n的i位>k
\(f[i][j][1]+=f[i][j][1]+f[i][j][0]\)
n的i位<k
\(f[i][j][0]+=f[i][j][1]+f[i][j][0]\)
n的i位==k
\(f[i][j][1]+=f[i][j][1]\)
\(f[i][j][0]+=f[i][j][0]\)

3.

统计的时候，sort
之后想象成二维数组，每一行都是单调的，所以只用头做比较，堆维护就可以
单调队列没想过

错误$$感叹

dp调试真快啊，处理起来真恶心曹丹清啊

代码

#include <iostream>
#include <queue>
#include <map>
#include <cstdio>
#include <algorithm>
#include <vector>
#define ll long long
const ll N=5e5+7;
const ll mod=1e9+7;
using namespace std;
ll n,k,val[N],c[N],js;
ll f[15][N][2];
ll A,B,jl[15];
map<ll,ll> hasH;
struct Pair {
    ll first,second;
    Pair() {}
    Pair(ll a,ll b) :
        first(a),second(b) {}
};
bool operator < (Pair a,Pair b) {
    if(a.second==js+1) return 0;
    if(b.second==js+1) return 1;
    return c[a.first]*c[a.second]<c[b.first]*c[b.second];
}
bool cmp(ll a,ll b) {
    return a>b;
}
priority_queue<Pair> q;
int main() {
    // freopen("a.in","r",stdin);
    cin>>n>>k;
    for(ll a=0,tmp_a=1;a<=39;++a,tmp_a*=2) {
        if(tmp_a>n) break;
        for(ll b=0,tmp_b=1;b<=25;++b,tmp_b*=3) {
            if(tmp_a*tmp_b>n) break;
            for(ll c=0,tmp_c=1;c<=17;++c,tmp_c*=5) {
                if(tmp_a*tmp_b*tmp_c>n) break;
                for(ll d=0,tmp_d=1;d<=14;++d,tmp_d*=7) {
                    if(tmp_a*tmp_b*tmp_c*tmp_d>n) break;
                    if(tmp_a*tmp_b*tmp_c*tmp_d==0) continue;
                    val[++js]=tmp_a*tmp_b*tmp_c*tmp_d;
                }
            }
        }
    }
    sort(val+1,val+1+js);
    js=unique(val+1,val+1+js)-val-1;
    for(ll i=1;i<=js;++i) hasH[val[i]]=i;
    ll AAA=0;
    while(n) jl[++AAA]=n%10,n/=10;
    f[0][1][1]=1;
    for(ll i=1;i<=AAA;++i) {
        for(ll j=1;j<=js;++j) {
            for(ll k=1;k<=9;++k) {
                if(val[j]%k==0) {
                    ll w=hasH[val[j]/k];
                    if(k==jl[i]) {
                        f[i][j][1]+=f[i-1][w][1];
                        f[i][j][0]+=f[i-1][w][0];
                    } else if(k<jl[i]) {
                        f[i][j][1]+=f[i-1][w][0]+f[i-1][w][1];
                    } else {
                        f[i][j][0]+=f[i-1][w][0]+f[i-1][w][1];
                    }
                }
            }
        }
    }
    for(ll i=1;i<=js;++i) {
        for(ll j=1;j<AAA;++j)
            c[i]+=f[j][i][0]+f[j][i][1];
        c[i]+=f[AAA][i][1];
    }
    sort(c+1,c+1+js,cmp);
    for(ll i=1;i<=js;++i) q.push(Pair(i,1));
    ll ans=0;
    for(ll i=1;i<=k;++i) {
        Pair x=q.top();
        q.pop();
        ans+=c[x.first]*c[x.second]%mod;
        ans%=mod;
        q.push(Pair(x.first,x.second+1));
    }
    cout<<ans<<"\n";
    return 0;
}