这场的G怎么这么毒瘤啊/kk
听说正解是DP？我爆搜头一个表示不服！
statement
找出三元组 \((S, a, b)\) 的数量，使得 \(S\) 在 \(a\) 进制下和在 \(b\) 进制下的差为 \(X\) ，其中 \(0 \leq S_i <(min(a, b, 10))\) 。
首先因为 \(X > 0\) 显然 \(S\) 不可能为 \(1\) 位数。
如果 \(S\) 为两位数，那么可以枚举 \(S\) 的十位 \(n\) ，显然满足 \(n(a - b) = X\) ，这种情况对答案的贡献是 \(min(10, b)\) 。可以把 \(b < 10\) 和 \(b \geq 10\) 分开计算。
如果 \(S\) 为三位数，可以验证 \(a,b \leq 1e5\) 。那么枚举十位 \(n\) ，个位 \(m\) 和 \(a\) ，这个时候如果存在 \(b\) 那么 \(b\) 唯一，可以通过二分求出。这种情况还是贡献 \(min(10, b)\) 。
如果 \(S\) 的位数 \(>3\) ，感性理解一下就能知道合法的三元组非常少。事实上，通过在计算器上二分可以得知，在 \(\mid S \mid = 4\) 的时候 \(a, b \leq 300\) ，在 \(\mid S \mid = 5\) 的时候 \(a, b \leq 40\) 。这个范围不禁想让我们枚举 \(S, a, b\) 。
但是经过计算， \(S\) 的位数最高可以达到 \(12\) ，在最高位填 \(1\) , \(a,b\) 分别取 \(3, 2\) 时取得。
你肯定发现了，如果位数很高，其实没有必要每一位填 \((0, 9)\) 中的每一个数。那么在已经填好的数 \(\geq\) 当前可能的最大进制的时候可以剪枝。
那么现在就可以在 略长于时限的时间内 跑完了。接下来我们还是老办法，不枚举第一位，改为在最后加上 \(min(10, b)\) 就可以 通过 这道题了。
注意实现时的一车细节。复杂度 \(\Theta(勉强能跑)\)
赠送一张表，是我估算的每一个位数下可能存在的最高进制。
| 位数 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|
| 最高进制 | 300 | 40 | 16 | 8 | 6 | 4 | 3 | 3 | 3 |
后话：我在场上的初步想出并实现了这个做法，这道题和题解是第二天写完的。
如果思考能够更缜密，
实现能够更迅速，，
细节能够更准确，，，
或许结局就会不一样吧？
\(\textcolor{green}{CSP2023rp++}\)
code:
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int P = 998244353;
const int N = 2e5+5;
template<typename T>inline void read(T &a)
{
a = 0;
int f = 1;
char c = getchar();
while(!isdigit(c))
{
if(c == '-') f = -1;
c = getchar();
}
while(isdigit(c))
a = a * 10 + c - 48,c = getchar();
a *= f;
}
template<typename T,typename ...L> inline void read(T &a,L &...l)
{
read(a),read(l...);
}
inline int Mul(int a, int b) {
return (long long)a * b % P;
}
inline int Add(int a, int b) {
return a + b >= P ? a + b - P : a + b;
}
inline void Inc(int &a, int b) {
a = Add(a, b);
}
const int dx[] = {300, 300, 300, 300, 40, 16, 8, 6, 4, 3, 3, 3};
int n, X, ans;
int qp[13][505];
ll f(ll i, ll j, int x) {
return i * x * x + j * x;
}
ll f2(vector <int> &a, int b) {
ll ans = 0;
for(int i = 0; i < int(a.size()); i++) {
ans += qp[i][b] * a[i];
}
return ans;
}
void DFS(vector<int> a, int pos) {
if(pos == 12) {
return;
}
if(*max_element(a.begin(), a.end()) >= dx[pos]) return;
//cerr<<a.size()<<' '<<pos<<endl;
for(int i = 0; i < min(min(10, dx[pos]), n); i++) {
a.emplace_back(i);
if(pos >= 3 && a[pos]) {
for(int l = *max_element(a.begin(), a.end()) + 1; l <= min(dx[pos], n); l++) {//下界
for(int j = i + 1; j <= min(dx[pos], n); j++) {
if(f2(a, j) - f2(a, l) == X) {
Inc(ans, min(l, 10));
}
}
}
}
DFS(a, pos + 1);
a.pop_back();
}
}
int main() {
read(n, X);
for(int i = 0; i <= 11; i++) {
for(int j = 1; j <= dx[i]; j++) {
int k = 1, res = i;
while(res--) {
k *= j;
}
qp[i][j] = k;
}
}
vector<int> tmp;
tmp.emplace_back(0);
DFS(tmp, 1);//不填第0位
for(int i = 1; i <= 9; i++) {
for(int j = 0; j <= 9; j++) {
//三位整数
for(int x = max(i, j) + 2; x <= min(100005, n); x++) {
int l = max(max(i, j) + 1, 2), r = x - 1, mid;
while(l < r) {
int mid = (l + r + 1) >> 1;
if(f(i, j, x) - f(i, j, mid) < X) {
r = mid - 1;
}
else {
l = mid;
}
}
if(f(i, j, x) - f(i, j, l) == X) {
Inc(ans, min(10, l));
}
}
}
}
for(int i = 1; i <= 9; i++) {
for(int k = i + 1; k < min(10, n + 1); k++) {
if(X % i == 0 && k + (X / i) <= n) {
Inc(ans, k);
}
}
if(X % i == 0) {
Inc(ans, Mul(10, max(0, n - (X / i) - 10 + 1)));
}
}
cout<<ans<<endl;
}
/*
start coding at:
finish debugging at:2023/10/1 16:00
stubid mistakes:DFS里push_back没有回溯 ，二分里面调用了mid（90%的程序员写不对二分。。。） ，循环变量重名，贡献没有和10取min
*/
/*
吾日三省吾身：
你排序了吗？
你取模了吗？
你用%lld输出long long 了吗？
1LL<<x写对了吗？
判断=0用了abs()吗？
算组合数判了a<b吗？
线段树build()了吗？
.size()加了(signed)吗？
树链剖分的DFS序是在第二次更新的吗？
修改在询问前面吗？
线段树合并到叶子结点return了吗？
__builtin_ctz后面需要加ll吗？
*/