链接:https://ac.nowcoder.com/acm/contest/373/B
来源:牛客网
 

时间限制:C/C++ 2秒,其他语言4秒
空间限制:C/C++ 32768K,其他语言65536K
64bit IO Format: %lld

题目描述

在欧美,“666”是个令人极其厌恶和忌讳的数,被称为“野兽数”。
相传,尼禄,这位历史上以暴君著称的古罗马皇帝,在一次罗马大火后,无端指控是基督徒焚烧了罗马,并对他们进行大肆镇压。尼禄死后,部分基督徒出于对尼禄的恐惧,相信他并没有死去,而且还会回到罗马来。圣经《新约·启示录》中说,有一头野兽“因伤致死,但是它的致命伤又治好了”。“你所看见的兽先前有,如今没有,将要从无底坑里上来……可以计算野兽的数目,他的数目是六百六十六。” 基督徒把“666”称为“野兽数”,相信尼禄就是复活的野兽。
关于“野兽数666”有许多趣闻。比如:
美国前总统里根在其离任前,曾打算退休后移居贝莱尔市克劳德大街666号别墅,然而当他得知这一邪恶的门牌号时,顿时大惊失色。
无独有偶,在尼克松当政时,国务卿基辛格博士也碰上了“666”的调侃。美国著名数学科普作家马丁·加德纳在其名著《不可思议的矩阵博士》中,采用以代码数字替换英文字母的方式,把26个英文字母变成一个以6为首项、公差为6的等差数列:
A(6),B(12),C(18),D(24),E(30),F(36),G(42),H(48),I(54), J(60),K(66),L(72),M(78),N(84),O(90),P(96),Q(102),R(108),S(114),T(120),U(126),V(132),W(138),X(144),Y(150),Z(156)。
然后,把基辛格(Kissinger)的姓氏字母,变换为代码数字求和:66+54+114+114+54+84+42+30+108=666,正好是个“野兽数”。
以前对希特勒和墨索里尼也进行过类似的计算。并且,经过一些有心人的“考证”,许多坏事、恶事都与“野兽数666”有关。比如,“666”就正好是赌场轮盘上数字的和。所以,西方人甚至不少名流、学者都对“野兽数666”讳莫如深。
 
不过在数学上,666的确有许多奇妙之处。如:
 1、666是前七个素数的平方和  2^2+3^2+5^2+7^2+11^2+13^2+17^2=666 
 2、 (6+6+6)+(6^3+6^3+6^3)=666 。
 3、 (6+6+6)+2×(6+6+6)^2=666 。
 4、 1^3+2^3+3^3+4^3+5^3+6^3+5^3+4^3+3^3+2^3+1^3=666 。
 ---废话到此为止 

 

lililalala正在玩一种有 N N个回合的回合制RPG游戏,初始分数为0,第 i i个回合lililalala有如下两种选择。

    A.将分数加上 ai
    B.将分数 ×-1 

lililalala同样也很讨厌野兽数 666 ,但是他很却喜欢数字 -666 。他想知道有多少种不同的方案使得 N N个回合后分数变为 -666 且在任何一个回合之后分数都不为 666。

如果两种方案有任何一个回合选择不同,就认为这两种方案是不同的。

答案请对 10^8+7 7取模。

输入描述:


 

输入包含两行。

第一行一个整数 N(1≤N≤300) 。

第二行 N N个整数 a1a2a3...an(-666≤ a1a2a3...an≤666) 。

输出描述:

输出一行一个整数--符合条件的不同方案数。

示例1

输入

复制

3
-333 -333 -333

输出

复制

1

说明


 

仅一种符合条件的方案

第一回合选择将分数 ×−1。分数为 0

第二回合选择将分数加上 -333。分数为 -333

第三回合选择将分数加上 -333。分数为 -666

示例2

输入

复制

3
333 333 333

输出

复制

0

示例3

输入

复制

13
518 -643 -503 424 -76 -18 547 26 51 -647 -457 -5 329

输出

复制

2

题意:不解释,很好理解~

题解:dp[i][j]+=dp[i-1][j-a[i]]+dp[i-1][-j];表示第i个回合后,分数为j的方案数,直接开二维超内存,所以需要滚动,得出:

dp[i&1][j]+=dp[!(i&1)][j-a[i]]+dp[!(i&1)][-j],防止下表是负数,都加上一个很大的数,即dp[i&1][j+MAX]+=dp[!(i&1)][j-a[i]+MAX]+dp[!(i&1)][-j+MAX],这样就可以了。

上代码:

#include <iostream>
#include <cstring>
using namespace std;
const int MAX = 666*300*4+5;//为了满足范围,满足范围即可,不一定非要这个
const int mod=1e8+7;
int dp[2][MAX];
int a[301];
int n;
int main(){
    cin >> n;
    for (int i = 0; i < n;i++) cin >> a[i];
    dp[1][0+MAX/2]=1;
    for (int i = 0; i < n;i++){
        for (int j = -MAX/4; j < MAX/4;j++){
            if(j==666) continue;
            dp[i&1][j+MAX/2]=(dp[i&1][j+MAX/2]+dp[!(i&1)][-j+MAX/2]+dp[!(i&1)][j-a[i]+MAX/2])%mod;//最大值除以二是为了满足范围,满足范围即可,不一定非要最大值除以二
        }
        memset(dp[!(i&1)],0,sizeof(dp[!(i&1)]));
    }
    cout << dp[(n-1)&1][-666+MAX/2] << endl;
    return 0;
}