当前位置:网站首页>E - Sugoroku 3(期望dp)
E - Sugoroku 3(期望dp)
2022-08-09 23:16:00 【Harris-H】
E - Sugoroku 3(期望dp)
d p i = ∑ j = i i + a i d p j a i + 1 + 1 dp_i=\dfrac{\sum_{j=i}^{i+a_i}dp_j}{a_i+1}+1 dpi=ai+1∑j=ii+aidpj+1
右边的 d p i dp_i dpi 移项得到:
a i a i + 1 d p i = ∑ j = i + 1 i + a i d p j a i + 1 + 1 \dfrac{a_i}{a_{i}+1}dp_i=\dfrac{\sum_{j=i+1}^{i+a_i}dp_j}{a_i+1}+1 ai+1aidpi=ai+1∑j=i+1i+aidpj+1
d p i = ∑ j = i + 1 i + a i d p j a i + a i + 1 a i = ( ∑ j = i + 1 i + a i d p j ) + a i + 1 a i dp_i=\dfrac{\sum_{j=i+1}^{i+a_i}dp_j}{a_i}+\dfrac{a_i+1}{a_i}=\dfrac{(\sum_{j=i+1}^{i+a_i}dp_j)+a_i+1}{a_i} dpi=ai∑j=i+1i+aidpj+aiai+1=ai(∑j=i+1i+aidpj)+ai+1
取模用逆元递推即可。
时间复杂度: O ( n ) O(n) O(n)
// Problem: E - Sugoroku 3
// Contest: AtCoder - LINE Verda Programming Contest(AtCoder Beginner Contest 263)
// URL: https://atcoder.jp/contests/abc263/tasks/abc263_e
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// Date: 2022-08-09 12:44:54
// --------by Herio--------
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=2e5+5,M=2e4+5,inf=0x3f3f3f3f,mod=998244353;
const int hashmod[4] = {
402653189,805306457,1610612741,998244353};
#define mst(a,b) memset(a,b,sizeof a)
#define db double
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define x first
#define y second
#define pb emplace_back
#define SZ(a) (int)a.size()
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define per(i,a,b) for(int i=a;i>=b;--i)
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr)
void Print(int *a,int n){
for(int i=1;i<n;i++)
printf("%d ",a[i]);
printf("%d\n",a[n]);
}
template <typename T> //x=max(x,y) x=min(x,y)
void cmx(T &x,T y){
if(x<y) x=y;
}
template <typename T>
void cmn(T &x,T y){
if(x>y) x=y;
}
int n;
ll dp[N];
ll suf[N];
ll a[N];
ll inv[N];
ll p=mod;
void init(int n){
inv[1]=1;
for(int i=2;i<=n;i++)
inv[i]=(p-p/i)*inv[p%i]%p;
}
int main(){
ll q = 1;
cin>>n;
rep(i,1,n-1) cin>>a[i];
init(n);
dp[n] = 0;
for(int i=n-1;i;i--){
dp[i] = (suf[i+1]-suf[i+a[i]+1]+a[i]+1)*inv[a[i]]%mod;
suf[i] = (suf[i+1] + dp[i])%mod;
}
printf("%lld",(dp[1]%mod+mod)%mod);
return 0;
}
边栏推荐
猜你喜欢
ES6 从入门到精通 # 13:数组的扩展方法二
Qt 之 QDateEdit 和 QTimeEdit
ES6 从入门到精通 # 14:迭代器 Iterator 的用法
YOLOV5学习笔记(七)——训练自己数据集
A summary of 6 common tools for cross-border e-commerce
【问题解决】训练和验证准确率很高,但测试准确率很低
Golden Warehouse Database KingbaseGIS User Manual (6.5. Geometry Object Editing Function)
vmware Exsi 网卡配置
今日睡眠质量记录61分
ES6 Beginner to Mastery #13: Extension Methods for Arrays 2
随机推荐
selenium和驱动安装
网络协议05 -网络层
【集训DAY3】挖金矿【二分答案】
ES6 从入门到精通 # 15:生成器 Generator 的用法
Gumbel distribution of discrete choice model
70. Stair Climbing Advanced Edition
【SSL集训DAY2】Sort【树状数组】
vmware Exsi 网卡配置
ECCV 2022 | 微软开源TinyViT :搞定小模型的预训练能力
【集训DAY4】矩形【线段树】
上交所实时行情文件汇总
SRv6 performance measurement
阿里云短信服务开通
数字钱包红海角逐,小程序生态快速引入可助力占领智慧设备入口
NotWritableError: The current user does not have write permissions when conda creates a new environment
In-depth understanding of multithreading (Part 1)
【集训DAY4】异或【字典树】
Technology feast!Huayun Data brings six topics to OpenInfra Days China
数字孪生智慧制造生产线项目实施方案,平台认知与概念
NTU General Database-Gbase-8a-Learning-04-Deploying Distributed Clusters