BZOJ 2999 inint【数DP优化】(Ender的模拟赛)

题目描述

从起点1开始，每次选择当前数的任意一位上加上去，问得到n的最小步数以及方案数。多组数据。
例如，从1开始得到100，有很多方法，其中有下面两种方式：
A. 1-2-4-8-16-17-18-19-20-22-24-28-36-39-48-56-62-68-76-83-91-100
B. 1-2-4-8-16-17-24-28-36-39-48-56-62-68-76-83-91-100
显然，B只需要17步。
而事实上，有两种17步的方法。
C. 1-2-4-8-16-22-24-28-36-39-48-56-62-68-76-83-91-100
输入
第一行一个T
接下来T行每行一个n
输出
对于每个n输出得到n的最小步数和方案数，方案数mod 1000000007后输出
如果无法得到输出IMPOSSIBLE
数据规模（数据范围比BZOJ大）
对于20%的数据n<=10^6
对于60%的数据n<=10^9
对于100%的数据n<=10^12,T<=100

题目分析：

考试时分段打表打到1e8，结果数据无梯度只有20分QWQ
把步数和方案数作为一个结构体重载一下会好写很多。

容易发现我们只需要知道一段连续的0~8就可以一直往下递推。
没有什么好办法，只能DP。
朴素的DP是把数值当做状态一步一步转移，但这样当n>=10⁹时无法接受，想想能否一次“跳一段”。
考虑我们需要什么才能继续往下推，显然我们需要知道当前数中1~9是否出现。
那么如果我们能够预处理出一个数组$f[S][i][j]$表示末三位为$00i$，高位的1~9状态为$S$，转移到下一个$00j$的最小步数及方案，就意味着我们可以用9*9的时间进行1000的转移，这样对于10⁹的数据，我们可以跳10⁶次，剩下的一千次暴力一步一步推，复杂度为预处理+跳=$O(512\ast 9^2\ast 1000+10^6\ast 9^{2}T)$，(如果常数优秀)勉强可以通过60分（然而基本上会TLE）。

那么优化就比较自然了，预处理转移的1000是瓶颈，我们想办法用类似的“一次跳一段”的方法优化转移。设$f[d][S][i][j]$表示末$d+1$位为$00...i$，高位的1~9状态为$S$，转移到下一个$00...j$的最小步数及方案。那么我们求$f[d][S][i][j]$时，令$tmp[0][i]=(0步,1种方案)$，枚举$f[d-1][S][a][b]$转移，就可以得到从$00...i$转移到$10...k$的$tmp[1][k]$，同理，在$tmp[1][k]$的基础上再转移，可以得到$00...i$到$20...k$的步数及方案，只需要10次$f[d-1]$的转移得到$tmp[10][j]$，就得到了$f[d][S][i][j]$。

这样，对于10¹²的数据，预处理的复杂度就是$12\ast 512\ast 9\ast 10\ast 9^2\approx 40000000$
求1转移n的答案，就从高位到低位一位一位做，先令$tmp[1]=(0,1)$，如果n的第$d$位是$x$，前$d-1$位的数位状态是$S$，就用$f[d][S][i][j]$对$tmp$转移$x$次，这样一直做到最后一位，由于每次的转移都是从$00...i$到$00...j$，高位的S是定的，所以最后得到的$tmp$需要一次自转移，最后$tmp[n\%10]$就是答案。
总复杂度为$O(prepare+12\ast 9\ast 9^{2}T)$，主要消耗在预处理。

明确DP转移需要的条件来将数值压缩、整段转移进行优化。这道题和数位DP有相似之处。

Code：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int mod = 1e9+7;
const LL inf = 1ll<<60;
struct node{
	LL s;int t; node(){s=inf,t=0;}
	node(LL s,int t):s(s),t(t){}
	void operator += (const node &B){
		if(s>B.s+1) *this=B,s++;
		else if(s==B.s+1) t=(t+B.t)%mod;
	}
	void operator <<= (const node &B){
		if(s>B.s) *this=B;
		else if(s==B.s) t=(t+B.t)%mod;
	}
	node operator * (const node &B){
		return node(min(s+B.s,inf),1ll*t*B.t%mod);
	}
	void print(){
		if(t==0) puts("IMPOSSIBLE");
		else printf("%lld %d\n",s,t);
	}
}f[12][512][10][10],tmp[11][10];
void prepare(){
	for(int S=0;S<512;S++)
		for(int i=9;i>=0;i--){
			int T=i?(S|1<<(i-1)):S;
			for(int j=0;j<=8;j++)
				if(T&1<<(j+9-i)) f[0][S][i][j]=node(1,1);
				else for(int k=i+1;k<=9;k++) if(T&1<<(k-i-1)) f[0][S][i][j]+=f[0][S][k][j];
		}
	for(int d=1;d<=11;d++)
		for(int S=0;S<512;S++)
			for(int i=0;i<=8;i++){
				for(int j=0;j<=10;j++) for(int k=0;k<=8;k++) tmp[j][k]=node();
				tmp[0][i]=node(0,1);
				for(int j=0,T=S;j<=9;j++,T=S|1<<(j-1))
					for(int a=0;a<=8;a++) if(tmp[j][a].t)
						for(int b=0;b<=8;b++)
							tmp[j+1][b]<<=(tmp[j][a]*f[d-1][T][a][b]);
				for(int j=0;j<=8;j++) f[d][S][i][j]=tmp[10][j];
			}
}
int T;
LL n;
int main()
{
	freopen("inint.in","r",stdin);
	freopen("inint.out","w",stdout);
	prepare();
	scanf("%d",&T);
	while(~scanf("%lld",&n)){
		for(int i=0;i<=1;i++) for(int j=0;j<=9;j++) tmp[i][j]=node();
		int now=0,S=0,d=11; tmp[now][1]=node(0,1);
		for(LL i=1e12;d>=0;n/i%10&&(S|=1<<(n/i%10-1)),i/=10,d--)
			for(int j=0,T=S;j<n/i%10;j++,T=S|1<<(j-1),now=!now){
				for(int k=0;k<=9;k++) tmp[!now][k]=node();
				for(int a=0;a<=8;a++) if(tmp[now][a].t)
					for(int b=0;b<=8;b++)
						tmp[!now][b]<<=(tmp[now][a]*f[d][T][a][b]);
			}
		for(int i=0;i<9;i++){
			int T=i?(S|1<<(i-1)):S;
			for(int j=i+1;j<=9;j++) if(T&1<<(j-i-1))
				tmp[now][j]+=tmp[now][i];
		}
		tmp[now][n%10].print();
	}
}