做特产的网站的分析,各种软件链接网址,东莞横沥邮编,海淀做网站F. Pairwise Modulo
想到了#xff0c;但又没完全想到。。wtcl 首先 pkpk−1∑1≤ikakmodai∑1≤ikaimodakp_kp_{k-1}\sum_{1\leq ik} a_k \bmod \ a_i\sum_{1\leq ik} a_i \bmod \ a_kpkpk−1∑1≤ikakmod ai∑1≤ikaimod ak ∑1≤…F. Pairwise Modulo
想到了但又没完全想到。。wtcl 首先 pkpk−1∑1≤ikakmodai∑1≤ikaimodakp_kp_{k-1}\sum_{1\leq ik} a_k \bmod \ a_i\sum_{1\leq ik} a_i \bmod \ a_kpkpk−1∑1≤ikakmod ai∑1≤ikaimod ak
∑1≤ikakmodai∑1≤ik(ak−⌊akai⌋ai)(k−1)ak−s\sum_{1\leq ik} a_k\bmod a_i\sum_{1\leq ik}(a_k- \left \lfloor \frac{a_k}{a_i} \right \rfloor a_i)(k-1)a_k-s∑1≤ikakmodai∑1≤ik(ak−⌊aiak⌋ai)(k−1)ak−s
考虑如何计算s∑1≤ik⌊akai⌋ais\sum_{1\leq ik}\left \lfloor \frac{a_k}{a_i} \right \rfloor a_is∑1≤ik⌊aiak⌋ai
如果kai≤ak(k1)aika_i\leq a_k(k1)a_ikai≤ak(k1)ai那么⌊akai⌋aikai\left \lfloor \frac{a_k}{a_i} \right \rfloor a_ika_i⌊aiak⌋aikai这个东西用树状数组维护一下不太容易描述详细看代码。 ∑1≤ikaimodak∑1≤ik(ai−⌊aiak⌋ak)∑1≤ikai−t\sum_{1\leq ik} a_i \bmod a_k\sum_{1\leq ik}(a_i- \left \lfloor \frac{a_i}{a_k} \right \rfloor a_k)\sum_{1\leq ik}a_i-t∑1≤ikaimodak∑1≤ik(ai−⌊akai⌋ak)∑1≤ikai−t
考虑如何计算t∑1≤ik⌊aiak⌋akt\sum_{1\leq ik}\left \lfloor \frac{a_i}{a_k} \right \rfloor a_kt∑1≤ik⌊akai⌋ak
不但发现对于任意两个数u,vu,vu,v来说有下面规律⌊uv⌋vkv,u≤kv(k1)v\left \lfloor \frac{u}{v} \right \rfloor vkv,u\leq kv(k1)v⌊vu⌋vkv,u≤kv(k1)v
枚举k我们只需用统计出{ai,1≤ik}\{a_i,1\leq ik\}{ai,1≤ik}每段区间aia_iai的个数就可以计算ttt
Code
#includebits/stdc.h
using namespace std;
using lllong long;
template class Tint T rd()
{T res0;T fg1;char chgetchar();while(!isdigit(ch)) {if(ch-) fg-1;chgetchar();}while( isdigit(ch)) res(res1)(res3)(ch^48),chgetchar();return res*fg;
}
const int N300010;
template typename Tint
struct Fenwick
{const int n;T t[N];Fenwick(int n):n(n){memset(t,0,sizeof t);}void add(int k,T v){for(;kn;kk-k) t[k]v;}T qsum(int k){T v0;for(;k;k-k-k) vt[k];return v;}T get(int l,int r){return qsum(r)-qsum(l-1);}
};
int n;
int a[N];
int main()
{nrd();for(int i1;in;i) a[i]rd();Fenwickll f1(300000),f2(300000); //f1计算s f2计算tll pre0,ans0;for(int i1;in;i){ans1ll*a[i]*(i-1);//s_1anspre;//t_1ans-f1.qsum(a[i]);// s_2for(int ja[i];j300000;ja[i]){int lj,rmin(300000,ja[i]-1);ans-f2.get(l,r)*j;//t_2f1.add(l,a[i]);}f2.add(a[i],1);prea[i];printf(%lld%c,ans, \n[in]);}return 0;
}
