链接:https://ac.nowcoder.com/acm/contest/373/B
来源:牛客网
题目描述
在欧美,“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是前七个素数的平方和 22+32+52+72+112+132+172=666 22+32+52+72+112+132+172=666
2、 (6+6+6)+(63+63+63)=666 (6+6+6)+(63+63+63)=666。
3、 (6+6+6)+2×(6+6+6)2=666 (6+6+6)+2×(6+6+6)2=666。
4、 13+23+33+43+53+63+53+43+33+23+13=666 13+23+33+43+53+63+53+43+33+23+13=666。
---废话到此为止
lililalala正在玩一种有 N N个回合的回合制RPG游戏,初始分数为0,第 i i个回合lililalala有如下两种选择。
A.将分数加上 ai ai
B.将分数 ×-1 ×-1
lililalala同样也很讨厌野兽数 666 666,但是他很却喜欢数字 -666 -666。他想知道有多少种不同的方案使得 N N个回合后分数变为 -666 -666且在任何一个回合之后分数都不为 666 666。
如果两种方案有任何一个回合选择不同,就认为这两种方案是不同的。
答案请对 108+7 108+7取模。
输入描述:
输入包含两行。
第一行一个整数 N(1≤N≤300) N(1≤N≤300)。
第二行 N N个整数 a1a2a3...an(-666≤ a1a2a3...an≤666) a1a2a3...an(-666≤ a1a2a3...an≤666)。
输出描述:
输出一行一个整数--符合条件的不同方案数。
示例1
输入
3 -333 -333 -333
输出
1
说明
仅一种符合条件的方案
第一回合选择将分数 ×−1 ×−1。分数为 0 0
第二回合选择将分数加上 -333 -333。分数为 -333 -333
第三回合选择将分数加上 -333 -333。分数为 -666 -666
示例2
输入
3 333 333 333
输出
0
示例3
输入
13 518 -643 -503 424 -76 -18 547 26 51 -647 -457 -5 329
输出
2
作者:lililalala
链接:https://ac.nowcoder.com/discuss/157310
来源:牛客网
简单的计数dp.
dp[i][j]代表第i个回合后分数为j的方案数
则:dp[i][j]=dp[i-1][j-ai]+dp[i-1][-j]
因为开二维内存不够,需要使用滚动数组
特判屏蔽所有来自j=666的状态转移
复杂度O(n*n*1333)
牛客参考代码:
#include<bits/stdc++.h>
using namespace std;
const int mod=100000007;
long long a[421000],b[421000];
void solve(){
int n;
scanf("%d",&n);
memset(a,0,sizeof(a));
a[210000]=1;
for(int i=0;i<n;i++){
int p;
scanf("%d",&p);
memset(b,0,sizeof(b));
for(int i=0;i<420000;i++){
int f=i-210000;
if(f==666) continue;
b[-f+210000]=(a[i]+b[-f+210000])%mod;
b[f+210000+p]=(a[i]+b[f+210000+p])%mod;
}
memcpy(a,b,sizeof(b));
memset(b,0,sizeof(b));
}
printf("%d\n",a[210000-666]);
}
int main(){
solve();
return 0;
}
笔者参考代码:
#include<bits/stdc++.h>
using namespace std;
const int mod=1e8+7;
const int N=301,M=1e5,T=2e5;
int a[N],dp[T<<1][2];
int n;
int main(){
scanf("%d",&n);
int tot=0;
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
tot+=abs(a[i]);
}
dp[-666+T][0]=1;
for(int i=n;i;--i){
dp[666+T][0]=0;
for(int j=-tot;j<=tot;++j){
if(j==666){
continue;
}
dp[j+T][1]+=((dp[j+a[i]+T][0]+dp[-j+T][0])%mod);
dp[j+T][1]%=mod;
}
for(int j=-tot;j<=tot;++j){
dp[j+T][0]=dp[j+T][1];
dp[j+T][1]=0;
}
}
printf("%d",dp[T][0]);
return 0;
}
学长参考代码:
#include<bits/stdc++.h>
using namespace std;
int dp[2][304*666*2+20];
int main()
{
int n, index = 302*666+5, a, mod = 1e8+7, cur = 0;
scanf("%d",&n);
dp[cur][index] = 1;
for(int i = 1; i <= n; ++i)
{
scanf("%d",&a);
cur ^= 1;
dp[cur^1][index+666] = 0;
for(int j = -300*666; j <= 300*666; ++j) dp[cur][index+j] = (dp[cur^1][index-j]+dp[cur^1][index+j-a])%mod;
}
printf("%d\n",dp[cur][index-666]);
return 0;
}