比赛时间 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;
}
01-17 00:11