Round B No Nine

本文主要是介绍Round B No Nine，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <iostream>
//#include <string>
using namespace std;int T;
typedef long long LL;
LL f[20][12];
LL g[20];void init() {//f[i][j] i位和为j的所有可能f[0][0] = 1;for (int i = 0; i + 1 <= 18; ++i) {for (int j = 0; j <= 9; ++j) {for (int k = 0; k < 9; ++k) {f[i + 1][(j + k) % 9] += f[i][j];}}}for (int i = 0; i <= 18; ++i) {for (int j = 0; j <= 9; ++j) {g[i] += f[i][j];}}
}LL work(LL R) {if (R == 0) return 0;vector<int> nums;LL X = R;while(X) {nums.push_back(X % 10);X /= 10;}LL res = 0;int prev = 0;bool ok = true;for (int i = nums.size() - 1;i >= 0; i --) {int u = nums[i];for (int j = 0; j < u; ++j) {res += g[i] - f[i][(9 - (prev + j) % 9) % 9];}prev += u;prev %= 9;if (u == 9) {ok = false;break;}// prev %= 9}if (ok && prev % 9 != 0) {res ++;}return res;
}int main() {cin >> T;int Case = 1;init();while (T --) {LL F, L;cin >> F >> L;printf("Case #%d: %lld\n", Case, work(L) - work(F - 1));Case ++;}
}

这篇关于Round B No Nine的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---