Antimatter

Elimizde n tane doğal sayıdan oluşan a dizisi var. Bu dizinin bir bitişik alt dizisini seçelim. Sonrasında bu alt dizideki sayıların başlarına + veya - koyalım. Kaç farklı durum vardır ki bu işlemler uygulandığında alt dizideki sayıların toplamı 0 olsun. Bulduğunuz cevap büyük olabileceği için 1000000007'deki modunu alın.

Input Format

1. satırda n

2. satırda n tane sayıdan oluşan a dizisi

Output Format

Cevabın mod 1000000007'deki değeri

Constraints

1 <= n <= 1000

1 <= a_i <= 1000

sum(a) <= 10000

Input

4

1 1 1 1

Output

12

Açıklama
{1+,2-},{1-,2+},{2+,3-},{2-,3+},{3+,4-},{3-,4+},{1+,2+,3-,4-},{1+,2-,3+,4-},{1+,2-,3-,4+},{1-,2+,3+,4-},{1-,2+,3-,4+} ve {1-,2-,3+,4+}
_____________________________________________

Linkler

Soru: http://codeforces.com/contest/383/problem/D
Editorial: http://codeforces.com/blog/entry/10476
_____________________________________________

Çözüm

Bu soruda knapsack'i değiştiriyoruz çünkü önemli olan bitişik alt dizileri tutmak.

Yöntem
Ek olarak başka bir knapsack arrayi (dp2) tutuyoruz. Her a dizisi elemanını geziyoruz. Her seferinde dp2 arrayini sıfırlıyoruz. Klasik knapsack olayını biraz değiştirerek yapıyoruz. dp2 arrayini dp arrayini kullanarak dolduruyoruz. Ardından dp2 arrayine ek olarak şu anki elemanın + ve - halini koyuyoruz. Sonrasında dp arrayini dp2 arrayine eşitliyoruz.

Açıklama
Normal knapsack uygulasaydık {1+,3-} veya {2-,4+} gibi toplamı 0 olan bitişik olmayan alt dizileri ekleyecektik. Başka bir dp arrayi kullanarak dediğim yolu takip etmemizin nedeni bu.

Örnek Girdi
i=1 {1+},{1-}
i=2 {1+,2+},{1-,2+},{1+,2-},{1-,2-},{2+},{2-}
i=3 {1+,2+,3+},{1-,2+,3+},{1+,2-,3+},{1-,2-,3+},{2+,3+},{2-,3+},{1+,2+,3-},{1-,2+,3-},{1+,2-,3-},{1-,2-,3-},{2+,3-},{2-,3-},{3+},{3-}
i=4 {1+,2+,3+,4+},{1-,2+,3+,4+},{1+,2-,3+,4+},{1-,2-,3+,4+},{2+,3+,4+},{2-,3+,4+},{1+,2+,3-,4+},{1-,2+,3-,4+},{1+,2-,3-,4+},{1-,2-,3-,4+},{2+,3-,4+},{2-,3-,4+},{3+,4+},{3-,4+},{1+,2+,3+,4-},{1-,2+,3+,4-},{1+,2-,3+,4-},{1-,2-,3+,4-},{2+,3+,4-},{2-,3+,4-},{1+,2+,3-,4-},{1-,2+,3-,4-},{1+,2-,3-,4-},{1-,2-,3-,4-},{2+,3-,4-},{2-,3-,4-},{3+,4-},{3-,4-},{4+},{4-}
Her i.eleman için hesaplama bittiğinde dp arrayinde bitişi i olan bitişik alt dizileri tutmuş oluyoruz.
_____________________________________________

Kod

#include <algorithm>
#include <string.h>
#include <stdio.h>
#define  maxn      1000
#define  maxs      20001
#define  mod       1000000007
using namespace std;

int n,ans;
int ar[maxn];
int dp[maxs];
int dp2[maxs];

int main()
{
  scanf("%d",&n);
  for(int i=0 ; i<n ; i++)
    scanf("%d",&ar[i]);
  for(int i=0 ; i<n ; i++)
  {
    memset(dp2,0,sizeof(dp2));
    for(int j=0 ; j<maxs ; j++)
    {
 if(j>=ar[i])     dp2[j-ar[i]]=(dp2[j-ar[i]]+dp[j])%mod;
 if(j+ar[i]<maxs) dp2[j+ar[i]]=(dp2[j+ar[i]]+dp[j])%mod;
}
dp2[10000-ar[i]]=(dp2[10000-ar[i]]+1)%mod;
dp2[10000+ar[i]]=(dp2[10000+ar[i]]+1)%mod;
for(int j=0 ; j<maxs ; j++)  dp[j]=dp2[j];
ans=(ans+dp[10000])%mod;
  }
  printf("%d\n",ans);
  return 0;
}