首页 > 其他分享 >题解 CF1265E

题解 CF1265E

时间:2023-07-17 21:57:21浏览次数:39  
标签:res cdot 题解 ll int CF1265E mod

期望 DP。

定义 \(f_i\) 表示第 \(i\) 个镜子照成功的期望天数,\(p_i\) 为第 \(i\) 天成功的概率,\(q_i\) 为第 \(i\) 天失败的概率。

根据题意容易列出方程:

\[f_i=(f_{i-1}+1)\cdot p_i+(f_{i-1}+1+f_i)\cdot q_i \]

移项得:

\[(1-q_i)\cdot f_i=(f_{i-1}+1)\cdot(p_i+q_i) \]

同除以 \((1-q_i)\) 得:

\[f_i=\frac{(f_{i-1}+1)\cdot(p_i+q_i)}{1-q_i} \]

复杂度 \(O(n\log n)\)。

code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5,mod=998244353;
ll n,f[N],p[N],q[N];
ll ksm(ll x,ll y){
  ll res=1;
  while(y){
    if(y&1)res=res*x%mod;
    y>>=1;
    x=x*x%mod;
  }
  return res;
}
int main(){
  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  cin>>n;
  for(int i=1;i<=n;++i){
    ll x;cin>>x;
    p[i]=x*ksm(100,mod-2)%mod;
    q[i]=(1-p[i]+mod)%mod;
  }
  for(int i=1;i<=n;++i)f[i]=(f[i-1]+1)*(p[i]+q[i])%mod*ksm((1-q[i]+mod)%mod,mod-2)%mod;
  cout<<f[n]<<endl;
  return 0;
}

标签:res,cdot,题解,ll,int,CF1265E,mod
From: https://www.cnblogs.com/HQJ2007/p/17561354.html

相关文章

  • 题解 CF930C
    好题啊好题。定义\(a_i\)为有多少个区间包含\(i\)。拍脑袋一想,当且仅当存在顺序的三个坐标\((i,j,k)\)满足\(a_i>a_j\)且\(a_j<a_l\)时,可以确定没有数被所有区间包含。这个结论很简单,因为如果存在,则\(a\)序列必定为一个“山峰”。而如果出现上面这种情况,说明有“山......
  • 题解 P6772 [NOI2020] 美食家
    观察数据范围,\(T\)很大,\(n\)很小,用矩乘。对于一条边\((u,v,w)\),我们将\(u\)拆成\(w-1\)个点,并连接\((u_0,u_1,0),(u_1,u_2,0)...(u_{w-2},u_{w-1},0)\)和\((u_{w-1},v_0,c_{v})\),总点数\(5n\)。将美食节按时间排序,相邻两个美食节之间用矩阵快速幂转移,然后再加上附加......
  • 题解 CF1202C
    不错的题,需要点思维和码力。容易发现,左右和上下互不影响,可以分开处理,这里以左右举例。定义向左走一格\(-1\),向右走一格\(+1\),求个前缀和找到最大值和最小值,和出现最值的最早时间与最晚时间。定义为\(l,r,l2,r2\)。只有当我们放了一个A或D使得所有最大值\(-1\)且最小值......
  • 题解 P8338 [AHOI2022] 排列
    恶心题。每次操作,相当与把第\(i\)个数置换到\(p_i\),于是可以连边。因为\(i\)和\(p_i\)互不相同,所以对于每一个点,有且仅有一条出边和一条入边,即若干个简单环。那么最少操作\(\operatorname{lcm}(a_1,a_2,a_3...a_{x-2},a_{x-1},a_x)\)次点会都回到原位。其中\(a_i\)......
  • 题解 CF840C On the Bench
    这是一篇简洁易懂的良心题解,提供了多种做法。对于两个数\(x,y\),定义\(x=n^2\cdottx,y=m^2\cdotty\)。如果\(x\cdoty\)为平方数,则说明\(tx=ty\)。所以我们可以将每个数除去其平方因子,比较相邻两数是否相等即可。F1:定义\(f_{i,j,k}\)为插入\(i\)个数、有\(j\)对......
  • 题解 P3803 【模板】多项式乘法(FFT)
    感觉题解区不是写的太高深,就是写的太高深。所以给初中、小学和幼儿园的萌新准备一篇简单易懂的良心题解~前置知识一、多项式的系数表示法和点值表示法。\(A(x)=\sum\limits_{i=0}^{n-1}a_i\cdotx^i\)系数:\((a_0,a_1,a_2...a_{n-2},a_{n-1})\)。点值:\((x_0,y_0),(x_1,y_1)...(......
  • 题解 CF41D
    基础DP题。定义\(f_{i,j,k}\)表示从第一行走到\((i,j)\),且数字总和模\(p\)等于\(k\)。转移方程为:\[f_{i+1,j-1,(k+a_{i+1,j-1})\bmodp}=\max(f_{i,j,k}+a_{i+1,j-1})\]\[f_{i+1,j+1,(k+a_{i+1,j+1})\bmodp}=\max(f_{i,j,k}+a_{i+1,j+1})\]同时还需要定义\(g_{i,j......
  • 题解 P6091 【模板】原根
    题解太高深,自己整理一份。阶的定义:若\(\gcd(a,m)=1\),则使\(a^l\equiv1\pmod{m}\)的最小的\(l\)称为\(a\)关于模\(m\)的阶,记为\(\operatorname{ord}_ma\)。阶的性质:根据欧拉定理,\(a^{\varphi(m)}\equiv1\pmod{m}\),所以\(\operatorname{ord}_ma\mid\varphi(m)\)......
  • 题解 CF417D
    \(m\le20\),状压DP。首先可以根据每个人的\(k\)从小到大排序。定义\(f_{i,j}\)表示考虑到第\(i\)个人,完成了\(j\)状态的题目,不考虑显示器所需的最小价格。转移显然为\(f_{i,j|s_i}=\min(f_{i-1,j}+x_i)\)。最终答案为\(ans=\min\limits_{i=1}^{n}f_{i,S}+b\cdotk_......
  • 题解 CF985E
    贪心+DP。先从小到大排序。定义\(f_i\)表示序列\([1,i]\)能否分组。转移为\(f_i|=f_j[a_i-a_j\led,j\lei-k+1]\)。右区间可以直接算出来,左区间可以二分或根据单调性弄个指针。定义\(sum_i=\sum\limits_{t=1}^{i}f_t\),前缀和减一下判断是否为正即可。复杂度\(O(n\lo......