HDU20260723F 合成大 HDU

HDU20260723F 合成大 HDU

waw ，这是被出题人认为最难的一档题，我们居然做出来了。

题目描述：

构造仅包含 h ， d 和 u 的字符串 SS ，满足 ∣S∣≤3001|S|\le3001 且 SS 里恰包含 nn 个 hdu 子序列。

n≤109n\le10^9

神奇的写题历程。

这题是我和 WaterM 一起解决的。

一下是无聊的对话（回忆的，不保证百分百一样）：

……

WaterM ：你们对 F 有什么想法？

wzh ：根据 n 大小分类讨论。

WaterM ：详细点？

wzh ：大概就是如果 n<1e6n<1e6 时固定一个右边的 u ，剩下全用 hd ，变为 hd 子序列计数。 nn 大的时候就多搞点 uu ，然后再调整。

WaterM ：想想……

wzh ：大概就把 nn 按照 1,3,6⋯1,3,6\cdots 拆分。

WaterM ：不对，达不到 1e9 。

wzh ：那就在末尾补一些 hhh...ddd...uuu... 。

WaterM ：想想……

WaterM ：细节？

wzh ：估计就在开头补一些，然后后边按 1+k,3+k,6+k,⋯1+k,3+k,6+k,\cdots 拆分。

WaterM ：覆盖不到的怎么办？

wzh ：举例子。

WaterM ：就比如说 nn 被补 hhh..dd..uu.. 后很小。

WaterM ：主要会前后影响，难做。

wzh ：想想……

WaterM ：我现在会 1e9-eps 和 10001000 的倍数，看看能不能推广。

……

wzh ：我好像有一点思路。

WaterM ：[一个表情] 。

wzh ：就是固定左边 10001000 个 h ，中间 10001000 个 d ，右边 999999 个 u 。

wzh ：然后每把一个 u 那一坨的 d 往左和右会失去或获得 10001000 个子序列。

wzh ：把每一个 h 那一坨的 d 往左右会失去或获得 999999 个子序列。

WaterM ：然后干啥。

WaterM ： exgcd ？

wzh ：对。

WaterM ：这么牛。

wzh ：不过还有 1e9-eps 。

WaterM ：还有 0+eps 。

WaterM ： 0 到 1998 是吧。

WaterM ：恰巧我会做 [1e9-1e3,1e9] 。

wzh ：等等。

wzh ：为什么我不用 1000+1000+1001 ？

wzh ：这样就没有 1e9-eps 了。

WaterM ：这样中间有些地方不行。

wzh ：哪些？

WaterM ：比如 30053005 。

WaterM ：这些都是小事情。

WaterM ：有没有证明 d 的移动不超过 10001000 。

WaterM ：不然 exgcd 搞出几十和几千。

WaterM ：不就不行了。

A few minutes later.

WaterM ：那是不是可以枚举 k,k+1k,k+1 。

WaterM ：那也才 30003000 。

wzh ：或许可以。

……

hdu 多校第 88 ，还是蛮开心的。

代码（ WaterM ）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <bits/stdc++.h>
using namespace std;
#define filename "xxx" 

#define inf 0x3f3f3f3f
#define Linf 0x3f3f3f3f3f3f3f3f
#define pii pair<int, int> 
#define all(v) v.begin(), v.end()
#define upw(i, a, b) for(int i = (a); i <= (b); ++i)
#define dnw(i, a, b) for(int i = (a); i >= (b); --i)

template<class T> bool vmax(T &a, T b) { return b > a ? a = b, true : false; }
template<class T> bool vmin(T &a, T b) { return b < a ? a = b, true : false; }
template<class T> void clear(T &x) { T().swap(x); }

const int N = 10005;

#define int long long

int n;

void exgcd(int a, int &x, int b, int &y, int c) {
	if(b == 0) {
		assert(a == 1);
		x = c, y = 0;
		return;
	}
	exgcd(b, y, a % b, x, c);
	y -= (a / b) * x;
}

void WaterM() {
	cin >> n;
	if(n <= 1e7) {
		vector<int> d(3005);
		dnw(i, 1000, 1) {
			int c = i * (i + 1) / 2;
			d[i] = n / c;
			n %= c;
		}
		upw(i, 1, 1000) {
			cout << "hd";
			upw(j, 1, d[i]) cout << "u";
		}
		puts("");
		return;
	}
	tuple<int, int, int, int> res(-1, -1, -1, -1);
	dnw(k, 1000, 1) {	//放k个 h 和k+1个u
		int basic = 1000 * k * (k + 1);
		int m = basic - n;
		int x, y;
		exgcd(k + 1, x, k, y, m);
		if(x < 0) {
			int c = (-x + k - 1) / k;
			x += c * k, y -= c * (k + 1);
		}
		else if(y < 0) {
			int c = (-y + k+1 - 1) / (k + 1);
			y += c * (k + 1), x -= c * k;
		}
		if(x < 0 || y < 0) continue;
		while(x - k >= 0) x -= k, y += (k + 1);
		int flag = 0;
		while(y >= 0) {
			int lower = (x + k - 1) / k;
			int upper = 1000 - (y + k+1 - 1) / (k + 1);
			if(lower <= upper) {
				flag = 1;
				res = {k, x, y, lower};
				break;
			}
			x += k, y -= (k + 1);
		}
		if(flag) break;
	}
	auto [k, x, y, a] = res;
	cerr << k << ' ' << k + 1 << ' ' << x << ' ' << y << ": " << a << '\n';
	assert(~a);
	vector<int> u(3005), v(3005);
	u[k] = x / k;
	u[x % k] = 1;
	u[0] += a - (x / k) - 1;
	v[k + 1] = y / (k + 1);
	v[y % (k + 1)] = 1;
	v[0] += (1000 - a) - (y / (k + 1)) - 1;

	dnw(i, k, 1) {
		upw(j, 1, u[i]) cout << 'd';
		cout << 'h';
	}
	upw(j, 1, u[0] + v[0]) cout << 'd';
	upw(i, 1, k + 1) {
		cout << 'u';
		upw(j, 1, v[i]) cout << 'd';
	}
	cout << '\n';
}

signed main() {
	// freopen(filename".in", "r", stdin), freopen(filename".out", "w", stdout);
	signed _ = 1;
	scanf("%d", &_);
	upw(round, 1, _) WaterM();
	return 0;
}