湖北省赛2022H.Hamster and Multiplication

真是没想到，原来数位dp也能滚动数组优化
题目链接
题意很简单，定义
f(x)={x,x<10f(Πixi),x≥10f(x)= \\left\\{\\begin{matrix} x,x<10 \\\\ f(\\Pi_ix_i),x≥10 \\end{matrix}\\right.f(x)={x,x<10f(Πi​xi​),x≥10​
求Σi=1nf(i)\\Sigma_{i=1}^nf(i)Σi=1n​f(i)
先说下我的“错误做法”（思路有点小问题，但其实可以改对）
$f[pos][st][fl][fl2]$代表处理到$pos$位，
当前$\mathrm{2...9}$的数量的状态为$st$（注意到有贡献的数肯定不存在某位是0，且1不影响乘积，其实这里就可以看出我这个定义可以改改），
是否贴着上界$(fl)$，
之前是否全是$0(fl2)$（最开始可以填0是因为位数不一定要和n相同）
$st$的状态隔板法计算一下就是C268=1,562,275C^8_{26}=1,562,275C268​=1,562,275（开始算错了，以为就5w个状态，不然肯定不会这么莽）
由于不知道怎么想的，认为只能从某个状态更新之后的状态，而不能每次用之前状态计算当前状态，所以dfs就不成立了（某个节点更新多次后才是最优的，根本不知道什么时候才能拿来更新别的点），于是我就采用了bfs，在实现时发现会爆内存，采用了滚动数组优化
以下是用当前思路写出来的“错误”代码，极限数据cf需要1.7s

#include<bits/stdc++.h>
using namespace std;
const int N=500002;
typedef long long ll;
unordered_map<ll,int>mp;
ll f[2][N][2][2],n,ans,v,pw[10];
bool vis[2][N][2][2];
int i,tot[N],cnt,lim,d[20];
struct node{int pos;ll v;bool fl,fl2;
};
inline int calc(ll v){//计算v状态的答案ll x=1;for (int i=7;~i;v%=pw[i],i--)for (int j=0;j<v/pw[i];j++) x*=i+2;while (x>=10){ll y=1;while (x){y*=x%10;x/=10;}x=y;}return x;
}
//pre函数预处理每个状态的映射
inline void pre(ll v,int x,int sum){//x代表当前处理x+2，v[0...7]代表[2...9] if (!mp.count(v)) mp[v]=++cnt,tot[cnt]=calc(v);if (x==8 || sum==lim) return;pre(v,x+1,sum);if (x==3 && (v%pw[1] || v%pw[3]/pw[2])) return;//处理5时不能出现2,4，剪枝if (x==4 && v%pw[4]/pw[3]) return;//处理6之前不能出现5if (x==6 && v%pw[4]/pw[3]) return;//处理8之前不能出现5v+=pw[x];pre(v,x,sum+1);v-=pw[x];
}
void doit(ll n){while (n){d[++lim]=n%10;n/=10;}
}
inline void bfs(int pos,ll v,bool fl,bool fl2){queue<node>q;q.push({pos,v,fl,fl2});int x1=pos&1,x2=x1^1;int las=pos;while (!q.empty()){pos=q.front().pos;v=q.front().v;fl=q.front().fl;fl2=q.front().fl2;q.pop();if (!pos){ans+=f[x2][mp[v]][fl][fl2]*tot[mp[v]];continue;}if (pos==las-1){x1^=1,x2^=1;memset(f[x2],0,sizeof(f[x2]));memset(vis[x2],0,sizeof(vis[x2]));las=pos;}ll t=f[x1][mp[v]][fl][fl2];int up=(fl?d[pos]:9);for (int i=!fl2;i<=up;i++){if (i==5 && (v%pw[1] || v%pw[3]/pw[2])) continue;if ((i==6 || i==8) && v%pw[4]/pw[3]) continue;if (i>1) v+=pw[i-2];int to=mp[v];f[x2][to][fl&(i==up)][fl2&(i==0)]+=t;if (!vis[x2][to][fl&(i==up)][fl2&(i==0)]){q.push({pos-1,v,fl&(i==up),fl2&(i==0)});vis[x2][to][fl&(i==up)][fl2&(i==0)]=1;}if (i>1) v-=pw[i-2];}}
}
int main(){scanf("%lld",&n);pw[0]=1;for (i=1;i<=7;i++) pw[i]=pw[i-1]*18;doit(n);pre(0,0,0);f[lim&1][1][1][1]=1;bfs(lim,v,1,1);printf("%lld",ans-1);
}

其实在写剪枝的时候，我就发现了另外一个性质：每个数可以用它的因数表示
我当时就试了一个9，拆成两个3，结果爆了，以为是错误的，后来才知道是我这么做的话，3可能有36个，而我当作18在做
其实由这个就可以发现，没必要存储完整的状态，存储所有数位的乘积即可（vp的时候脑抽没想到），状态只有36100个，大大减小了复杂度，代码也更简单：

#include<bits/stdc++.h>
using namespace std;
const int N=50002;
typedef long long ll;
unordered_map<ll,int>mp;
ll f[2][N][2][2],n,ans,v;
bool vis[2][N][2][2];
int i,tot[N],cnt,lim,d[20];
struct node{int pos;ll v;bool fl,fl2;
};
inline int calc(ll v){while (v>=10){if (mp.count(v)) return tot[mp[v]];ll x=1;while (v){x*=v%10;v/=10;}v=x;}return v;
}
inline void bfs(int pos,bool fl,bool fl2){//fl2:之前全0queue<node>q;ll v;q.push({pos,1,fl,fl2});int x1=pos&1,x2=x1^1;int las=pos; while (!q.empty()){pos=q.front().pos;v=q.front().v;fl=q.front().fl;fl2=q.front().fl2;q.pop();if (!pos){ans+=f[x2][mp[v]][fl][fl2]*tot[mp[v]];continue;}if (pos==las-1){x1^=1,x2^=1;memset(f[x2],0,sizeof(f[x2]));memset(vis[x2],0,sizeof(vis[x2]));las=pos;}ll t=f[x1][mp[v]][fl][fl2];int up=(fl?d[pos]:9);for (int i=!fl2;i<=up;i++){if (i) v*=i;if (!mp.count(v)) tot[++cnt]=calc(v),mp[v]=cnt;int to=mp[v];f[x2][to][fl&(i==up)][fl2&(i==0)]+=t;if (!vis[x2][to][fl&(i==up)][fl2&(i==0)]){q.push({pos-1,v,fl&(i==up),fl2&(i==0)});vis[x2][to][fl&(i==up)][fl2&(i==0)]=1;}if (i) v/=i;}}
}
int main(){scanf("%lld",&n);while (n){d[++lim]=n%10;n/=10;}mp[1]=++cnt,tot[1]=1;f[lim&1][1][1][1]=1;bfs(lim,1,1);printf("%lld",ans-1);
}

我过了以后甚至还想直接状态变成$f(x)$的值，但这样的话两个无关的状态也能转化了，故不可