addimnorsux II 题解

mahaorui2012 · 2026-06-18 21:43:44 · 题解

本文使用 AI 进行了润色。

对 x, a_i 的每一位，若它们在第 k 位（权值为 2^k）中至少有一个为 0，则对运算 (x+a_i)-(x\oplus a_i) 的结果贡献为 0，否则贡献为 2^{k+1}。因此恒有：

(x+a_i)-(x\oplus a_i) = (x \ \& \ a_i) \ll 1

其中 \& 为按位与，\ll 为左移。

左移运算对按位与运算满足分配律，所以：

f(a) = (a_1 \ll n) \ \& \ (a_2 \ll (n-1)) \ \& \ \dots \ \& \ (a_n \ll 1)

每一位是独立的，因此可以拆位计算。对每一位权值 2^k，计算有多少种序列 a 使得 f(a) 的第 k 位为 1。

设 c = k - n - 1。f(a) 的第 k 位为 1，等价于对所有元素 a_i，其在第 c+i 位（即权值为 2^{c+i}）必为 1，其他位没有限制。我们先把总和 S 减去必选的部分 \sum_{i=1}^n 2^{c+i} = 2^{c+1}(2^n-1) 得到 S'，则条件变为：所有元素 a_i 的第 c+i 位必须为 0，且总和为 S'。

注意，如果 f(a) \neq 0，则必定有 \sum_{i=1}^n 2^{i-1} \leq S，即 2^n-1 \leq S，也就是 n \leq \log_2 (S+1)。故有意义的 n 只有 \mathcal{O}(\log S) 量级。

