将某些复杂度不对的dp方程降一个维度9159.com,将

作者: 编程  发布:2019-09-22

想不出什么办法能直接算的(别跟我提分块打表),不如二分答案吧:设=sum_{i=1}^n [i不是“完全平方数”]), 显然f与x正相关。再结合筛法、容斥,不难得到:
[f=sum_{i=1}^{sqrt x } mulfloorfrac{x}{i^2}rfloor]
找到那个满足f==k的x就行了。

Description

​ 对于正整数n,定义f(n)为n所含质因子的最大幂指数。例如f(1960)=f(2^3 * 5^1 * 7^2)=3, f(10007)=1, f(1)=0。
​ 给定正整数a,b,求(sumlimits _{i=1}^a sumlimits_{j=1}^b f(gcd(i,j)))。

时间复杂度从O(n*n*m)降到O(n*m)

[f_j+(sum_i-sum_j)^2+c_i>f_k+(sum_i-sum_k)^2+c_i]

[f_j+sum_i^2-2times sum_itimes sum_j+sum_j^2+c_i>f_k+sum_i^2-2times sum_itimes sum_k+sum_k^2+c_i]

[f_j-2times sum_itimes sum_j+sum_j^2>f_k-2times sum_i*sum_k+sum_k^2]

#include <bits/stdc++.h>#define int long long using namespace std;const int N=1e6+10;int mu[N],pr[N],cnt;bool vis[N];void predure() {    mu[1]=1;    for(int i=2; i<N; ++i) {        if mu[pr[++cnt]=i]=-1;        for(int j=1; j<=cnt && i*pr[j]<N; ++j) {            vis[i*pr[j]]=1;            if(i%pr[j]==0) break;            mu[i*pr[j]]=-mu[i];        }    }}int f {    int ret=0;    for(int i=1; i<=x/i; ++i) {        ret+=mu[i]*;    }    return ret;}signed main() {    predure();    int T,k;    scanf("%lld",&T);    while {        scanf("%lld",&k);        int l=1,r=k*2,mid,ans;        while {            mid=>>1;            if>=k) ans=mid,r=mid-1;            else l=mid+1;        }        printf("%lldn",ans);    }    return 0;}

Input

​ 第一行一个数T,表示询问数。
接下来T行,每行两个数a,b,表示一个询问。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define ll long long
ll i,j,k,n,m,f[3001][3001],x[3001],y[3001][3001],sum[3001],s,l,r,q[3001];
int main()
{
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)scanf("%lld",&sum[i]),s+=sum[i],sum[i]+=sum[i-1],x[i]=sum[i]<<1,f[1][i]=sum[i]*sum[i],y[1][i]=f[1][i]<<1;
    for(i=2;i<=m;i++){
        l=r=0;
        for(j=1;j<=n;j++){
            while(l<r&&y[i-1][q[l+1]]-y[i-1][q[l]]<=sum[j]*(x[q[l+1]]-x[q[l]]))l++;
            f[i][j]=f[i-1][q[l]]+(sum[j]-sum[q[l]])*(sum[j]-sum[q[l]]);
            y[i][j]=f[i][j]+sum[j]*sum[j];
            while(l<r&&(x[q[r]]-x[q[r-1]])*(y[i-1][j]-y[i-1][q[r-1]])<=(x[j]-x[q[r-1]])*(y[i-1][q[r]]-y[i-1][q[r-1]]))r--;
            q[++r]=j;
        }
    }
    printf("%lldn",f[m][n]*m-s*s);
    return 0;
}
   那么可以证明这个dp方程式具有决策单调性的。

Solution

[ begin{aligned} ans&=sum_{i=1}^asum_{j=1}^bf(gcd(i,j))\ &=sum_{x=1}^{min(n,m)}f(x)*sum(x) &sum(x)为x=gcd(i,j)的(i,j)对数,满足i和j在a和b范围内\ &=sum_{x=1}^{min(n,m)}f(x)sum_{x|d}mu(frac dx)lfloorfrac ndrfloorlfloorfrac mdrfloor\ &=sum_{x=1}^{min(n,m)}f(x)sum_{k=1}^{lfloor min(n,m)/xrfloor}mu(k)lfloorfrac n{kx}rfloorlfloorfrac m{kx}rfloor\ &=sum_{T=1}^{min(n,m)}lfloorfrac nTrfloorlfloorfrac mTrfloorsum_{d|T}f(d)mu(frac Td)\ &=sum_{T=1}^{min(n,m)}lfloorfrac nTrfloorlfloorfrac mTrfloor g(T) &令g(x)=sumlimits_{d|x}f(d)mu(frac xd) end{aligned} ]

