HDU 4913 Least common multiple

题目：Least common multiple

链接：http://acm.hdu.edu.cn/showproblem.php?pid=4913

题意：有一个集合s，包含x1,x2,...,xn，有xi=2^ai * 3^bi，然后给你a数组和b数组，求s所有子集合的最小公倍数之和。比如S={18,12,18}，那么有{18}，{12}，{18}，{18,12}，{18,18}，{12,18}，{18,12,18}，所以答案是174。

思路：

　　1. 最小公倍数，因为xi只包含两个质因子2、3，那么子集合的最小公倍数其实就是2^max(a[]) * 3^max(b[])。max(a[])就是子集合相关的a数组集合中最大的ai。

　　2. 先简化题目，如果题目中的xi = 2^ai，那么可以对x数组进行从小到大排序。那么 lcm(x0,x1,...,xi)=xi，又 i 前面包含xi的子集合数量为2^(i-1)（其实就是xj(j<i)放入集合为1，不放入集合为0），那么最后的答案为 ∑ (2^ i-1 ) * xi，也就是ans[i]=ans[i-1]+2^(i-1)*2^(ai)

　　3. 回归题目，题目中多了b数组，那么我们可以按b排序，令 x= i 前面 a的值小于ai的数量，令p1、p2、...、pk为i 前面 a的值比ai大的位置。那么ans[i] = ans[i-1] + ( 2^x * 2^ai + 2^x * 2^ap1 + 2^(x+1) * 2^ap2 + ... + 2^(x+k-1) * 2^apk ) * 3^bi。

　　3中的递推公式可以如下理解：

　　推到i 就表示i 必选，那么i 前面最小公倍数为2^ai * 3^bi 的有 2^x 个，就是 x 个 a的值比ai小的xj 选与不选的问题了。比ai大的不选（因为选了的话，最小公倍数就不是xi了）

　　然后xp1必选，也就是第一个a的值比ai大的 xj必选，又 xi 必选，剩下x个比ai小的可选可不选，有2^x种情况，这2^x种情况的最小公倍数为2^ap1 * 3^bi。

　　再接着xp2必选（注意：xi 还是必选，但xp1可选可不选），有2^(x+1)种情况，他们的最小公倍数为2^ap2 * 3^bi。

　　。。。

　　上面的递推公式只是告知ans[i]的算法，当然不能直接照样计算，因为即使你可以很容易得到 i 前面a值比ai大的位置，最坏情况下（b递增，a递减），时间复杂度也高达O(n*n)。

　　现在我们可以维护2^x * 2^aj（其实就是维护那个x值），我们建一个线段树（离散型的），孩子结点（i,i）对应a值排名为i 的xj（x数组是按b排序的），线段树的结点包含sum、cnt和mulCnt三个属性，当遍历（从1-n）到j 时，xj对应的a值排名i的线段树结点cnt置1，sum置为2^x * 2^aj，然后向上更新，现在如果问x值，就可以用线段树很快地得出来。就是1-i 中cnt已经是1的数量。而2^x * 2^ap1 + 2^(x+1) * 2^ap2 + ... + 2^(x+k-1) * 2^apk可以通过维护得到，就是说每次计算完，从i+1到n的已经置为1（就是前面已经出现过的）的sum值乘2（因为比他们小的又多了一个aj，就是x+1）。

