[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\)

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

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

注意到上面的形式，我们可以根据 \(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\n", 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)\n", 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)\n", base, D % (rten * 10) / rten, D);

		ten *= 10;

//		printf("(%lld %lld)\n", ini, tmp);

		if(!D) ans += tmp;

	}

	printf("%lld\n", ans);

	return 0;

}

巴特西

[AtCoderContest075F]Mirrored