首页 > 其他分享 >费马小定理 逆元 期望dp

费马小定理 逆元 期望dp

时间:2024-05-13 20:10:38浏览次数:31  
标签:费马 int long 逆元 100010 ans define dp mod

p8774

include<bits/stdc++.h>

using namespace std;

define int long long

define f(i, a, b) for(int i = (a); i <= (b); i++)

define cl(i, n) i.clear(),i.resize(n);

define endl '\n'

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int inf = 1e9;
void cmax(int &x, int y) {if(x < y) x = y;}
void cmin(int &x, int y) {if(x > y) x = y;}
int x[100100], y[100010];
const int mod = 998244353;
int p[100010], q[100010], c[100010];
int qpow(int x, int k) {
int ans = 1;
while(k){
if(k&1) ans=ansx%mod;
x=x
x%mod;
k>>=1;
}
return ans;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
time_t start = clock();
//think twice,code once.
//think once,debug forever.
int n; cin >> n;
f(i, 0, n - 1) {
cin >> x[i] >> y[i];
p[i] = x[i] * qpow(y[i], mod - 2) % mod;
}
q[n-1]=p[n-1];
c[n - 1] = 1;
for(int i = n - 2; i >= 0; i--) {
q[i] = ((1 - p[i] + mod) % mod) * q[i + 1] % mod + p[i];
q[i] %= mod;
c[i] = (1 - p[i] + mod) %mod*c[i+1]%mod + 1;
}
cout << c[0] * qpow((1 - q[0] + mod) % mod, mod - 2) % mod;
time_t finish = clock();
//cout << "time used:" << (finish-start) * 1.0 / CLOCKS_PER_SEC <<"s"<< endl;
return 0;
}

标签:费马,int,long,逆元,100010,ans,define,dp,mod
From: https://www.cnblogs.com/anlan-woaiyuanshen/p/18189878

相关文章

  • m基于遗传优化的LDPC码OMS译码算法最优偏移参数计算和误码率matlab仿真
    1.算法仿真效果matlab2022a仿真结果如下:   2.算法涉及理论知识概要       低密度奇偶校验码(Low-DensityParity-CheckCodes,LDPCcodes)因其优秀的纠错能力和接近香农极限的性能而广泛应用于现代通信系统中。有序统计译码(OrderedStatisticsDecoding,OSD)......
  • [笔记](更新中)树形dp-中(树上背包)
    树上背包是树形dp的常见模型,通常是分组背包的变形。引入:二叉苹果树P2015二叉苹果树题意简述:在一个二叉树中,每个边有一个权值。我们要保留\(Q\)条边组成的连通分量(必须包含根节点),求边权和最大值。我们思考,从节点\(1\)(根节点)开始保留\(Q\)条边,最大答案是什么?我们分出\(3\)种......
  • rdp利用技巧总结
    近期在项目中管理员在rdp挂载之后搞掉了管理员,想着有时间就整理下针对rdp的利用方法。针对挂盘的利用方法复制文件这个不多说,可以根据的不同的挂盘来决定是拖文件还是放启动项。有一些自动文件监控和拷贝的应用,如:https://github.com/cnucky/DarkGuardianDarkGuardian是一款用于监......
  • TheAlgorithms/C - 各种基础算法、数据结构的 C 语言实现+armink/SFUD - 一款基于 JED
    1、OpenMV-RT-基于恩智浦i.MXRT系列的开源机器视觉AI模块OpenMV-RT是一款基于恩智浦最近主打的i.MXRT超高性能系列MCU的视觉模块,模块设计者是恩智浦大牛工程师宋岩(对,就是ARMCortex-M3权威指南中文版作者)。模块源代码: https://github.com/RockySong/micropython......
  • [动态规划] 背包 dp
    背包dpAcWing278.数字组合\(n\)个数就是$n$个物品,每个物品的价值就是它本身的数值,只能用一次,要求价值和为\(m\)的方案数。直接01背包即可。intn,m;inta[N],f[M];signedmain(){cin>>n>>m;for(rinti=1;i<=n;i++)cin>>a[i];mem......
  • [动态规划] 线性 dp
    线性dpSP15637GNYR04H按照编号从小到大摆放所有人每个人都只能放在已经存在的某个人的后面(除第一行外)任何一行的人数都不能比后一行多状态表示:\(f[a][b][c][d][e]\)表示第一行\(a\)个人,第二行\(b\)个人,...,第五行\(e\)个人的合法方案数然后在每个状态下......
  • 两个问题类似的dp,二者有时间复杂度的不同
    1.https://vjudge.net/problem/POJ-2229/origin(这个问题是以2的倍数为物品的背包)1#include<iostream>#include<cstdio>#include<fstream>#include<algorithm>#include<cmath>#include<deque>#include<vector>#include<que......
  • Intel 显卡单机多卡 FSDP 模型 checkpointing 时 Assert Out
    Intel显卡单机多卡FSDP模型checkpointing时AssertOut Intel显卡单机多卡FSDP模型checkpointing时AssertOut现象根因顺藤摸瓜抽丝剥茧解法最后的话现象使用HuggingFaceTrainer在单机多卡环境下对LLAMA2-7B进行LoRAfinetuning时,......
  • Freerdp基本参数说明
    Freerdp基本参数说明语法:xfreerdp[file][options][/v:<server>[:port]] 基础参数: /v:主机IP地址 /u:登录账号 /p:登录密码 /f 全屏显示 /port:3389 端口定义 /version版本查询 /help帮助查询 扩展参数: /bpp:[8/16/24/32] 画面效果和流畅度 /sound:sys:pul......
  • 一道DP(2024ICPC武汉邀请赛A)-shaking trees
    ShakingTrees题外话这题易哥哥跟我说这题的时候,点明了这题是关于高度\(100\)的\(O(n^3)\)或者\(O(n^4)\)的dp,还有提出切割点的概念使序列化。dp是真的,序列化也是真的。只能说易哥哥我的神。不过其实切割点是根据树形态而变的,之前一直以为是不变的,歪了好久。不知道是我没get到......