愤怒的小 N（angry）- CCF NOI Online 能力测试 提高组 2021第一题

【题目描述】
极度愤怒的小 N 通关了一款游戏来泄愤。
这款游戏共有 n 关，分别为第 0 关、第 1 关、第 2 关、···、第 n−1 关。这些关卡中有一些是普通关卡，另一些则是奖励关卡。 这款游戏中普通关卡与奖励关卡的分布比较特殊。如果用字符 a 表示普通关卡，用 字符 b 表示奖励关卡，那么第 0 关、第 1 关、第 2 关、···、第 n−1 关依次排列形成 的字符串是一个无穷字符串 s 的前缀，且 s 可以按照如下方式构造：

  1. 初始时 s 为包含单个字符 a 的字符串。
  2. 将 s 的每个字符 a 替换成字符 b，每个字符 b 替换成字符 a 得到字符串 t，然后 将 t 拼接到 s 后。
  3. 不断执行 2. 得到的字符串就是最终的 s。

可以发现 s = abbabaabbaababba···，所以这款游戏的第 0 关是普通关卡，第 1 关 是奖励关卡，第 2 关是奖励关卡，第 3 关是普通关卡，以此类推。 通过游戏的第 i 关可以得到 f(i) 分，其中 f(x) = a0 + a1x + a2x2 +···+ ak−1xk−1 是一个固定的 k−1 次多项式。 小 N 通关时一气之下通过了所有奖励关卡而忽略了所有普通关卡，然后就把游戏 卸载了。现在回想起来，他想要知道他在卸载游戏前的总得分对 10⁹ + 7 取模后的结果。
【输入格式】 从文件 angry.in 中读入数据。 第一行一个正整数 n，表示游戏的关卡数目。为方便，n 以二进制表示给出。 第二行一个正整数 k，表示多项式的次数加一。 第三行 k 个非负整数，分别为 a0,a1,a2,…,ak−1，表示多项式的各项系数。
【输出格式】 输出到文件 angry.out 中。 一行一个非负整数，表示小 N 卸载游戏前的总得分对 109 + 7 取模后的结果。
【样例 1 输入】
1 1000 2 3 3 3 2 1
【样例 1 输出】
1 110
【样例 1 解释】
这款游戏共有 8 关，通关第 i 关可以得到 (3 + 2i + i2) 分。第 1,2,4,7 关为奖励关， 小 N 通过这几关分别得到了 6,11,27,66 分，共 110 分。
【样例 2 输入】

1
2
3
11111100101 
4
2 0 2 1

【样例 2 输出】

1
143901603

【样例 3 输入】

1
2
3
1001011001101001 
16
1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1

【样例 3 输出】

1
184740992

【数据范围与提示】 对于所有测试点：0 ≤log₂n < 5×10⁵，1 ≤ k ≤ 500，0 ≤ ai < 10⁹ + 7，a的第k-1项≠ 0。

我的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <iostream>
#include <string.h>
using namespace std;
#define RLL register long long
#define LL long long
#define VALUE 1000000007

int n;
int x[512],k;
int getn(LL num){
	return (num)?1+getn(num/10):0;
}

int BtoD(LL num){
	int dec=0,i=0;
	while(num){
		dec+=(num%10)*(1<<i++);
		num/=10;
	}
	return dec;
}

//这一一般的求幂（的模）
LL normalExponentiation(int base,int power){
    LL res=1;
    for(int i=1;i<=power;i++){
        res*=base;
        res%=VALUE;
    }
    return res%VALUE;
}
//老快了
LL fastExponentiation(LL base,LL power) {
    LL res = 1;
    while (power > 0) {
        if (power & 1) {//此处等价于if(power%2==1)
            res = res * base % VALUE;
        }
        power >>= 1;//此处等价于power=power/2
        base = (base * base) % VALUE;
    }
    return res;
}

LL getScore(int i){
	//第i个关卡
	LL res=0,power;
	for(int l=0;l<k;l++){
		power=x[l];
		if(x[l])
			res+=fastExponentiation(i,l);//比normalExponentiation快了好多好多好多好多 
	}
	return res;
}

string mades(string s){
	string news=s;
	for(int i=0;i<n;i++){
		for(int j=0;j<s.size();j++)
			news+=(s[j]=='a')?"b":"a";
		s=news;
	}
	return news;
}

int main() {
	LL num;
	cin>>num>>k;
	n=getn(num);
	for(int i=0;i<k;i++)cin>>x[i];
	string s=mades("a");
	RLL ScoreSum=0;
	int max=BtoD(num);
	for(int i=0;i<max;i++)
		if(s[i]=='b'){
			ScoreSum+=getScore(i);
		}
	cout<<"SUM:"<<ScoreSum%VALUE;
	return 0;
}

这里的fastExponentiation其实有更好的方法，但是没从本子那边拿到（我自己也想不出来😥）