JZOJ__Day 9:【普及模拟】算法学习(sfxx)

题目描述

自从学习了动态规划后，Famer KXP对动态规划的热爱便一发不可收拾，每天都想找点题做，一天，他找到了一道题，但是不会做，于是，他找到了你。题目如下：
给出N个无序不重复的数，再有M个询问，每次询问一个数是否在那N个数中，若在，则ans增加2^K,K为该数在原数列中的位置。
由于ans过大，所以只要求你输出ans mod 10^9+7。

输入

第一行，两个数N,M，第二行N个数，第三行M个数。

输出

输出最终答案。

样例输入

5 5
1 3 4 6 5
1 8 1 3 6

样例输出

数据范围限制

30% 0< N,M<100
50% 0< N,M<10000
100% 0< N,M<100000
输入的数均在2^31 以内

分析
理论时间复杂度：N*logN*logN
正解：动态规划（骗人的）
题目背景坑人的：
30%可以暴力拿到；
50%可以用二分查找或者快速幂其一得到；

正解为二分查找+快速幂。

程序：

var
a,p:array[0..100000]of int64;
i:longint;
n,m,ans,w,wz:int64;

function f(b1,p1,k1:longint):int64;
var
l,t,bz:int64;
i:longint;
a1:array[1..32]of longint;
begin
    l:=0;t:=p1;
    while t<>0 do
    begin
        inc(l);
        a1[l]:=t mod 2;
        t:=t div 2;
    end;
    bz:=1;
    for i:=l downto 1 do
    begin
        t:=bz*bz mod k1;
        if a1[i]=1 then bz:=b1 mod k1 *t mod k1 else bz:=t;
    end;
    exit(bz);
end;

procedure kp(l,r:longint);
var
i,j:longint;
mid:int64;
begin
    if l>=r then exit;
    i:=l;j:=r;mid:=a[(i+j) div 2];
    repeat
         while a[i]<mid do inc(i);
         while a[j]>mid do dec(j);
         if i<=j then
         begin
             a[0]:=a[i];a[i]:=a[j];a[j]:=a[0];
             p[0]:=p[i];p[i]:=p[j];p[j]:=p[0];
             inc(i);dec(j);
         end;
    until i>j;
    kp(l,j);
    kp(i,r);
end;

function search(k:int64):longint;
var
l,r,mid:int64;
begin
    l:=1;r:=n;
    mid:=(l+r) div 2;
    while (a[mid]<>k)and(l<=r) do
    begin
        if a[mid]>k then r:=mid-1 else l:=mid+1;
        mid:=(l+r) div 2;
    end;
    if l>r then exit(0);
    exit(mid);
end;


begin
    assign(input,'sfxx.in');
    reset(input);
    assign(output,'sfxx.out');
    rewrite(output);
    readln(n,m);
    for i:=1 to n do
    begin
        read(a[i]);
        p[i]:=i;
    end;
    kp(1,n);
    readln;
    ans:=0;
    for i:=1 to m do
    begin
        read(w);
        wz:=search(w);
        if wz>0 then ans:=ans+f(2,p[wz],1000000007);
    end;
    write(ans mod 1000000007);
    close(input);
    close(output);
end.