[C++] Lucky Tickets

幸运票被定为前半部分数字总和等于后半部分，比如数字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组合时。

#include <iostream>
#include <fstream>
#include <sstream>
#include <string>


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))，这时间差距可是指数增长。

https://v.qq.com/txp/iframe/player.html?vid=f13114lvr7z&width=500&height=375&auto=0
程序员的日常生活就是各种试错，这视频让无数人躺枪有没有！👻