自动搬运

查看原文

来自洛谷，原作者为

	zsq259 这个家伙很懒，什么也没有留下................................................

搬运于2025-08-24 22:08:49，当前版本为作者最后更新于2020-02-13 09:56:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题解 JSOI2013 数字理论

题面

luogu5261

解析

先判掉不存在的情况:$S>K*9||P>K*9||(S*D \ \ mod \ \ 9)!=(P \ \ mod \ \ 9)$

考虑数位 dp,

首先我们可以考虑求 $k=x*D$.

设 $f[i][s1][s2][l]=0/1$ 表示是否存在一个数 $x$ ,使得

• $dight(x/D)=s1$
• $dight(x)=s2$,
• $x \ \ mod \ \ D=l$,
• 在$x$后面添加$i$位数字后能满足题目条件

其中 $dight(i)$ 表示 $i$ 的各位数字之和.

好奇怪的状态...

边界就是 $f[0][S][P][0]=1$.

再来看转移:

枚举在 $x$ 后添加一位数字 $d$,则

$f[i][s1][s2][l]|=f[i-1][s1+(l*10+d)/D][s2+d][(l*10+d)\ \ mod \ \ D]$.

其实其中的含义仔细分析一下就能明白了...

然后贪心地从高位往低位找,找到一个符合条件的就继续找下一位.

读到这里,细心的读者一定会发现这样做会TLE,然而,这样做确实会TLE...

发现当 $i\times 9+s1<S$ 或 $i\times 9+s2<P$是都是无意义的,

并且当 $s1$ 和 $l$ 确定时,$s2 \ \ mod \ \ 9$ 也能知道,因此可以将 $s2$ 除9.

然后就能奇妙地过了...

code

#include <iostream>
#include <stdio.h>
#include <cstring>
#define ll long long
#define filein(a) freopen(a".cpp","r",stdin)
#define fileout(a) freopen(a".cpp","w",stdout);
using namespace std;

inline int read(){
	int sum=0,f=1;char c=getchar();
	while((c<'0'||c>'9')&&c!=EOF){if(c=='-') f=-1;c=getchar();}
	while(c>='0'&&c<='9'&&c!=EOF){sum=sum*10+c-'0';c=getchar();}
	return sum*f;
}

const int N=101;
int K,P,S,D;
bool f[N][N*9][N][10];

int main(){
	K=read();S=read();P=read();D=read();
	if(S>K*9||P>K*9||((S*D%9)^(P%9))){puts("-1");return 0;}
	f[0][S][P/9][0]=1;
	for(int i=1;i<K;i++){
		int S_st=max(S-i*9,0),P_st=max(P-i*9,0);
		for(int j=S_st;j<=S;j++){
			for(int l=0;l<D;l++){
				int mod=(j*D+l)%9;
				for(int k=P_st/9,realk=k*9+mod;realk<=P;k++,realk+=9){
					for(int d=0;!f[i][j][k][l]&&d<10;d++){
						if(f[i-1][j+(l*10+d)/D][(realk+d)/9][(l*10+d)%D]) f[i][j][k][l]=1;
					}
				}
			}
		}
	}
	int st=D;
	while(st<D*10&&!f[K-1][st/D][(st/10+st%10)/9][st%D]) st++;
	if(st==D*10){puts("-1");return 0;}
	printf("%d",st/D);
	int I=K-1,J=st/D,K=(st/10+st%10),L=st%D;
	while(I){
		int d=0;
		while(!f[I-1][J+(L*10+d)/D][(K+d)/9][(L*10+d)%D]) d++;
		printf("%d",(L*10+d)/D);
		I--;J+=(L*10+d)/D;K+=d;L=(L*10+d)%D;
	}
	return 0;
}