[NC189A]数字权重

题目大意：有一个$n$位的数，设第$i$位为$a_i$（最高位为$a_1$）。问满足$(\sum\limits_{i=2}^n(a_i-a_{i-1}))==k$的数的个数（不含前导零）

题解：发现$(\sum\limits_{i=2}^n(a_i-a_{i-1}))==k\Leftrightarrow a_n-a_1==k$。然后枚举$a_1$判断$a_n$是否合法就行了

卡点：模数为$10^9+7$，写成$10^{10}+7$

C++ Code：

#include <cstdio>

const long long mod = 1000000007;

long long n, k, ans;

long long pw(long long base, long long p) {

	long long res = 1;

	for (; p; p >>= 1, base = base * base % mod) if (p & 1) res = res * base % mod;

	return res;

}

int main() {

	scanf("%lld%lld", &n, &k);

	for (int i = 1; i < 10; i++) {

		if (i + k < 10 && i + k >= 0) (ans += pw(10, n - 2)) %= mod;

	}

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

	return 0;

}

巴特西

[NC189A]数字权重

最新文章

热门文章