題目描述

自從學習了動態規劃后，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

樣例輸出

24

數據范圍限制

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; beginl:=0;t:=p1;while t<>0 dobegininc(l);a1[l]:=t mod 2;t:=t div 2;end;bz:=1;for i:=l downto 1 dobegint:=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; beginif l>=r then exit;i:=l;j:=r;mid:=a[(i+j) div 2];repeatwhile a[i]<mid do inc(i);while a[j]>mid do dec(j);if i<=j thenbegina[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; beginl:=1;r:=n;mid:=(l+r) div 2;while (a[mid]<>k)and(l<=r) dobeginif 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;beginassign(input,'sfxx.in');reset(input);assign(output,'sfxx.out');rewrite(output);readln(n,m);for i:=1 to n dobeginread(a[i]);p[i]:=i;end;kp(1,n);readln;ans:=0;for i:=1 to m dobeginread(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.

轉載于:https://www.cnblogs.com/YYC-0304/p/9500083.html

總結

以上是生活随笔為你收集整理的JZOJ__Day 9:【普及模拟】算法学习(sfxx)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。