题目传送门
题目大意：
设函数 \(F(x) := (x + 1) \bmod 3 − 1\)，\(T\) 次询问，计算：
\[\sum\limits_{i = 0}^{n}\sum\limits_{j}F\left({i\choose j}\right) \]思路：
看到奇奇怪怪的组合数求和首先考虑 \(\text{Lucas}\)，将原数在 \(3\) 进制下拆位，得：
\[{i\choose j} = \prod\limits_{k = 1}^{m}{i_k\choose j_k}\bmod 3 \]其中 \(m\) 表示 \(i\) 和三进制下较长的那个数的数字位数。
接着注意到 \(F\) 函数是一个积性函数（这个可以分九类讨论证明），即 \(F(xy) = F(x)F(y)\)，所以实际上 \(F\left({i\choose j}\right)\) 要计算的就是所有 \(F\left({i_k\choose j_k}\right)\) 的乘积。
对于每一个 \(i\)，\(j\) 的每一位就独立了，这时候再分类讨论：
- 当 \(i_k = 0\) 时，\(j_k\) 取 \(0\) 的时候有贡献，此时这一位的值为 \(F(1) = 1\)；
- 当 \(i_k = 1\) 时，\(j_k\) 取 \(0,1\) 的时候有贡献，此时这一位的值为 \(F(1) + F(1) = 2\)；
- 当 \(i_k = 2\) 时，\(j_k\) 取 \(0,1,2\) 的时候有贡献，此时这一位的值为 \(F(1) + F(2) + F(1) = 1\)。
而乘 \(1\) 是不会是答案增加的，所以只用考虑乘 \(2\) 的个数就行了，即：
\[\sum\limits_{j}F\left(i\choose j\right) = \left(\prod\limits_{i_k = 0}1\right)\left(\prod\limits_{i_k = 1}2\right)\left(\prod\limits_{i_k = 2}1\right) = 2^{\#\{i_k = 1\}} \]然后就会发现统计一下三进制表示下 \(1\) 的个数就行了，数位 dp 即可。
\(\texttt{Code:}\)
#include <cmath>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 65, mod = 1732073999;
int T;
ll vmax, n;
vector<int> num;
ll f[N][N];
ll qpow(int a, int b) {
ll ans = 1, base = a;
while(b) {
if(b & 1) ans = ans * base % mod;
base = base * base % mod;
b >>= 1;
}
return ans;
}
ll dfs(int pos, int cnt, bool limit, bool zero) {
if(pos < 0) return qpow(2, cnt);
if(!limit && !zero && ~f[pos][cnt]) return f[pos][cnt];
int mx = (limit ? num[pos] : 2);
ll res = 0;
for(int i = 0; i <= mx; i++)
res = (res + dfs(pos - 1, cnt + (i == 1), limit && (i == num[pos]), zero && (!i))) % mod;
if(!limit && !zero) f[pos][cnt] = res;
return res;
}
ll calc(ll x) {
num.clear();
ll tmp = x;
while(tmp) {
num.push_back(tmp % 3);
tmp /= 3;
}
return dfs(num.size() - 1, 0, 1, 1);
}
int main() {
scanf("%d%lld", &T, &vmax);
memset(f, -1, sizeof f);
while(T--) {
scanf("%lld", &n);
printf("%lld\n", calc(n));
}
return 0;
}