https://codeforces.com/contest/1202/problem/D
题目大意
构造一个包含 $1, 3, 7$ 的字符串 $S \ (|S| \le 10^5)$ 使得其中 $1337$ 子序列的个数为 $n \ (1 \le n \le 10^9)$ 个。
简要题解
观察：
- 如果 $n$ 更小，我们可以直接 $133$ 然后加上 $n$ 个 $7$。或者 $1$ 是同理的。
- 如果用 $111333777$ 这样的结构，那么结果是 $n_1 n7 C(n3, 2)$。注意到这是一个乘积，则要求分解 $n$。但 $n$ 可能是个大素数，因此不太好。
- 考虑将结果表示为一些加法的形式。但是发现增量的搞出 $2^k$ 或 $2^k - 1$ 不是很容易。
- 注意到这样的结构 $133337733373737$，这样每个 $7$ 的贡献只和前面的 $3$ 有多少个有关。
这里终于得到了一个算法。
因为 $1337777$ 这样可以组合出任何数，所以我们先加上足够多的 $3$ 然后尽量多的减掉一些值，每次减掉 $C(n_i, 2)$，这样 $n_i$ 在 $3000$ 的时候就有 $3000 \times 2999 / 2 = 4,498,500$。配合 $200$ 多个 $7$ 就可以达到 $10^9$。然后逐渐减掉一些小的数，最后总可以靠最小的 $C(2, 2)$ 把剩下的减完。
当然最大设到 $30000$ 也可以。
复杂度
$T$：$O(3000)$
$S$：$O(|ans|)$
代码实现
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
void solve() {
int n; cin >> n;
string ans;
int f = 0;
for (int i = 3000; i >= 2; i--) {
int cur = i * (i - 1) / 2;
while (n >= cur) {
n -= cur;
ans += '7';
f = 1;
}
if (f) ans += '3';
}
ans += '3';
ans += '1';
reverse(ans.begin(), ans.end());
cout << ans << '\n';
}
int main() {
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
Next: [CF] B. You Are Given a Decimal String... - Educational Codeforces Round 70 (Rated for Div. 2)