当前位置: 首页 > 工具软件 > Ender > 使用案例 >

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

潘灵均
2023-12-01

题目描述

从起点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>=109时无法接受,想想能否一次“跳一段”。
考虑我们需要什么才能继续往下推,显然我们需要知道当前数中1~9是否出现。
那么如果我们能够预处理出一个数组 f [ S ] [ i ] [ j ] f[S][i][j] f[S][i][j]表示末三位为 00 i 00i 00i,高位的1~9状态为 S S S,转移到下一个 00 j 00j 00j的最小步数及方案,就意味着我们可以用9*9的时间进行1000的转移,这样对于109的数据,我们可以跳106次,剩下的一千次暴力一步一步推,复杂度为预处理+跳= O ( 512 ∗ 9 2 ∗ 1000 + 1 0 6 &NegativeThinSpace; ∗ &NegativeThinSpace; 9 2 T ) O(512*9^2*1000+10^6\!*\!9^2T) O(512921000+10692T),(如果常数优秀)勉强可以通过60分(然而基本上会TLE)。

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

这样,对于1012的数据,预处理的复杂度就是 12 &NegativeThinSpace; ∗ &NegativeThinSpace; 512 &NegativeThinSpace; ∗ &NegativeThinSpace; 9 &NegativeThinSpace; ∗ &NegativeThinSpace; 10 &NegativeThinSpace; ∗ &NegativeThinSpace; 9 2 ≈ 40000000 12\!*\!512\!*\!9\!*\!10\!*\!9^2\approx40000000 125129109240000000
求1转移n的答案,就从高位到低位一位一位做,先令 t m p [ 1 ] &NegativeThinSpace; = &NegativeThinSpace; ( 0 , 1 ) tmp[1]\!=\!(0,1) tmp[1]=(0,1),如果n的第 d d d位是 x x x,前 d − 1 d-1 d1位的数位状态是 S S S,就用 f [ d ] [ S ] [ i ] [ j ] f[d][S][i][j] f[d][S][i][j] t m p tmp tmp转移 x x x次,这样一直做到最后一位,由于每次的转移都是从 00... i 00...i 00...i 00... j 00...j 00...j,高位的S是定的,所以最后得到的 t m p tmp tmp需要一次自转移,最后 t m p [ n % 10 ] tmp[n\%10] tmp[n%10]就是答案。
总复杂度为 O ( p r e p a r e + 12 ∗ 9 ∗ 9 2 T ) O(prepare+12*9*9^2T) O(prepare+12992T),主要消耗在预处理。

明确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();
	}
}
 类似资料: