牛客小白月赛9 A-签到(逆元性质)

62 阅读 0 评论 41 点赞

我是靠谱客的博主俊逸机器猫，最近开发中收集的这篇文章主要介绍牛客小白月赛9 A-签到(逆元性质)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接

https://ac.nowcoder.com/acm/contest/275/A

思路来源

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=37485613

心得

get到了逆元的性质，

比如说每次乘以 $(y-x)/y$ 的时候，直接乘以mod意义下的 $(y-x)*y^{_-1}$

而假设最后求的分数是 $frac{p}{q}$ ，即 $p*q^{-1}$ 时，

此时要求 $(1-frac{p}{q})$ ，只需 $(1-p*q^{-1}+mod)$ %mod即可，

也就是说，逆元世界里，没有分母，剩下的可以统一过来。

顺便在这里写下，阶乘逆元的性质

由n!=(n-1)!*n，

则由inv(n!)=inv((n-1)!)*inv(n),

两侧同乘1/inv(n)，即同乘inv(inv(n))=n知，

inv(n!)*n=inv((n-1)!)

因此，可利用inv(n)求inv(n-1)，先求得inv(maxn)后，

可预处理出阶乘逆元表，O(n)

当然用inv[i]=(mod-mod/i)*inv[mod%i]%mod（记忆化O(logn)搜索）也可，注意i<mod

2020年3月29日补充：若kx+b=0，则1/x=-k/b，有inv[i]=(-mod/i)*inv[mod%i]，加入+mod%mod，方便理解许多

求出每个的逆元之后阶乘一下。

代码

#include <iostream>
#include <algorithm> 
#include <cstring>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <functional>
const long long int INF=1e18;
const int maxn=1e5+10; 
const int mod=1e9+7;
const int MOD=998244353;
const double eps=1e-9;
typedef long long ll;
#define vi vector<int> 
#define si set<int>
#define pii pair<int,int> 
#define pi acos(-1.0)
#define pb push_back
#define mp make_pair
#define lowbit(x) (x&(-x))
#define sci(x) scanf("%d",&(x))
#define scll(x) scanf("%lld",&(x))
#define sclf(x) scanf("%lf",&(x))
#define pri(x) printf("%d",(x))
#define rep(i,j,k) for(int i=j;i<=k;++i)
#define per(i,j,k) for(int i=j;i>=k;--i)
#define mem(a,b) memset(a,b,sizeof(a)) 
using namespace std;
int n;
ll ans;
ll modpow(ll x,ll n,ll mod)
{
    ll res=1;
    while(n)
    {
        if(n&1)res=res*x;
        if(res>mod)res%=mod;
        x*=x;
        if(x>mod)x%=mod;
        n/=2;
    }
    return res;
}
int main()
{
	ans=1;
    sci(n);
    rep(i,0,n-1)
    {
    	int a,b;
    	sci(a),sci(b);
    	ans*=(b-a)*modpow(b,mod-2,mod)%mod;
    	if(ans>mod)ans%=mod;
    }
    printf("%lldn",(1-ans+mod)%mod);
    return 0;
}