题目大意
记 $m_i=\underbrace{1\cdots1}_{i\text{ times}}$ ，即十进制下 $i$ 个连续的 $1$ 。
现在给定一个正整数 $n$ ，找到一个无限长的整数序列 $(x_1,x_2,\cdots)$ 满足：
- $\sum_{i=1}^\infty m_ix_i=n$ 。
- 最小化 $\sum_{i=1}^\infty i|x_i|$ 。
$n\leq10^{50}.$
思路
本题是 CCPC 2020 Final Number Theory 弱化版。加强版的范围 $n\leq10^{5000}$ 。因为我的优化过不了加强版，而且我还为此花费了两天时间，所以我要为这道题送上我最儒雅的赞叹。本篇以 $|n|$ 表示 $n$ 的长度。
令 $f_{y,x}$ 表示加减所有 $m_i(i>y)$ 剩下 $x$ 的最小代价。
对于 $f_{y,x}$ 中的每一个 $x$ ，在转移至下一位中至多有两种选择：假设 $x$ 为非负的，这两种选择为 $x-km_y$ 和 $x-(k+1)m_y$ ，其中 $x-km_y$ 非负， $x-(k+1)m_y$ 非正。否则 $|x-km_y|>m_y$ 总可以减掉（加上）一个 $m_y$ 使得代价更小。
可以证明从 $f_y$ 转移到 $f_{y-1}$ 最多创造 $\mathcal{O}(1)$ 个多出来的 $x$ ，则共有 $\mathcal{O}(|n|)$ 个不同的 $x$ 。这样可以得到 $\mathcal{O}(|n|^3\log|n|)$ 的复杂度。
考虑优化掉高精度运算的 $\mathcal{O}(|n|)$ ：把数字都乘上 $9$ ，则 $m_i=\underbrace{9\cdots9}_{i\text{ times}}=1\underbrace{0\cdots0}_{i\text{ times}}-1$ 。那么每次高精度运算只用加减两位，修改位数是均摊 $\mathcal{O}(1)$ 的。
直接这么做还有一个问题：由于 $x-km_y<m_y$ ，则计算 $x-(k+1)m_y$ 就不是 $\mathcal{O}(1)$ 的了。
发现 $m_i\bmod m_{i-1} = 1$ ，可以以此引出一条性质：在 $i > 2$ 层中，由 $x$ 以正负划分可以组成两组连续的数列（如果不乘 $9$ ），乘上 $9$ 则是两个公差为 $9$ 的等差数列。如下（未乘 $9$ ）：
3453 i=1
120 -991 i=2
9 -102 8 -103 i=3
9 -2 -3 8 8 -3 -4 7 i=4
那么我们随便取一个数 $x$ ， $\mathcal{O}(|n|)$ 算 $m_y-x$ ，然后用哈希存储。
这样我们消掉了高精度运算的 $\mathcal{O}(|n|)$ ，总时间复杂度是 $\mathcal{O}(|n|^2\log|n|)$ ……吗？并不。注意到 map 在 $\log|n|$ 以外，比较两数大小也需要 $|n|$ ，因此时间复杂度还是 $\mathcal{O}(|n|^3\log|n|)$ 。似乎用 pb_ds 也只能简单消掉一个 $\log|n|$ 。接下来的超出我的能力了……
我的代码
const int N = 5010;
inline ll Read() {
ll x = 0, f = 1;
char c = getchar();
while (c != '-' && (c < '0' || c > '9')) c = getchar();
if (c == '-') f = -f, c = getchar();
while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
return x * f;
}
namespace Main {
char s[N];
int n;
struct Number {
public:
vector<int> v;
Number() {}
Number(int x) {
for (; x--; v.push_back(0));
v.push_back(1);
}
void CharToNumber(char *s) {
int len = strlen(s);
for (int i = 0; i < len; i++)
v.push_back(s[i] - '0');
reverse(v.begin(), v.end());
}
int& operator[](int x) { return v[x]; }
int length () { return v.size(); }
};
bool operator< (Number a, Number b) {
if (a.length() != b.length()) return a.length() < b.length();
for (int i = a.length() - 1; i >= 0; i--)
if (a[i] != b[i]) return a[i] < b[i];
return 0;
}
Number operator+ (Number a, Number b) {
if (b < a) swap(a, b);
for (int i = 0; i < a.length() || (i < b.length() && b[i] > 9); i++) {
if (i < a.length()) b[i] += a[i];
if (b[i] > 9) {
if (i + 1 < b.length()) b[i + 1] += b[i] / 10;
else b.v.push_back(b[i] / 10);
b[i] %= 10;
}
}
return b;
}
Number operator- (Number a,Number b) {
if (b < a) swap(a, b);
for (int i = 0; i < b.length(); i++) {
if (i < a.length()) b[i] -= a[i];
if (b[i] < 0) {
b[i] += 10;
b[i + 1]--;
}
}
for (int i = b.length() - 1; i >= 1; i--)
if (b[i] == 0) b.v.resize(i);
else break;
return b;
}
Number PlusInt (Number a, int x = 1) {
a[0] += x;
for (int j = 0; a[j] >= 10; j++) {
if (j + 1 >= a.length()) a.v.push_back(a[j] / 10);
else a[j + 1] += a[j] / 10;
a[j] %= 10;
}
return a;
}
Number MinusBit (Number a, int x, int val = 1) {
a[x] -= val;
for (int j = x; a[j] < 0; j++) {
a[j] += 10, a[j + 1]--;
}
for (int i = a.length() - 1; i >= 1; i--)
if (a[i] == 0) a.v.resize(i);
else break;
return a;
}
map<Number, int> f[N];
int main () {
for (int t = 1; t--; ) {
for (int i = 0; i <= 5000 + 1; i++) f[i].clear();
scanf ("%s", s);
Number n, m;
n.CharToNumber(s);
m = n;
for (int i = 1; i <= 8; i++) n = n + m;
f[n.length() + 1][n] = 0;
for (int i = n.length() + 1; i; i--) {
map<Number, Number> hash;
auto fir = *f[i].begin();
Number key = fir.first;
Number antiKey;
if (key.length() == 0) key.v.push_back(0);
while (PlusInt(key).length() >= i + 1) {
key = PlusInt(key);
key = MinusBit(key, i);
}
antiKey = Number(i) - PlusInt(key);
if (!(key.length() == 1 && key[0] == 0)) {
key = MinusBit(key, 0, 9);
antiKey = PlusInt(antiKey, 9);
}
hash[key] = antiKey;
hash[antiKey] = key;
Number tmp1 = key, tmp2 = antiKey;
for (int j = 0; j <= f[i].size() / 2 && !(antiKey.length() == 1 && antiKey[0] == 0); j++) {
key = PlusInt(key, 9);
antiKey = MinusBit(antiKey, 0, 9);
if (hash.find(key) != hash.end()) break;
hash[key] = antiKey;
hash[antiKey] = key;
}
key = tmp1, antiKey = tmp2;
for (int j = 0; j <= f[i].size() / 2 && !(key.length() == 1 && key[0] == 0); j++) {
antiKey = PlusInt(antiKey, 9);
key = MinusBit(key, 0, 9);
if (hash.find(key) != hash.end()) break;
hash[key] = antiKey;
hash[antiKey] = key;
}
for (auto u: f[i]) {
Number tmp = u.first;
int val = u.second;
while (PlusInt(tmp).length() >= i + 1) {
tmp = PlusInt(tmp);
tmp = MinusBit(tmp, i);
val += i;
}
if (f[i - 1].find(tmp) == f[i - 1].end()) f[i - 1][tmp] = val;
else f[i - 1][tmp] = min(f[i - 1][tmp], val);
tmp = hash[tmp];
if (f[i - 1].find(tmp) == f[i - 1].end()) f[i - 1][tmp] = val + i;
else f[i - 1][tmp] = min(f[i - 1][tmp], val + i);
}
}
Number Zero;
Zero.CharToNumber((char*)"0");
printf ("%d\n", f[0][Zero]);
}
return 0;
}
}
int main () {
// freopen("ones.in", "r", stdin);
// freopen("ones.out", "w", stdout);
Main::main();
return 0;
}
CF1487F