AC代码：

 #include<stdio.h>

 #include<string.h>

 #include<math.h>

 #include<algorithm>

 #define Mod 1000000007

 using namespace std;

 typedef long long LL;

 LL qpow(LL a,LL b)

 {

   LL ret=;

   while(b)

   {

     if(b&) ret=ret*a%Mod;

     a=a*a%Mod;

     b>>=;

   }

   return ret;

 }

 struct X

 {

   int id;

   int a,b;

   int ra;           //a的排名

 };

 bool cmp1(X a,X b)  //根据a排序

 {

   return a.a<b.a;

 }

 bool cmp2(X a,X b)  //根据b排序

 {

   return a.b<b.b;

 }

 X x[];

 struct Node

 {

   LL sum,cnt;

   LL mulCnt;      //该区间乘了多少个2

   int l,r;

   int mid()

   {

     return (l+r)/;

   }

 };

 Node v[];

 void build(int l,int r,int rt)

 {

   v[rt].sum=v[rt].cnt=;

   v[rt].mulCnt=;

   v[rt].l=l;

   v[rt].r=r;

   if(l==r) return ;

   build(l,v[rt].mid(),rt<<);

   build(v[rt].mid()+,r,rt<<|);

 }

 void push_down(int rt,bool flag)

 {

   if(v[rt].l==v[rt].r)

   {

     v[rt].mulCnt=;

     return ;

   }

   v[rt<<].mulCnt+=v[rt].mulCnt;

   v[rt<<|].mulCnt+=v[rt].mulCnt;

   if(flag==)

   {

     v[rt<<].sum=v[rt<<].sum*qpow(,v[rt<<].mulCnt)%Mod;

     push_down(rt<<,);

     v[rt<<|].sum=v[rt<<|].sum*qpow(,v[rt<<|].mulCnt)%Mod;

     push_down(rt<<|,);

   }

   v[rt].mulCnt=;

 }

 LL look_cnt(int l,int r,int rt)

 {

   if(l==v[rt].l&&r==v[rt].r) return v[rt].cnt;

   int mid=v[rt].mid();

   if(l>mid) return look_cnt(l,r,rt<<|);

   else if(r<=mid) return look_cnt(l,r,rt<<);

   else return look_cnt(l,mid,rt<<)+look_cnt(mid+,r,rt<<|);

 }

 LL look_sum(int l,int r,int rt)

 {

   if(l==v[rt].l&&r==v[rt].r)

   {

     v[rt].sum=v[rt].sum*qpow(2LL,v[rt].mulCnt)%Mod;

     push_down(rt,);

     return v[rt].sum;

   }

   push_down(rt,);

   int mid=v[rt].mid();

   LL ret;

   if(l>mid) ret=look_sum(l,r,rt<<|);

   else if(r<=mid) ret=look_sum(l,r,rt<<);

   else ret=(look_sum(l,mid,rt<<)+look_sum(mid+,r,rt<<|))%Mod;

   v[rt].sum=(v[rt<<].sum+v[rt<<|].sum)%Mod;

   return ret;

 }

 void update(int ra,int a,int rt)

 {

   if(v[rt].l==v[rt].r)

   {

     v[rt].cnt=;

     LL x = ra== ?  :look_cnt(,ra-,);  //x 就是在a的前面（按b排序后）排名比a小的数量

     v[rt].sum=qpow(,x+a);

     v[rt].mulCnt=;

     return ;

   }

   push_down(rt,);

   if(ra<=v[rt].mid())

     update(ra,a,rt<<);

   else update(ra,a,rt<<|);

   v[rt].cnt=v[rt<<].cnt+v[rt<<|].cnt;

   v[rt].sum=(v[rt<<].sum+v[rt<<|].sum)%Mod;

 }

 void mul(int l,int r,int rt)

 {

   if(v[rt].l==l&&v[rt].r==r)

   {

     v[rt].mulCnt++;

     v[rt].sum=v[rt].sum*qpow(2LL,v[rt].mulCnt)%Mod;

     push_down(rt,);

     return ;

   }

   push_down(rt,);

   if(r<=v[rt].mid()) mul(l,r,rt<<);

   else if(l>v[rt].mid()) mul(l,r,rt<<|);

   else

   {

     mul(l,v[rt].mid(),rt<<);

     mul(v[rt].mid()+,r,rt<<|);

   }

   v[rt].sum=(v[rt<<].sum+v[rt<<|].sum)%Mod;

 }

 int main()

 {

   int n;

   while(scanf("%d",&n)!=EOF)

   {

     build(,n-,);

     for(int i=;i<n;i++)

     {

       scanf("%d%d",&x[i].a,&x[i].b);

       x[i].id=i;

     }

     sort(x,x+n,cmp1);

     for(int i=;i<n;i++) x[i].ra=i;

     sort(x,x+n,cmp2);

     LL ans=;

     for(int i=;i<n;i++)

     {

       update(x[i].ra,x[i].a,);

       ans = (ans + look_sum(x[i].ra,n-,)*qpow(3LL,x[i].b))%Mod;

       if(x[i].ra!=n-) mul(x[i].ra+,n-,);

     }

     printf("%I64d\n",ans);

   }

   return ;

 }

巴特西

HDU 4913 Least common multiple

最新文章

热门文章