233

$\sum_{i=1}^n i^k$

打个模拟赛,自认为写了$O(mn)$的很稳,但事实上是$O(mn^2)$,才发现自己不会主定理,就记录在这儿好了

先把主定理抄在这里:

$a\ge 1,b>1$是常数,$f(n)$是一个函数,$T(n)$是定义在非负整数上的递归式:

其中我们将$\frac{n}{b}$解释为$\lfloor \frac{n}{b} \rfloor$或$\lceil \frac{n}{b} \rceil$。那么$T(n)$有如下渐进界:

  1. 若对于某个常数$\varepsilon>0$有$f(n)=O (n^{log_{b}a-\varepsilon})$,则$T(n)=\Theta (n^{log_{b}a})$.

  2. 若$f(n)=\Theta(n^{log_{b}a})$,则$T(n)=\Theta(n^{log_{b}a}lgn)$.

  3. 若对于某个常数$\varepsilon>0$有,$f(n)=\Omega (n^{log_{b}a-\varepsilon})$,且对于某个常数$c<1$和足够大的$n$有$af(\frac{n}{b})\leq cf(n)$,则$T(n)=\Theta(f(n))$.

然后我很傻逼的这么写的

void solve(int l,int r,int ql,int qr,int v){
    if(ql>qr)return;
    if(ql==qr) {
        p[ql] = (p[ql] + 1LL*(r-l+1)*(n-v-1)%MOD*(n-v-1))%MOD;
    }
    else{
        int mid=l+r>>1;
        int t=upper_bound(a+1,a+n+1,mid)-a;
        solve(l,mid,ql,t-1,v+qr-t+1),solve(mid+1,r,t,qr,v);
        solve(l,mid,ql,t-1,v),solve(mid+1,r,t,qr,v+t-ql);
    }
}