[abc] E - LEQ 树状数组+组合计数

前言

真简单,树状数组真简单,数论真简单 (我在口胡)

传送门 : https://atcoder.jp/contests/abc221/tasks/abc221_e

补题借鉴 : https://zhuanlan.zhihu.com/p/416410911

思路

题目需要求的是 满足 所有组数

A 1 ′ ≤ A k ′ A_{1}^{\prime} \leq A_{k}^{\prime} A1′​≤Ak′​

因此不难想象 如果我们排序之后 那么我们只需要枚举k

对于每一个k我们都求出所有可能 即 2 k 2^{k} 2k (二进制枚举中有用到)

C ( N , 0 ) + C ( N , 1 ) + C ( N , 2 ) + … + C ( N , N ) = 2 n C(N, 0)+C(N, 1)+C(N, 2)+\ldots+C(N, N)=2^{n} C(N,0)+C(N,1)+C(N,2)+…+C(N,N)=2n

因此 这题的 最终需要求的就是 : ∑ 1 ≤ i < j ≤ n 2 j − i − 1 [ a i ≤ a j ] \sum_{1 \leq i>=1; } return res; } /// 求b*x == 1 mod p /// 费马小定理 求出 x == b^(p-2) ll inv(ll x) { return qmi(x,mod - 2); } void solve() { int n; cin>>n; T.n = n; for(int i=1;i>a[i]; b[i] = a[i]; } /*离散化*/ sort(b+1,b+1+n); cc_hash_table rk; for(int i=1;i