其他
手上握有多少幸运票？
幸运票被定为前半部分数字总和等于后半部分，比如数字117234和4493278
1 + 1 + 7 = 2 + 3 + 4 = 9
4 + 4 + 9 = 2 + 7 + 8 = 17 (3 is ignored)
如果个数是奇数的，中间的数字被忽略。
数字不一定是10进制的，可以是各种各样的B进制，题目给定数字的位数N和进制B，求解所有的幸运票，比如N是6，而B是10，那么要求出区间[000000, 999999]所有幸运票的数目。
实例如下：
input data:
4
1 5
4 3
5 2
6 10
answer:
5 19 12 55252
像最后一个，答案已经超过5万个，显然遍历是很耗时的，特别当我们需要求解很多个不同的NB组合时。
unsigned long long int count_lucky(int N, int B);
int plus1_sum(int* digits, int N, int B, int sum);
int main() {
std::ifstream infile("data/id109.txt");
std::string line;
getline(infile, line);
std::stringstream ss(line);
int n;
ss >> n;
int N, B;
for (int i=0; i<n; i++) {
getline(infile, line);
std::stringstream NB(line);
NB >> N;
NB >> B;
std::cout << count_lucky(N, B) << " ";
}
std::cout << std::endl;
}
主程序很简单，读了N和B，用count_lucky求解，并打印结果。
这个问题的重点在于，要求前后两部分，我们知道，其实取值的各种组合是一样的，所以只要求解前半部分就可以了。
所以呢，我定义了：
int plus1_sum(int* digits, int N, int B, int sum) {
digits[N-1]++;
sum++;
for (int i=N-1; i>0; i--) {
if (digits[i] >= B) {
digits[i] -= B;
digits[i-1]++;
sum = sum - B + 1;
} else {
break;
}
}
return sum;
}
这里digits是长度为N的向量，而这里的N是要求解的NB的N/2，也就是我们只看前半部分，函数很简单，通过每次加1来遍历所有数字，每一次都记录数字的总和sum。
然后count_luck可以登场了：
unsigned long long int count_lucky(int N, int B) {
int n = N/2;
if (n == 0)
n = 1;
int* digits = new int[n];
int size = 1;
for (int i=0; i<n; i++) {
digits[i] = 0;
size *= B;
}
int max = n*(B-1) +1 ;
int* sum_cnt = new int[max];
for (int i=1; i<max; i++) {
sum_cnt[i] = 0;
}
sum_cnt[0] = 1;
int i=0;
int sum = 0;
while(++i < size) {
sum = plus1_sum(digits, n, B, sum);
sum_cnt[sum]++;
}
unsigned long long int cnt = 0;
for (i=0; i<max; i++) {
cnt += sum_cnt[i] * sum_cnt[i];
}
if (N % 2 == 1 && N > 1)
cnt *= B;
return cnt;
}
遍历了前半部分，记录下了所有数字加和的个数，比如说前半部分有和为X的组合Y个，那么后半部分也会有和为X的组合Y个，所以前半部分和为X以及后半部分和也为X的组合就应该是Y^2，所以呢cnt += sum_cnt[i] * sum_cnt[i];就算出来总数。但这里还有一个问题，如果是数字位数是奇数，那么中间可以是0:(B-1)的任意数，所以还需要cnt*B.
这里我们只遍历了前半部分，次数是B^(N/2)，试想一下，如果遍历所有，次数是B^N次方，B^N/B^(N/2) = exp(N/2 * log(B))，这时间差距可是指数增长。
往期精彩