真简单,树状数组真简单,数论真简单 (我在口胡)
传送门 : 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
