[AtCoderContest075F]Mirrored

试题描述

For a positive integer (n), we denote the integer obtained by reversing the decimal notation of n (without leading zeroes) by (rev(n)). For example, (rev(123)=321) and (rev(4000)=4).

You are given a positive integer (D). How many positive integers (N) satisfy (rev(N)=N+D)?

(rev(n)) 表示 (n) 在十进制表示下的倒过来写的数，对于给定的 (D)，求有多少个正整数 (N) 满足 (rev(N) = N + D)。

输入

Input is given from Standard Input in the following format:

输出

Print the number of the positive integers (N) such that (rev(N)=N+D).

输入示例1

输出示例1

输入示例2

输出示例2

输入示例3

864197532

输出示例3

数据规模及约定

(D) is an integer.

(1 le D < 10^9)

题解

题目地址

考虑从两头向中间依次确定每一位，考虑每一位的贡献。

  abcdefg
- gfedcba

所以 (a - g) 的贡献是 ((a - g) * 999999)，下一位贡献是 ((b - f) * 999900)……所以 (D) 必须是 (9) 的倍数。令 (d = D div 9)

那么每一位的贡献依次是：

111111
 11110
  1100

上面是偶数位的情况，偶数位类似。

注意到上面的形式，我们可以根据 (d) 确定出每一位的数位差是多少。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;

int read() {
	int x = 0, f = 1; char c = getchar();
	while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
	while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
	return x * f;
}

#define maxn 15
#define LL long long

int d;
LL ans;

int main() {
	d = read();
	
	if(d % 9) return puts("0"), 0;
	d /= 9;
//	printf("d: %d
", d);
	LL ini = 0, ten = 1;
	for(int i = 1; i <= 17; i++) {
		LL tmp = 1, D = d;
		ini = ini * 10 + 1;
		LL base = ini, lten = ten, rten = 1;
		for(int j = 0; j <= (i >> 1); j++) {
//			printf("%lld * %lld [tmp *= %lld] (%lld)
", base, D % (rten * 10) / rten, 10 - abs(D % (rten * 10) / rten) - (!j ? 1 : 0), D);
			tmp *= 10 - abs(D % (rten * 10) / rten) - (!j ? 1 : 0);
			D -= base * (D % (rten * 10) / rten);
			base -= lten + rten;
			lten /= 10; rten *= 10;
		}
//		printf("%lld * %d (%lld)
", base, D % (rten * 10) / rten, D);
		ten *= 10;
//		printf("(%lld %lld)
", ini, tmp);
		if(!D) ans += tmp;
	}
	
	printf("%lld
", ans);
	
	return 0;
}