​ 现在关键是求解(g)函数,完事后求(g)的前缀和,一样分块求(ans).

​ (1)当(x)为质数时,(g(x)=f(1)mu(x)+f(x)mu(1)=0+1=1)

​ (2)当筛到(x=p*i)时,分解质因数(x=p_1^{q_1}p_2^{q_2}...p_k^{q_k}),(frac xd=p_1^{a_1}p_2^{a_2}...p_k^{a_k}),显然(或a_i=0或1),才能对(g(x))有贡献,不然(mu({frac xd})=0). 现在只考虑满足(或a_i=0或1)的因数(d).
[ begin{aligned} g(x)&=sum_{d|x}f(d)mu(frac xd)\ &=f(x)sum_{d|x且f(d)=f(x)} mu(frac xd)+[f(x)-1]sum_{d|x且f(d)ne f(x)}mu(frac xd)\ &=-sum_{d|x且f(d)ne f(x)}mu(frac xd) end{aligned} ]
​ 要满足(f(d)ne f(x)),所有(q_i=f(x))的(p_i)的指数在(d)中都要变成(q_i-1).

​ 1° 如果所有(q_i=f(x)),那么(a_i)全部取1,则(g(x)=-mu(p_1p_2...p_k)=-(-1)^k=(-1)^{k+1}),这里有个特殊情况,如果(i)为(p)的完全平方数,即(i=p^{a_i}),(这里的(a)是最后提到的那个(a)数组),那么(x=p^{a_i+1}),则(g(x)=-mu(p)=1)

​ 2° 否则若存在(q_ine f(x)),(g(x)=0).

​ 记(A={i|q_i=f(x)},B={i|q_ine f(x)}).

​ 对于(A)中的(i),(a_i)必须取1,而(B)中的(a_i)取0或1都可以,那么
[ begin{aligned} g(x)&=-summu((prod_{iin A}p_i)*(prod_{jin B}(p_j或1))\ &=-mu(prod_{iin A}p_i)summu(prod_{jin B}(p_j或1))\ &=-(-1)^{|A|}*0&prod_{iin B}(p_j或1)有奇数个质数和偶数个质数的情况次数一样,正负抵消\ &=0 &大快人心 end{aligned} ]

​ 线性筛时,维护一个(a_i)表示(i)的最小质因子(p_{min})的指数,(b_i)表示(p_{min}^{a_i}).

​ 由于每次循环的(p)都是(x)的最小质因子,故每次更新时比较(a_i)和(a_x)是否相同,如果相同就更新,如果不相同直接等于0,这样就可以保证每一个数(x)如果存在质因子指数不同的情况,(g(x))立即等于0. 详情见代码.

#include <cstdio>
using namespace std;
typedef long long ll;
const int N=1e7+1;
int vis[N],lis[N],cnt;
ll g[N],a[N],b[N];
inline void swap(int &x,int &y){int t=x;x=y;y=t;}
inline int min(int x,int y){return x<y?x:y;}
void init(){
    for(int i=2;i<N;i++){
        if(!vis[i]){
            lis[++cnt]=i;
            a[i]=1; b[i]=i;
            g[i]=1;
        }
        for(int j=1;j<=cnt&&i*lis[j]<N;j++){
            int x=i*lis[j],p=lis[j];
            vis[x]=1;
            if(i%p==0){
                //d是i去除p后的数,i=d*p^ai, x=d*p^(ai+1) 故ax=ai+1,bx相应乘上p
                a[x]=a[i]+1;    
                b[x]=b[i]*p;
                int d=i/b[i];
                if(d==1) g[x]=1; //特殊情况(边界情况)i是p的幂 
                else g[x]=(a[x]==a[d])?-g[d]:0;  //若x满足所有指数相同,g(x)=g(d)乘上-1,否则为0
                break;
            }
            a[x]=1; b[x]=p;
            g[x]=a[i]==1?-g[i]:0; //原理同上
        }
    }
    for(int i=2;i<N;i++) g[i]+=g[i-1];
}
int main(){
    freopen("input.in","r",stdin);
    init();
    int T,a,b;
    ll ans;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&a,&b);
        if(a>b) swap(a,b);
        ans=0;
        for(int i=1,j;i<=a;i=j+1){
            j=min(a/(a/i),b/(b/i));
            ans+=1LL*(a/i)*(b/i)*(g[j]-g[i-1]);
        }
        printf("%lldn",ans);
    }
    return 0;
}

 

