相关链接
题目传送门:http://arc075.contest.atcoder.jp/tasks/arc075_d
解题报告
之前PKUSC的时候考过$n + rev(n) = d$的版本
所以这一次把暴搜重新打一次就过了
Code
#include<bits/stdc++.h> #define LL long long using namespace std; int *mth, *spj, a2[100], a1[100]; inline int read() { char c=getchar(); int f=1,ret=0; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret * f; } LL DFS(LL res, LL l, LL r) { if (l <= r) { if (res == 0) { return l == r? 10: 1; } else { return 0; } } else { LL ret = 0, cur = l - r; l /= 10; r *= 10; for (int i = -9; i <= 9; i++) { if (abs(res - i * cur) < l * 11) { ret += mth[i] * DFS(res - i * cur, l, r); } } return ret; } } int main() { mth = a1 + 50; spj = a2 + 50; for (int i = 0; i <= 9; i++) { for (int j = -9; j <= 0; j++) { mth[i + j]++; } } for (int i = 1; i <= 9; i++) { for (int j = -9; j <= 0; j++) { spj[i + j]++; } } LL ans = 0, D = -read(); for (LL mx = 1e18; mx >= 10; mx /= 10) { LL delta = mx - 1; for (int i = -8; i <= 9; i++) { ans += spj[i] * DFS(D - i * delta, mx / 10, 10); } } cout<<ans<<endl; return 0; }