영롱배'ACM 레이스 라운드 #4 E --array[DP]

영롱배'ACM 레이스 라운드 #4
Start Time:2016-11-05 12:00:00 End Time:2016-11-05 17:00:00 Refresh Time:2016-11-06 21:43:46 Private
E -- array
Time Limit:3s Memory Limit:64MByte
Submissions:465Solved:140
DESCRIPTION
2 array is an array, which looks like:1,2,4,8,16,32,64......1,2,4,8,16,32,64......a1=1  | ai+1ai=2a1=1  | ai+1ai=2 Give you a number array, and your mission is to get the number of subsequences ,which is 2 array, of it. Note: 2 array is a finite array.
INPUT
There are multiple test cases.The first line is a number T (
T ≤10T ≤10), which means the number of cases.For each case, two integer
n(1≤n≤105)n(1≤n≤105).The next line contains
nn numbers
ai(1≤ai≤109)ai(1≤ai≤109)
OUTPUT
one line - the number of subsequence which is 2 array.(the answer will
% 109+7% 109+7)
SAMPLE INPUT
241 2 1 241 2 4 4
SAMPLE OUTPUT
54
       
DP가 직접 할 줄은 생각지도 못했다. 공식 문제풀이: 109109 범위 내의 22의 幂次는 3030개에 불과하다는 것을 알아차렸기 때문에 우리는 dp[30]dp[30]와 같은 dp수조를 정의했다. dp[i]dp[i]는 2i2i를 끝으로 조건을 만족시키는 하위 서열의 개수를 나타낸다.매 수를 매거하여 옮기면 복잡도 O(32n) O(32n).
AC 코드:

#include
#include

typedef long long LL;
const int MOD=1e9+7;

LL p[44],a[44];

int main()
{
	p[1]=1; 
	for(int i=2;i<=33;++i) {
     	p[i]=p[i-1]<<1; //printf("%lld %lld
",i,p[i]);	
	}
	int T; scanf("%d",&T);
	while(T--) {
		int N; scanf("%d",&N);
		memset(a,0,sizeof(a));
		for(int i=0;i