(【)题目(】:)

Output

​ 对于每一个询问,输出一行一个非负整数作为回答。

f[i-1][k]+sum[k]^2-(f[i-1][p]+sum[p]^2)<2*(sum[k]-sum[p])*sum[j]

   从上面的式子可以得到选择k优于选择j(不信的话可以自己展开)
Time Limit: 5000 ms Memory Limit: 512 MB

令g[i][j](i>j)为线段ij的斜率。

   显然,我们能得到一个效率为(n^2)的dp方程

  

Sample Output

​ 35793453939901
​ 14225956593420
​ 4332838845846
​ 15400094813

如果令y[i-1][t]=f[i-1][t]+sum[t]^2,x[i-1][t]=2*sum[t],

   我们注意到,对于点i来说,他的横坐标是(sum_i),因为(sum_i)是前缀和,是递增的,所以加入的点的横坐标也是递增的,那么对于每个点,我们只要把它加入维护凸包的那个队列就好了。

HINT

【数据规模】
​ T<=10000
​ 1<=a,b<=10^7

设x[i]为第i天走的路程,s为路程总和,则:

   我们先设

[sum_k=sum_{i=1}^ka_i]

[f_i=min(f_j+(sum_i-sum_j)^2+c_i)]

Sample Input

​ 4
​ 7558588 9653114
​ 6514903 4451211
​ 7425644 1189442
​ 6335198 4957

     =m*(x[1]^2+x[2]^2+x[3]^2+...+x[m]^2)-s^2

【某些不得不说的东西】:

 

(frac{上边一些与j和k相关的元素}{下边一些与j和k相关的递增的元素,注意,是递增}<或>只与i有关并且递增的常数)

则原式可化为:(y[i-1][k]-y[i-1][p])/(x[i-1][k]-x[i-1][p])<sum[j],不就是线段kp的斜率小于sum[j]吗?

【证明决策单调性】

斜率优化过程如下:

【数学归纳法】:

  1. 设(f_i=min(f_j+a_i-a_j))
  2. 假设有两个决策j和k,k>j且k优于j
  3. (f_k+a_i-a_k<f_j+a_i-a_j)
  4. (f_k-a_k<f_j-a_j)
  5. 那么对于(f_{i+1})来说选择(k)即(f_{i+1}=f_k+a_{i+1}-a_k)
  6. 而选择(j)的话即(f_{i+1}=f_j+a_{i+1}-a_j)
  7. 因为第(4)行的式子,对于(f_{i+1})选择k明显比选择j更优,同理(f_i+2)可通过(f_{i+1})得到,那么,可既可说这个dp方程具有决策单调性。

bzoj4518

   证明:若((a,b))在斜线下方,且(a<x)那么根据上面的式子((a,b)(x,y))之间的斜率会大于(2times sum_i)并且(a<x),那么(x,y)则不是最优点。若(a,b)在斜线下方,且(a>x)那么根据上面的式子((a,b)(x,y))之间的斜率会小于(2times sum_i)并且(a>x),那么(x,y)则不是最优点。

9159.com 1

9159.com 29159.com 3

   现在我们假设找到了一个点(x,y)对于(f_i)最优。我们在x点上画一条斜率为(2*sum_i)的斜线,那么,对于其他所有点,都必须在这条斜线上方。

     =[(s-x[1]*m)^2+(s-x[2]*m)^2+(s-x[3]*m)^2]+...+(s-x[m]*m)^2)]/m

  现在我们有一个序列(a),我们能把序列(a)切成若干段,对于在(i)和(j)被断开的一段序列,既(a_i..j),我们可以得到一个分数((sum_{k=i}^ja_k)^2)。我们在i位置切割一次,就会得到(c_i)的分数。那么对于整个序列a,我们希望它的总分最小,求这个分数和。