考虑生成函数。设第 i 个元素可选的非负整数集合为 P_i，令 F_i(x) = \sum_{j=0}^{\infty} [j \in P_i]x^j，G(x) = \prod_{i=1}^n F_i(x)，则当前位的方案数即为 [x^{S'}]G(x)。

站在二进制拆分的视角，没有限制时自然数的生成函数为 \frac{1}{1-x} = \sum_{j=0}^{\infty} x^j = \prod_{j=0}^{\infty} (1+x^{2^j})。因为第 c+i 位不能选，对应的生成函数即：

F_i(x) = \prod_{j \neq c+i} (1+x^{2^j}) = \frac{\prod_{j=0}^{\infty} (1+x^{2^j})}{1+x^{2^{c+i}}} = \frac{1}{(1-x)(1+x^{2^{c+i}})}

所以：

G(x) = \prod_{i=1}^n F_i(x) = \frac{1}{(1-x)^n} \prod_{i=1}^n \frac{1}{1+x^{2^{c+i}}}

考虑利用平方差公式变形化简连乘式：\frac{1}{1+x^{2^j}} = \frac{1-x^{2^j}}{1-x^{2^{j+1}}}。将其代入得：

\prod_{i=1}^n \frac{1}{1+x^{2^{c+i}}} = \prod_{i=1}^n \frac{1-x^{2^{c+i}}}{1-x^{2^{c+i+1}}} = \frac{1-x^{2^{c+1}}}{1-x^{2^{c+n+1}}}

代回 G(x)，并利用负二项式展开：

G(x) = (1-x^{2^{c+1}}) \frac{1}{(1-x)^n} \frac{1}{1-x^{2^{c+n+1}}} = (1-x^{2^{c+1}}) \left( \sum_{i=0}^{\infty} \binom{n-1+i}{n-1} x^i \right) \left( \sum_{i=0}^{\infty} x^{i \cdot 2^{c+n+1}} \right)

令 d = c+1。先把前面的 (1-x^{2^d}) 提取出来。令：

H(x) = \left( \sum_{i=0}^{\infty} \binom{n-1+i}{n-1} x^i \right) \left( \sum_{i=0}^{\infty} x^{i \cdot 2^{d+n}} \right)

则 [x^{S'}]G(x) = [x^{S'}]H(x) - [x^{S'-2^d}]H(x)，这两项可以分别计算。暴力卷积求系数即为：

[x^T]H(x) = \sum_{i=0}^{\lfloor \frac{T}{2^{d+n}} \rfloor} \binom{n-1+T-i \cdot 2^{d+n}}{n-1}

不知道这个东西有什么很好的组合意义。

考虑如何快速计算 [x^T]H(x)。显然 \binom{B}{n-1} 是一个关于 B 的 n-1 次多项式。而根据离散微积分性质，n-1 次多项式的前缀和必定是一个 n 次多项式，因此 \sum_{i=0}^M \binom{n-1+T-i \cdot 2^{d+n}}{n-1} 是一个关于 M 的 n 次多项式，可以通过拉格朗日插值得出。

具体地，对 i=0, 1, \dots, n：通过 Lucas 定理算出 \binom{n-1+T-i \cdot 2^{d+n}}{n-1} \pmod{MOD}，然后对其求前缀和，取这 n+1 个点做线性拉格朗日插值即可得到 M = \lfloor \frac{T}{2^{d+n}} \rfloor 时的多项式值。

预处理组合数数组的复杂度为 \mathcal{O}(MOD \log S)（也可以做到 O(MOD)），单次插值复杂度为 \mathcal{O}(n)，每次查询需枚举位数，总时间复杂度为 \mathcal{O}(MOD \log S + Q \log^2 S)。注意避免运算时的溢出，并特判算组合数时的极端情况。

::::success[std]

#include <iostream>
#include <vector>
#define int long long
#define MOD 599999
using namespace std;

const int LOGS=63;

int c[MOD][LOGS]; 
int inv[LOGS];
int C[LOGS],f[LOGS];

int work(int n,int T,int d){
    for(int i=0;i<=n;++i){
        C[i]=1;
        int A=n-1+T-1ll*i*(1ll<<(d+n));
        if(A<n-1) C[i]=0; 
        else{
            C[i]=c[A%MOD][n-1];
        }f[i]=(C[i]+(i?f[i-1]:0))%MOD;
    }
    int val=T/(1ll<<(d+n))%MOD;
    vector<int> pre(n+2,1),suf(n+2,1),ifac(n+1,1);
    for(int i=1;i<=n;++i) ifac[i]=1ll*ifac[i-1]*inv[i]%MOD;
    for(int i=0;i<=n;++i) pre[i+1]=1ll*pre[i]*(val-i+MOD)%MOD;
    for(int i=n;i>=0;--i) suf[i]=1ll*suf[i+1]*(val-i+MOD)%MOD;

    int ret=0;
    for(int i=0;i<=n;++i){
        int cans=1ll*f[i]*pre[i]%MOD*suf[i+1]%MOD*ifac[i]%MOD*ifac[n-i]%MOD;
        if((n-i)&1) cans=1ll*cans*(MOD-1)%MOD;
        (ret+=cans)%=MOD;
    }return ret;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    inv[1]=1;
    for(int i=2;i<LOGS;++i){
        inv[i]=1ll*(MOD-MOD/i)*inv[MOD%i]%MOD;
    }
    c[0][0]=1;
    for(int i=1;i<MOD;++i){
        c[i][0]=1;
        for(int j=1;j<LOGS;++j){
            c[i][j]=(c[i-1][j]+c[i-1][j-1])%MOD;
        }
    }

    int q;
    cin>>q;
    while(q--){
        int n,S;
        cin>>n>>S;
        if(n>=60 || S<(1ll<<n)-1){
            cout<<"0\n"; 
            continue;
        }
        int ans=0;
        S-=(1ll<<n)-1;
        for(int d=0;S>=0;S-=(1ll<<d)*((1ll<<n)-1),++d){
            int k=d+n;
            int w=(1ll<<k)%MOD;
            int cans=(work(n,S,d)-work(n,S-(1ll<<d),d)+MOD)%MOD;
            (ans+=1ll*cans*w%MOD)%=MOD;
        }cout<<ans<<'\n';
    }
    return 0;
}