费马小定理

定义

若 $a$ 与 $p$ 互质（即 $\gcd (a,p)=1$），则：
$$a^{p-1}\equiv 1(\mathrm{mod}p)$$
根据上述公式我们还可以推出一个公式：
$$a^{p-2}\equiv a^{-1}(\mathrm{mod}p)$$

使用条件：$p$ 需为质数。

也就是逆元。

常用来解决有除法且需要取模的问题（除法不能取模）。

应用

P10792 『SpOI - R1』笑起来最帅的小孩

期望+逆元。

比如说我们有 $1$ 个 $2$，$2$ 个 $1$，考虑所有情况：

112
112
121
121
211
211

加起来为 $888$。

数据小的情况可以直接手动例举，但如果数据大了呢？

考虑直接计算每一位的贡献。

比如说第一个 $1$ 在各位上的贡献为 $2!$，十位为 $10\times 2!$，百位为……

总共贡献：$111\times 2!$。

即 $(10^n-1)\times 2!$。

$n$ 表示数列的长度。

以此类推，所有数字的贡献总和为：
$$(\sum _{i=1}^k{x}_i\times l_i)\times (10^n-1)\times (n-1)!$$

然后还要对贡献和除以 $n!$，公式为：
$$\frac{({\sum }_{i=1}^k{x}_i\times l_i)\times (10^n-1)}{n}$$
接下来用逆元解决就好了。

实现

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=2007072007;
int t,k,x[100005],l[100005];
int kpow(int a,int b){int sum=1;while(b){if(b&1){sum=(sum*a)%mod;}a=(a*a)%mod;b/=2;}return sum;
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);for(cin>>t;t;t--){cin>>k;int n=0,sum=0;for(int i=1;i<=k;i++){cin>>x[i]>>l[i];n=(n+l[i])%mod,sum=(sum+x[i]*l[i])%mod;}cout<<(((((sum*(kpow(10,n)-1))%mod)*kpow(9,mod-2))%mod)*kpow(n,mod-2))%mod<<'\n';}return 0;
}