洛谷4345 [SHOI2015]超能粒子炮·改

反向最优解 $rk3$ 达成。

题意

求

$$\sum_{i=0}^k C_n^i\mod 2333$$

其中 $t\le 10^{5} \ , \ n,k\le 10^{18}$

题解

令 $ha=2333$ ，先用 $\text{Lucas}$ 定理化简

$$\sum_{i=0}^k C_{n\div ha}^{i\div ha}\times C_{n\ mod \ ha}^{i\ mod \ ha}\mod ha$$

对上式按照 $i\div ha$ 的值分块：

$$C_{n\div ha}^0\times \sum_{i=0}^{ha-1} C_{n\ mod \ ha}^i + C_{n\div ha}^1\times \sum_{i=0}^{ha-1} C_{n\ mod \ ha}^i + \ldots + C_{n\div ha}^{k\div ha-1}\times \sum_{i=0}^{ha-1} C_{n\ mod \ ha}^i \tag{1}$$

剩下的部分为

$$C_{n\div ha}^{k\div ha}\times \sum_{i=0}^{k\ mod \ ha} C_{n\ mod \ ha}^i\tag{2}$$

对整块 $(1)$ 进行合并

$$\sum_{i=0}^{ha-1} C_{n\ mod \ ha}^i \times (C_{n\div ha}^0+C_{n\div ha}^1+\dots+C_{n\div ha}^{k\div ha -1})\tag{3}$$

令

$$F(n,k)=\sum_{i=0}^k C_n^i$$

那么 $(3)$ 式化为

$$F(n\ mod \ ha,ha-1)\times F(n\div ha,k\div ha-1)\tag{4}$$

$(2)$ 式化为

$$C_{n\div ha}^{k\div ha}\times F(n\ mod \ ha,k\ mod \ ha)\tag{5}$$

答案即为 $(4)+(5)$ 。

除了 $F(n\div ha,k\div ha-1)$ ，其它的 $F()$ 中参数都 $\le ha$ ，可以先预处理出来。

组合数我就没有预处理了，直接拿 $\text{Lucas}$ 算，所以效率奇低。

#include<bits/stdc++.h>
#define ll long long
#define ha 2333

using namespace std;

inline ll read()
{
    char ch=getchar();
    ll f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

ll t,n,k,fac[2335],f[2335][2335];

inline void get_fac()
{
    fac[0]=fac[1]=1;
    for (ll i=2;i<=ha;i++) fac[i]=fac[i-1]*i%ha;
}

inline ll qpow(ll x,ll y)
{
    ll ans=1;
    while (y)
    {
        if (y&1) ans=ans*x%ha;
        y>>=1;
        x=x*x%ha;
    }
    return ans;
}

inline ll inv(ll x) { return qpow(x,ha-2); }

inline ll C(ll n,ll m)
{
    if (m>n) return 0;
    return fac[n]*(inv(fac[m])*inv(fac[n-m])%ha)%ha;
}

inline ll lucas(ll n,ll m)
{
    if (!m) return 1;
    return lucas(n/ha,m/ha)*C(n%ha,m%ha)%ha;
}

inline ll F(ll n,ll k)
{
    if (k<0) return 0;
    if (!k || !n) return 1;
    return (f[n%ha][ha-1]*F(n/ha,k/ha-1)%ha+lucas(n/ha,k/ha)*f[n%ha][k%ha]%ha)%ha;
}

signed main()
{
    get_fac();
    for (int i=0;i<=ha;i++) f[i][0]=1;
    for (int i=0;i<=ha;i++)
        for (int j=1;j<=ha;j++)
            f[i][j]=f[i][j-1]+C(i,j);
    t=read();
    while (t--)
    {
        n=read(); k=read();
        printf("%lld\n",F(n,k));
    }
    return 0;
}