自动搬运

查看原文

来自洛谷，原作者为

	Imakf **

搬运于2025-08-24 22:22:15，当前版本为作者最后更新于2020-05-19 18:52:46，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

似乎被一些不太正常的做法艹了，所以赛后加了组 HACK 数据

先讲不正经的部分分。

$\rm{testdata}\ 1(4pts)$ $a_i=0$

答案全为 -1。

$\rm{testdata}\ 8\sim9(8pts)$ $p=2$

因为 $p=2$，所以只能把 $4$ 放最后，前面直接贪心。

$\rm{testdata}\ 17\sim18(8pts)$ $\sum a_i=n$

然而出题人并不会这一档。

$\rm{testdata}\ 19\sim20(8pts)$ $a_i=n$

发现非常容易搜出结果，直接爆搜。

---

算法一：

从高位到低位贪心搜索。

期望得分：$32$。

实际得分：？？（取决于出题人心情）

算法二：

容易发现上述搜索算法在无解时一定会 TLE。

于是限制每一组数据只能跑 200ms，超过则判 -1。

期望得分：$44$。

实际得分：？？（取决于出题人心情）

---

算法三：

容易发现，这是一道 dp 题。

下面介绍一种错误的状态设计：

设 $dp_{b_1,b_4,b_5,l,q}$ 表示考虑了由高到低 $l$ 位，剩余 $b_1,b_4,b_5$ 个 $a_1,a_4,a_5$，当前模意义下为 $q$ 的最大答案（一个高精度数）。

经过状态简化可以变为 $dp_{b_1,b_4,b_5}$，含义不变。

这么设计状态为什么错误？

因为前面尽可能大，后面不一定能有解。

就算从低位到高位考虑也是不对的，因为后面尽可能大前面不一定大。

期望得分：？？（取决于出题人心情）

实际得分：N/A（出题人是懒狗，没写）。

算法四：

把原本的最优化 dp 转变为可行性 dp。

设 $dp_{b_1,b_4,b_5,l,q}$ 是否存在一个数，使得考虑了由低到高 $l$ 位，剩余 $b_1,b_4,b_5$ 个 $a_1,a_4,a_5$，当前模意义下为 $q$。

容易发现这样 dp 求解，过程是 $O(n^4p)$。

考虑如何获得答案，固定 $l=n,q=0$，枚举 $b_1,b_4,b_5$，贪心选取 $5,4,1$，获得答案。

计算答案是 $O(n^3p)$。

总复杂度 $O(Tn^4p)$

根据实现优劣可以拿到不同的分数。

期望得分：$20\sim 28$。

实际得分：N/A（出题人是懒狗，没写）。

算法五：

简化 $dp$ 状态。

将状态仅仅保留为 $dp_{b_1,b_4,b_5,q}$。

因为你可以通过 $b_1,b_4,b_5$ 直接求得当前位数 $l$。

总复杂度 $O(Tn^3p)$。

期望得分：$56$。

算法六：

继续简化 $dp$ 状态。

发现 $p$ 很小，可以直接使用 unsigned long long 进行压位。

总复杂度 $O(Tn^3)$。

期望得分：$100$。

以下为 std。

然而 std 的 dp 状态是 $l,b_1,b_4$。 然而 std 的 dp 状态是 $l,b_1,b_4$。 然而 std 的 dp 状态是 $l,b_1,b_4$

重要的事情说三遍。

最后求答案时可以进行剪枝，跑得飞快。 std 未剪枝。

#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;
#define ULL unsigned long long
#define MX (234 + 1)
#define pow10 IEE

int n ,p;
int a1 ,a4 ,a5 ,pow10[MX];
ULL dp[MX][MX][MX];
ULL LOOP(ULL x ,int bit){ // 循环左移
	bit = (bit % p + p) % p; 
	return (x << bit) | (x >> (p - bit));
}

struct BIGINT{
	char k[MX];
	int len;
	BIGINT(){memset(k ,0 ,sizeof k); len = 0;}
	void push_back(char c){k[len++] = c;} 
	bool operator <(const BIGINT &B)const{
		if(len != B.len) return len < B.len;
		for(int i = 0 ; i < len ; ++i){
			if(k[i] != B.k[i]) return k[i] < B.k[i];
		}return false;
	}
	void output(){puts(k);}
}Ans ,tmp;

void solve(){
	memset(dp ,0 ,sizeof dp); 
	Ans = BIGINT(); 
	cin >> n >> p >> a1 >> a4 >> a5;
	pow10[0] = 1;
	for(int i = 1 ; i <= n ; ++i){
		pow10[i] = pow10[i - 1] * 10 % p;
	}
	dp[0][0][0] = 1;
	for(int i = 0 ; i < n ; ++i){
		for(int j = 0 ; j <= min(i ,a1) ; ++j){
			for(int s = 0 ; s <= a4 && s + j <= i ; ++s){
				int k = i - j - s; if(k > a5) continue;
				dp[i + 1][j + 1][s] |= LOOP(dp[i][j][s] ,pow10[i] * 1 % p);
				dp[i + 1][j][s + 1] |= LOOP(dp[i][j][s] ,pow10[i] * 4 % p);
				dp[i + 1][j][s] |= LOOP(dp[i][j][s] ,pow10[i] * 5 % p);
			}
		}
	}
	for(int j = 0 ; j <= a1 ; ++j){
		for(int s = 0 ; s <= a4 ; ++s){
			int A5 = n - j - s ,A1 = j ,A4 = s;
			if(A5 < 0 || A5 > a5 || (dp[n][j][s] & 1) == 0 ) continue;
			ULL st = 1;
			tmp = BIGINT();
			for(int t = n ; t ; --t){
				// priority: 5 > 4 > 1
				if(A5 && (LOOP(st ,-pow10[t - 1] * 5) & dp[t - 1][A1][A4])){
					tmp.push_back('5');
					st = LOOP(st ,-pow10[t - 1] * 5) & dp[t - 1][A1][A4] ,--A5;
				}else if(A4 && (LOOP(st ,-pow10[t - 1] * 4) & dp[t - 1][A1][A4 - 1])){
					tmp.push_back('4');
					st = LOOP(st ,-pow10[t - 1] * 4) & dp[t - 1][A1][--A4];
				}else{
					tmp.push_back('1');
					st = LOOP(st ,-pow10[t - 1] * 1) & dp[t - 1][--A1][A4];
				}
			}
			if(Ans < tmp) Ans = tmp;
		}
	}
	if(Ans.len == 0) puts("-1");
	else Ans.output();
}

int main(){
	int T; cin >> T;
	while(T--) solve();
	return 0;
}