NC17412. take
描述
Kanade has n boxes , the i-th box has p[i] probability to have an diamond of d[i] size.
At the beginning , Kanade has a diamond of 0 size. She will open the boxes from 1-st to n-th. When she open a box,if there is a diamond in it and it's bigger than the diamond of her , she will replace it with her diamond.
Now you need to calculate the expect number of replacements.
You only need to output the answer module 998244353.
Notice: If x%998244353=y*d %998244353 ,then we denote that x/y%998244353 =d%998244353
输入描述
The first line has one integer n.
Then there are n lines. each line has two integers p[i]*100 and d[i].
输出描述
Output the answer module 998244353
示例1
输入:
3 50 1 50 2 50 3
输出:
499122178
C++14(g++5.4) 解法, 执行用时: 87ms, 内存消耗: 3688K, 提交时间: 2020-03-16 14:00:09
#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
const int mod=998244353,inv=828542813;
int n,m,t[N],res;
struct node{int p,d,id;}q[N];
int cmp(node a,node b){return a.d==b.d?a.id<b.id:a.d>b.d;}
inline void insert(int x,int v){for(;x<=n;x+=x&(-x)) t[x]=t[x]*v%mod*inv%mod;}
inline int ask(int x){int s=1; for(;x;x-=x&(-x)) s=s*t[x]%mod; return s;}
signed main(){
cin>>n; for(int i=0;i<N;i++) t[i]=1;
for(int i=1;i<=n;i++) scanf("%lld %lld",&q[i].p,&q[i].d),q[i].id=i;
sort(q+1,q+1+n,cmp);
for(int i=1;i<=n;i++){
res=(res+ask(q[i].id-1)*q[i].p%mod*inv%mod)%mod;
insert(q[i].id,(100LL-q[i].p));
}
cout<<res;
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 133ms, 内存消耗: 8036K, 提交时间: 2020-02-28 12:23:12
#include<cstdio>
#include<map>
#include<algorithm>
#define lowbit(x) x&(-x)
#define mo 998244353
#define inv 828542813
using namespace std;
using LL=long long;
int n,d[100005],t[100005],C[100005],p[100005],ans;
map<int,int>M;
void add(int x,int d)
{
while(x<=n)
C[x]=(LL)C[x]*d%mo,x+=lowbit(x);
}
int mul(int x)
{
int res=1;
while(x)
res=(LL)res*C[x]%mo,x-=lowbit(x);
return res;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d%d",&p[i],&d[i]),p[i]=(LL)p[i]*inv%mo,t[i]=d[i],C[i]=1;
sort(t+1,t+n+1);
for(int i=1;i<=n;i++)
M[t[i]]=n-i+1;
for(int i=1;i<=n;i++)
{
ans=(ans+(LL)mul(M[d[i]])*p[i])%mo;
add(M[d[i]],(1-p[i]+mo)%mo);
}
printf("%d",ans);
return 0;
}