AtCoder Beginner Contest 221 E - LEQ(组合数学 树状数组)

简介: AtCoder Beginner Contest 221 E - LEQ(组合数学 树状数组)

linkkkk

题意

给出长度为n的序列a,问有多少种子序列满足首元素< =尾元素

思路:

假设现在已经确定了首元素的下标为x xx,尾元素的下标为y,那么方案数为2yx1。中间的每个元素都有选/不选两种可能性。

问题转化成了∑ 1 < = x < = y < = n 2 y − x − 1 [ a x < = a y ]

考虑每个元素的贡献,假设现在枚举到元素y,那么这个元素的贡献就是2 y − 1 ∗ ∑ ( 1 2 ) x计算完总贡献后计算该元素对后面元素的贡献,加上( 1 /2 ) y将1/2

转化为逆元,用树状数组维护。

代码:

// Problem: E - LEQ
// Contest: AtCoder - AtCoder Beginner Contest 221
// URL: https://atcoder.jp/contests/abc221/tasks/abc221_e
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;typedef unsigned long long ull;
typedef pair<ll,ll>PLL;typedef pair<int,int>PII;typedef pair<double,double>PDD;
#define I_int ll
inline ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
#define read read()
#define rep(i, a, b) for(int i=(a);i<=(b);++i)
#define dep(i, a, b) for(int i=(a);i>=(b);--i)
ll ksm(ll a,ll b,ll p){ll res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;}
const int maxn=4e5+7,maxm=1e6+7,mod=998244353;
int a[maxn],tr[maxn],n;
vector<int>nums;
int lowbit(int x){
  return x&-x;
}
void update(int pos,int val){
  while(pos<=n) tr[pos]=(val+tr[pos])%mod,pos+=lowbit(pos);
}
int query(int pos){
  int ans=0;
  while(pos) ans=(ans+tr[pos])%mod,pos-=lowbit(pos);
  return ans;
}
int main(){
  n=read;
  rep(i,1,n) a[i]=read,nums.push_back(a[i]);
  sort(nums.begin(),nums.end());
  nums.erase(unique(nums.begin(),nums.end()),nums.end());
  rep(i,1,n){
    a[i]=lower_bound(nums.begin(),nums.end(),a[i])-nums.begin()+1;
  }
  int ans=0,t=ksm(2,mod-2,mod);
  rep(i,1,n){
    ans=(ans+ksm(2,i-1,mod)*query(a[i])%mod)%mod;
    update(a[i],ksm(t,i,mod));
  }
  cout<<ans<<endl;
  return 0;
}


目录
相关文章
|
Windows
German Collegiate Programming Contest 2019 H . Historical Maths (二分 大数)
German Collegiate Programming Contest 2019 H . Historical Maths (二分 大数)
97 0
German Collegiate Programming Contest 2019 H . Historical Maths (二分 大数)
AtCoder Beginner Contest 226 E - Just one(dfs求连通块 组合数学)
AtCoder Beginner Contest 226 E - Just one(dfs求连通块 组合数学)
119 0
AtCoder Beginner Contest 216 G - 01Sequence (并查集 贪心 树状数组 差分约束)
AtCoder Beginner Contest 216 G - 01Sequence (并查集 贪心 树状数组 差分约束)
166 0
AtCoder Beginner Contest 133 E - Virus Tree 2(组合数学)
AtCoder Beginner Contest 133 E - Virus Tree 2(组合数学)
118 0
|
算法
AtCoder Beginner Contest 213 E - Stronger Takahashi(01BFS)
AtCoder Beginner Contest 213 E - Stronger Takahashi(01BFS)
145 0
AtCoder Beginner Contest 223 D - Restricted Permutation(建图 思维 构造 拓扑排序)
AtCoder Beginner Contest 223 D - Restricted Permutation(建图 思维 构造 拓扑排序)
139 0
|
机器学习/深度学习 人工智能 Java
AtCoder Beginner Contest 215 D - Coprime 2 (质因子分解 gcd)
AtCoder Beginner Contest 215 D - Coprime 2 (质因子分解 gcd)
122 0
AtCoder Beginner Contest 203(Sponsored by Panasonic) D.Pond(二分+二维前缀和)
AtCoder Beginner Contest 203(Sponsored by Panasonic) D.Pond(二分+二维前缀和)
102 0
|
机器学习/深度学习
AtCoder Beginner Contest 218 F - Blocked Roads (最短路径还原 思维)
AtCoder Beginner Contest 218 F - Blocked Roads (最短路径还原 思维)
106 0
AtCoder Beginner Contest 203 Pond(二分+二维前缀和)
大体思路: 二分,将原矩阵根据二分的值变成01矩阵,如果元素值> val 就变为1,否则0 对于k * k 的矩阵,统计区域内元素之和,如果 sum < ⌊k2 / 2⌋ + 1,意味着当前k * k矩阵的中位数小于x,而x是我们的答案(最小中位数), ①sum < ⌊k2 / 2⌋ + 1 情况下x取得太大,r = mid ②反之,x还可能取更小的,l = mid 但是需要注意下l的初始值,当取0 or 1的时候是会wa掉的:
261 0
AtCoder Beginner Contest 203 Pond(二分+二维前缀和)

热门文章

最新文章