比赛时间 2019.10.19 8:00 - 2019.10.20 8:00
比赛网站 https://csacademy.com/ieeextreme13
// 连续24小时做题真的是极限体验
// 刚比完躺了醒来就会做压轴题了，吐血 = =
Alfa Pool
题目大意
有一种比赛的计分规则为：相邻得分下一次将加倍，两次连续不得分则终止比赛，每次从1开始得分。计算有多少种方式使总分为B， B = 5 的全部情况如下表。询问包含 N 组，每次求总分为 \(B_i\) 的方案数对 1e9+7 取模的结果。
数据范围
- \(1≤N≤10^4\)
- \(0 \leq B_i≤10^5\)
解题思路
分别尝试直接爆搜，分块爆搜（每一块得分为 \(2^k -1\)） 都 TLE ，只通过了一组测试。
由于答案没有递推性质，打表找不出规律，队友通过OEIS大法找到了该问题的数列，但求法太复杂，遂放弃。
注意到 B 不超过 1e5，最大的一部分得分为 \(2^16 - 1=65535\)，那么全部能选的分数只有 16 种可能。
考虑设 dp[n][k] ： 总得分为 n 最后一部分得分为 \(2^k-1\) 的方案数（1<=k<=16)，那么就可以写出状态转移方程了。
const int p[17] = {0,1,3,7,15,31,63,127,255,511,1023,2047,4095,8191,16383,32767,65535};
// Ans[n][0] : 总得分为 n 的全部方案数
Ans[i][0] += Ans[i][j] (1<=j<=16)
Ans[i+p[j]][j] += Ans[i][0] (1<=j<=16)
// 答案即为 2*Ans[B][0]
AC代码
#include<iostream>
#include<cstdio>
using namespace std;
const int mod = 1e9+7;
const int p[17] = {0,1,3,7,15,31,63,127,255,511,1023,2047,4095,8191,16383,32767,65535};
int Ans[100010][17];
// Ans[n][0] : ans[n]
void init() {
Ans[0][0] = 1;
for(int i=0;i<=100000;i++) {
for(int j=1;j<=16;j++) {
Ans[i][0] = (Ans[i][0] + Ans[i][j]) % mod;
}
for(int j=1;j<=16;j++) {
if(i+p[j]<=100000)
Ans[i+p[j]][j] = (Ans[i+p[j]][j] + Ans[i][0]) % mod;
}
}
}
int main() {
init();
int n; cin>>n;
while(n--) {
int B;
scanf("%d", &B);
if(B==0) printf("1\n");
else
printf("%d\n", 2*Ans[B][0]%mod);
}
return 0;
}