牛客练习赛 41 B- 666RGB

在欧美，“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 \times (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$ 个回合的回合制RPG游戏,初始分数为0,第 $\ i$ 个回合lililalala有如下两种选择。

A.将分数加上 $\ a_{i}$
B.将分数 $\ \times \text -1$

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

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

答案请对 $\ 10^{8}+7$ 取模。

3
-333 -333 -333

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

仅一种符合条件的方案

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

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

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

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

dp[i][j]

代表1--i 结果为cd+j的数目

滚动优化

%%%clf

/*
总共有300个数，每个数-666<=x<=666
300个数的数据范围就是-666*300---666*300
负数我把它弄到0--cd范围
正数cd---maxn范围
dp[i][j]代表着  1---i  经过运算之后，结果为j的数量
*/
    long long dp[305][444444];
    memset(dp,0,sizeof(dp));
    dp[0][cd]=1;//最初的那一个  0  也就是cd
    for(int i=1; i<=n; i++)
    {
        for(int j=2000; j<420000; j++)
        {
            if(j==cd+666)
                dp[i][j]=0;//不能出现666
            else
            {
                dp[i][j]+=dp[i-1][j-a[i]];//加上a[i]
                //j-a[i]加上a[i]就是j
                dp[i][j]+=dp[i-1][2*cd-j];//乘以-1
                //cd相当于0   2*cd-j就是原来的数乘以-1
                dp[i][j]%=mod;
            }
        }
    }
    //long long dp[305][444444];太大了
    //我们发现有了dp[i]之后之前的就没有用了，所以滚动数组优化
    //变成dp[2][444444]

#include<bits/stdc++.h>
using namespace std;
const long long mod=1e8+7;
long long dp[2][444444];
int cd=220000;
long long a[305];
int n;
int main()
{
    scanf("%d",&n);
    //n=300;
    for(int i=1; i<=n; i++)
    {
        scanf("%lld",&a[i]);
       //a[i]=i;
    }
    memset(dp,0,sizeof(dp));
    dp[0][cd]=1;
    for(int i=1; i<=n; i++)
    {
        int cnt;
        cnt=i%2;
        memset(dp[cnt],0,sizeof(dp[cnt]));
        for(int j=2000; j<420000; j++)
        {
            if(j==cd+666)
                dp[cnt][j]=0;
            else
            {
                dp[cnt][j]+=dp[cnt^1][j-a[i]];
                dp[cnt][j]+=dp[cnt^1][2*cd-j];
                dp[cnt][j]%=mod;
            }
        }
    }
    cout<<dp[n%2][cd-666];
 
}