Wannafly挑战赛13 B:Jxc军训(逆元)

题目描述

在文某路学车中学高一新生军训中，Jxc正站在太阳下站着军姿，对于这样的酷热的阳光，Jxc 表示非常不爽。

Jxc将天空看做一个n*n的矩阵，此时天上有m朵云，这些云会随机分布在m个不同的位置，同时太阳会随机出现在一个位置，Jxc想知道他被太阳晒到的概率是多少，由于他仍在站军姿，所以这个有趣的问题就交给了你。考虑到精度问题，Jxc只需要知道这个概率在对998244353取模意义下的值。

Tips：一个分数p/q在模意义下的值即p*q^-1在模意义下的值，X^p-1 $\equiv$ 1 (mod p)

输入描述:

输入只有一行，包含两个整数n、m。n和m的意义见题面.

输出描述:

第一行包含一个整数Ans，为答案

示例1

输入

2 2

输出

499122177

备注:

1 <= n, m <= 2000,m <=n^2

题意

n*n的区域里放m朵云，求jxc被太阳直射的概率

题解

可以发现jxc只要站在云下就可以避免被直射，所以很容易得到，jxc被直射的概率==1-m/(n*n)，通过通分，得到(n*n-m)/(n*n)

由于题目已经说明mod为质数，所以直接套费马小定理快速幂求逆元，最后求(n*n-m)*(n*n)^mod-2%mod即可

x^p-1 $\equiv$ 1 (mod p)这个意思是x^p-1%mod==1%mod

x^p-2 $\equiv$ x^p-1(mod p)这个意思是x^p-2%mod==x^-1%mod

代码

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long int
 4 const ll mod=998244353;
 5 ll Pow(ll x,ll n)
 6 {
 7     ll res=1;
 8     while(n)
 9     {
10         if(n&1)res=res*x%mod;
11         x=x*x%mod;
12         n>>=1;
13     }
14     return res;
15 }
16 int main()
17 {
18     ll n,m;
19     cin>>n>>m;
20     cout<<(n*n-m)*Pow(n*n,mod-2)%mod;
21     return 0;
22 }