解题思路

设数字 $x$ 的十进制长度为 $n$ ，第 $i$ 位数字为 $d_i$ 。

题目要求的是：

等概率选一个数位，概率为 $\frac{1}{n}$
再把这一位替换成 $0 \sim 9$ 中任意一个数字，概率为 $\frac{1}{10}$
统计新数 $x'$ 严格大于原数 $x$ 的概率

P2089.第2题-计数

1000ms

Tried: 1

Accepted: 1

Difficulty: 7

所属公司 : 阿里

算法与标签>数学

题目内容

对于给定的数字 $x$ ，任选一个数位，将其替换成 $0$ ~ $9$ 任意一个数字，得到的新数字 $x’$ 大于原数字 $x$ 的概率是多少。

可以证明答案可以表示为一个不可约分数 $\frac {p} {q}$ ，为了避免精度问题，请直接输出整数 $(p·q^{-1} mod M)$ 作为答案，其中 $M$ 为模数， $q^{-1}$ 是满足 $(q×q^{-1} mod M)=1的$ 整数。

在本题中， $mod$ 的含义是取模，例如 $4$ $mod$ $2$ 即为将 $4$ 对 $2$ 取模。

提示: $q^{-1}$ 可以使用公式 $(q^{M-2} mod M)$ 得到，例如 $M=7$ 且 $q=4$ 时， $q^{-1}$ = $(1024 mod 7)=2$ ，满足 $(4×2 mod 7)=1$ 。

输入描述

在一行上输入两个整数

$x, M (1 ≤ x ≤ 10^{100000} ; 1 ≤ M ≤ 10^9 + 7)$ 代表给定的数字、模数。

输入数据保证上述公式成立。

输出描述

在一行上输出一个整数，代表得到的新数字 $x’$ 大于原数字 $x$ 的概率。

样例1

输入

12 1000000007

输出

750000006

说明

选中第一位数字的概率为 $\frac {1} {2}$ ，替换为 $2$ ~ $9$ 都会比原数字更大，概率为 $\frac {1} {2}$ × $\frac {8} {10}$ ；
选中第二位数字的概率为 $\frac {1} {2}$ ，替换为 $3$ ~ $9$ 都会比原数字更大，概率为 $\frac {1} {2}$ × $\frac {7} {10}$ ；

综上，总概率为 $\frac {8} {20}$ + $\frac {7} {20}$ = $\frac {1} {2}$ $mod$ $M$ 。当 $q^{-1}=250000002$ 时，因为 $4×q^{-1}≡1(mod M)$ ,我们应该输出 $3×q^{-1}mod M=750000006$

编辑器加载中…

输入

预期输出（选填）

解题思路

P2089.第2题-计数

题目内容

输入描述

输出描述

样例1

Status

Development

Support

About