ans=[(s/m-x[1])^2+(s/m-x[2])^2+(s/m-x[3])^2+...+(s/m-x[m])^2]*m

   显然,我们可以得到一个很显然的结论,那就是这个最优解x在下凸壳上。那么我们可以通过一个队列来维护凸包,并且根据决策单调性,还有(frac{f_j-f_k+sum_j^2-sum_k^2}{sum_j-sum_k}>2*sum_i)这条斜率式,我们可以每次比对下凸壳上相邻的两个点(也就是队首元素),若队列中第二个元素比队首元素优,那么我们可以删除队首元素(决策单调性,队首元素再也用不到)。

由于m,s不变,问题可以转化为将一个长为n的序列划分成m段,求最小平方和

斜率优化

(f[i-1][k]+sum[k]^2-(f[i-1][p]+sum[p]^2))/(2*sum[k]-2*sum[p])<sum[j]

   换句话说,对于(f_i)来说,最优解x是斜率(k=2*sum_i)从下往上扫扫到点集里最优的那个点。

f[i][j]=min(f[i][k]+(sum[j]-sum[k])^2),0<k<j

【(n^2)做法】:

设p<k<j,在求f[i][j]时k比p优,于是可得如下方程:
f[i-1][k]+(sum[j]-sum[k])^2<f[i-1][p]+(sum[j]-sum[p])^2

   选择j为决策既:(f_{{i+1}}=f_j+(sum_{i+1}-sum_j)^2+c_{i+1})

代码:

   我们把((f_j-sum_j^2,sum_9159.com,j))和((f_k-sum_k^2,sum_k))分别看做坐标系上面的点,那么小于号左边的式子的含义恰好是这两个点之间的斜率。

很明显的斜率优化。

【推导斜率式】

 [f_j-2times sum_itimes sum_j+sum_j^2>f_k-2times sum_i*sum_k+sum_k^2]

从这条式子继续

[f_j-f_k+sum_j^2-sum_k^2>2times sum_i*(sum_j-sum_k)]

[frac{f_j-f_k+sum_j^2-sum_k^2}{sum_j-sum_k}>2*sum_i]  

     =s^2+m*(x[1]^2+x[2]^2+x[3]^2+...+x[m]^2)-2*(x[1]+x[2]+x[3]+...+x[m])*s

   选择k为决策既:(f_{i+1}=f_k+(sum_{i+1}-sum_k)^2+c_{i+1})

 

   那么对于(f_{{i+1}})来说:

于是在求f[i]时维护一个序列,满足对任意j(j>2),g[j][j-1]>g[j-1][j-2],则f[i][j]的最优值就从序列中斜率小于sum[j]的序号最大的线段的右端点转移。

斜率优化:

  举例子说明总是比较直观的,下面我们来看一道例题。

令f[i][j]为将长为j的序列划分成i段的最小平方和,则

   若(nleq10^5)那么这个复杂度不能令人满意,我们就要接着对他进行一些处理。
   最后我们推出来的式子一般都是长这样:

决策单调性:

   若对于(f_i)来说,选择k这个决策是最优的,那么对于(f_{i+1})到(f_n)来说,选择k之前的决策不会比选择k更优。例如:若f具有决策单调性(f_{i+1})的决策一定是k或在k后面的决策。

   如果右边的与i有关的常数不是递增的,那意味着我们要扫的答案的斜率不是递增的,那么决策单调性就会消失,我们就要用平衡树或者三分去维护。所以一般,正常,好写的斜率优化最后推出来的式子一般都形如上面那条√
   根据这条式子的定义,我们可以得到,对于(k>j),只有在满足上面式子的情况下才会k比j优

作用:

   将某些复杂度不对的dp方程降一个维度,譬如O(n^2)的dp方程,若其满足决策单调性,既可通过斜率优化对其进行降维打击,让它强行变成O(n)的。

   若(k> j)且(k)优于(j)

【证明决策单调性】:

本文由9159.com发布于编程,转载请注明出处:将某些复杂度不对的dp方程降一个维度9159.com,将

关键词:

上一篇:没有了
下一篇:没有了