题解：P5863 [SEERC2018] Numbers

yuanruiqi · 2024-12-15 22:54:41 · 题解

搜索冲过去也是奇异搞笑了。

首先枚举 x,y 的长度，然后可以通过枚举最后一位确定两个数，x,y 不能有前导零，记录一下，有状态 f_{n,x,0/1,y,0/1}。记忆化后并轻度剪枝后可以通过。

不会证明复杂度，但是单点最慢 4\ \text{ms}。

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using arr = array<i64, 5>;
constexpr int maxn = 20;
i64 p[maxn];
i64 len(i64 n)
{
    for (int i=1;i<=18;++i) if (n < p[i]) return i;
    return 19;
}
bool chk(i64 n, int m)
{
    string s = to_string(n);
    if (m < s.size()) return 0;
    while (s.size() < m) s = "0" + s;
    string t = s;
    reverse(t.begin(), t.end());
    return s == t;
}
map<arr, i64> mp;
i64 f(i64 n, int x, int a, int y, int b)
{
    i64 m = len(n);
    if (!n) return a && b;
    if (x < m - 1 && y < m - 1) return 0;
    if ((!x || !y))
    {
        if (chk(n, x | y)) return 1;
        return 0;
    }
    if (mp.count(arr {n, x, a, y, b})) return mp[arr {n, x, a, y, b}];
    i64& ans = mp[arr {n, x, a, y, b}];
    for (int i=a?0:1;i<10;++i)
        for (int j=b?0:1;j<10;++j)
            if ((i + j) % 10 == n % 10)
            {
                i64 m = n - i - j;
                if (x > 1) m -= i * p[x - 1];
                if (y > 1) m -= j * p[y - 1];
                if (m < 0) continue;
                ans += f(m / 10, max(0, x - 2), 1, max(y - 2, 0), 1);
            }
    return ans;
}
void solve()
{
    i64 n;
    cin >> n;
    int m = len(n);
    i64 ans = 0;
    for (int i=1;i<=m;++i)
        for (int j=1;j<=m;++j) ans += f(n, i, 0, j, 0);
    cout << ans << '\n';
}
int main()
{
    p[0] = 1;
    for (int i=1;i<=18;++i) p[i] = p[i - 1] * 10;
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}