code / 坠机：P17111 「FAOI-R13」addimnorsux II

· · 题解

Warning：本篇题解没有代码实现，正确性存疑，请谨慎参考。推导思路与已有的公开题解均（事实上截止目前只有一篇）不相同，故先行发表。仅使用 AI 以及参照官方题解进行了正确性的核验。

如果有问题就叫我撤下来。

:::info[什么样的人生是失败的？（第十四弹）]

背景：all in T3 推式子。

开头：秒了 AB，剩下 3h 多，看了眼 D 打了个暴力发现怎么过不去 subtask 2 懒得思考了，钦定 t4 是困难题，发现榜上过了 5 个 C 于是决定 all in 推式子。

中间：推了三版式子假了两版，剩 30min 得到正确式子花了 10min 发现不会算，剩 15min 的时候发现好像这个式子可以转变成一个项数很少的 poly。

高潮：我不会拉插。

结尾：

结尾呢？不知道。或许这个折叠框是个墓碑吧。

R.I.P. :::

100 + 100 + 33 + 12 遗憾离场。

为什么会变成这样子呢？我问我自己。

详细揭秘组合意义天地灭。

首先 n 个东西的和是定值 S 有经典组合意义，拆解成 n-1 个板和 S 个球的插板方案数。

然后和减异或部分有经典位运算等式 2(a\otimes b)+(a\oplus b)=a+b，其中 \otimes 表示与，\oplus 表示异或。

所以问题就变成了一边左移一边与，交替进行，第一个是左移，最后一个也是左移，求所有划分球后得到的操作序列的结果。

最后一个左移先不看，容易发现这个东西每一步左移在前与在后，那么提前把左移的位给移好显然没有问题。

所以我们把这个玩意的对齐规则搞成一个平行四边形状物，前面高后面低，同样高的位置齐平。

因为数字二进制下长度顶天 \log S 位，所以有解情况下 n 不可能超过数字长度，故我们可以降数据范围到 n<60。

此时的与就是要求这个平行四边形上的一个横线上全部都是 \texttt1，考虑重新对齐把原先飞上去的列给还原回来，那么对齐的线就变成了斜向右上四十五度的线。

考虑构造一个双射，我们把这个线的部分往左边压平，压在开头数字上，然后要求第一个数字的一段连续位置一定得是 \texttt1，显然这里的方案可以和原始局面构成双射。

那么，我们直接对着这个东西做双指针，动态维护被强制要求的位置，把需要的球的数量从总量里扣去。

如果第一个数字禁止放球了那么是容易的，直接在其他数字里面做插板即可，但问题就出在这里。

因为我们只是强制要求了第一个数字上的一段是 \texttt 1，没有要求其他地方是 \texttt 0，所以这个东西是非常坏的，也就是说我们有可能在高位另外开一片地放球，低位也可以。

低位的部分本质上是多了一个带上限的盒子，可以转单步容斥，用不带上界减去带下界的情况。带下界的话直接预先填充即可。

高位部分怎么处理？首先有可能不放球，那么我们不要这个盒子就是一个合法解。

否则至少会放 k 个球，这里的 k 是高位部分的 \text{lowbit}，那么当场带下界的预先塞一下就好了……？

错的，你不能够侵蚀低位的地方。

所以高位限制的本质是放的球必须得是 k 的倍数。

不管上面的了，我们现在只需要解决，有 n+1 个盒子，m 个球，第一个盒子的球的数量必须是 k 的倍数，总共的划分方案数。

列出式子：

\sum_{i=0}^{\left\lfloor\frac{m}k\right\rfloor}\binom{n-1+m-ik}{n-1}

显然，直接算算不了。

但是根据定义我们知道，组合数 \binom{a}{b} 本质上是一个关于 a 的 b 次多项式，这里套了个求和所以变成关于枚举上界的多项式，而且会多一次。

那么也就是说次数是 O(n) 级别的，n<60 根据见过的 poly 算法可以想到拉插。然后，没了。

某个同学想到这里的时候，发现距离比赛结束还剩十五分钟。

组合数部分要用 lucas 定理优化，这个是简单的，略去不提。因为下指标非常小所以这部分可以看做 O(1) 的。

时间复杂度应该是 O(P+Tn^2)，其中 n<60，瓶颈在于双指针的同时内部反复拉插。

代码等我学了拉插来补。这里有一个完全按照这个式子写出来的 33 分暴力，没有 WA 所以式子应该没有问题。

:::info[暴力代码]

#include<bits/stdc++.h>
#define int long long
#define mod 599999
#define lowbit(x) (x&-x)
using namespace std;
int A[600005];
int inv[600005];
int qpow(int a,int b=mod-2){
    int ans=1;
    if(b==0)return 1;
    while(b){
        if(b&1)ans*=a,ans%=mod;
        a*=a,b>>=1,a%=mod;
    }
    return ans;
}
int C(int n,int m){
    if(m>n)return 0;
    return (A[n]*inv[m]%mod*inv[n-m]%mod);
}
void init_of_C(int N){
    A[0]=A[1]=1;
    for(int i=2;i<=N;i++)
    A[i]=A[i-1]*i%mod;
    inv[N]=qpow(A[N]);
    for(int i=N;i;i--)
    inv[i-1]=inv[i]*i%mod;
}
int lucas(int n,int m){
    if(n<m)return 0;
    if(n==0)return 1;
    return lucas(n/mod,m/mod)*C(n%mod,m%mod)%mod;
}
void solve(){
    int n,s;
    cin>>n>>s;
    if(n>59){
        cout<<"0\n";
        return;
    }
    if(n==1){
        cout<<s*2<<'\n';
        return;
    }
    int x=0;
    int flc=1;
    for(int i=0;i<n;i++,flc<<=1)
    x|=flc;
    int ans=0;
    int sj=0;
    while(x<=s){
        int sum=lucas(s-x+(n-1),s-x);
        if(s-x>sj)
        sum=((sum-lucas(s-x+(n-1)-sj-1,s-x-sj-1))%mod+mod)%mod;
        int flc2=flc;
        while(s-x>=flc2){
            int qwq=s-x-flc2;
            sum+=lucas(qwq+(n-1),qwq);sum%=mod;
            if(qwq>sj)
            sum=((sum-lucas(qwq+(n-1)-sj-1,qwq-sj-1))%mod+mod)%mod;
            flc2+=flc;
        }
        ans=(ans+sum*(flc%mod)%mod)%mod;
        x-=lowbit(x);
        x|=flc;
        flc<<=1;
        sj<<=1;
        sj|=1;
    }
    cout<<ans<<'\n';
}
signed main(){
    init_of_C(mod-1);
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}

:::