题意

给定 $n$，求 $\sum_{l=0}^n\sum_{r=l}^n f(C_r^l)$ 的值。其中 $f(x) = (x+1) \bmod 3 - 1$。

$1 \le n \le 2\times10^{16}$

分析

首先转化 $f$ 函数。

$$f(x)=\begin{cases}0,x \bmod 3 = 0 \\1,x \bmod 3 = 1 \\-1,x \bmod 3 = 2 \end{cases}$$

首先，如果 $C_r^l \bmod 3 = 0$，一定是没有意义的。这就是说，在 $3$ 进制意义下，所选的 $l,r$ 一定是每一位都满足 $r_i \ge l_i$。

所以求的就是。

$$\sum_{i=0}^n \sum_{j=0}^i [C_i^j = 1] - [C_i^j = 2]$$

这个式子不好算了，考虑设 $g(x) = \sum_{i=0}^x [C_x^i = 1] - [C_x^i = 2]$，答案就是 $\sum_{i=0}^n g(i)$。

我们对 $g$ 打一下表，发现都是 $2$ 的次幂。把次幂拿下来，就会发现，$g(x)$ 的指数就是 $x$ 在三进制下的 $1$ 的个数。

当我的表打到 $1000$ 的时候，我基本确定了这个猜想。但是我不会证，看了题解，似乎要二项式反演。所以不证了。

考虑我们已知 $g(x)$ 就是 $2^y$，其中 $y$ 就是 $x$ 在三进制下的 $1$ 的个数。考虑计算，用数位 $\text{dp}$ 求有 $i$ 个 $1$ 的方案数，这个是简单的。最终时间复杂度是 $O(\log_3^2n)$。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define il inline
#define int ll
il ll rd(){
    ll s = 0, w = 1;
    char ch = getchar();
    for (;ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') w = -1;
    for (;ch >= '0' && ch <= '9'; ch = getchar()) s = ((s << 1) + (s << 3) + ch - '0');
    return s * w;
}
const int P = 1732073999;
ll n;
int a[45], L, ans, f[45][45][2], p2[45];
int dfs(int i, int j, bool lim){
    if (!i) return (!j);
    if (~f[i][j][lim]) return f[i][j][lim];
    int maxn = (lim ? a[i] : 2), res = 0;
    for (int t = 0; t <= maxn; t++) res = (res + (j - (t == 1) < 0 ? 0 : dfs(i - 1, j - (t == 1), lim && (t == maxn)))) % P;
    return f[i][j][lim] = res;
}
int Main(){
    n = rd(), L = ans = 0;
    for (; n; n /= 3) a[++L] = n % 3;
    for (int i = 0; i <= L + 1; i++) for (int j = 0; j <= L + 1; j++) f[i][j][0] = f[i][j][1] = -1;
    for (int i = 0; i <= L; i++) ans = (ans + 1ll * dfs(L, i, 1) * p2[i] % P) % P;
    printf ("%lld\n", ans);
    return 0;
}
signed main(){
    p2[0] = 1;
    for (int i = 1; i <= 40; i++) p2[i] = 1ll * p2[i - 1] * 2 % P;
    for (int T = rd(), M = rd(); T--;) Main();
    return 0;
}