题解：P2592 [ZJOI2008] 生日聚会

· · 题解

反射容斥好题啊。

提供一种理论复杂度 O(n\log_p n) 的做法（默认 n,m 同阶），其中 p 为题目给定的模数，在为质数时可以做到线性。

首先将本题转化到网格图上：

对于 k\ge\max\{n,m\} 的情况一定是 \binom{n+m}{n}，不再讨论。

对于坐一个女孩，我们可以看成 (x,y)\to(x,y+1)，对于坐一个男孩可以看成是 (x,y)\to(x+1,y)，那么题目中的限制实际是 \max_{i=1}^{n+m}\{y_i-x_i\}-\min_{i=1}^{n+m}\{y_i-x_i\}\le k，为了方便不妨令前面的 \max 等于 S_0，后面的 \min 为 S_1。

我们考虑怎么在网格图上刻画这个东西，我们不妨枚举两个边界 y=x+i 和 y=x+i+k，那么在这两条线中间的路径必然有 S_0-S_1\le k。

但是这样会算重，对于一条合法的路径它会被算 k-(S_0-S_1)+1 次，但是惊奇的发现这是一个等差数列的形式，我们再减去 k \gets k-1 的结果不就是我们想要的了嘛。

然后上面的格路计数部分可以使用反射容斥计算，需要算 O(k\times \frac{n}{k})=O(n) 次组合数，因为本题模数过于魔怔，故可以使用 exlucas 去计算，复杂度为 O(n\log_p n)。

PS：由于 exlucas 常数过大，实际上本题数据范围下跑不过 O(n^2) 预处理组合数的写法。

附两种计算组合数方法的提交记录：link1，link2

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>

#define LL long long
#define MOD 12345678
#define N 10000005

inline int R() {
    int x=0; bool f=0; char c=getchar();
    while (!isdigit(c)) f|=(c=='-'),c=getchar();
    while (isdigit(c)) x=x*10+c-'0',c=getchar();
    return f?-x:x;
}

template<typename T>
void W(T x,int op=0) {
    if (x<0) return putchar('-'),W(-x,op);
    if (x>9) W(x/10); putchar(x%10+'0');
    if (op) putchar(op==1?' ':'\n');
}

using namespace std;
int n,m,k;

namespace EXlucas {
    LL quickpow(LL a,LL k,int P) {
        LL res=1;
        while (k) {
            if (k&1) res=res*a%P;
            a=a*a%P,k>>=1;
        }
        return res;
    }

    LL exgcd(LL a,LL b,LL &x,LL &y) {
        if (!b) return x=1,y=0,a;
        LL d=exgcd(b,a%b,x,y),tx=x;
        x=y,y=tx-(a/b)*y;
        return d;
    }

    LL mul(LL a,LL b,int P) {
        a=(a%P+P)%P,b=(b%P+P)%P;
        LL res=0;
        while (b) {
            if (b&1) res=(res+a)%P;
            a=(a+a)%P,b>>=1;
        }
        return res;
    }

    LL excrt(int n,LL *r,LL *mod) {
        LL R=r[1],P=mod[1];
        for (int i=2;i<=n;i++) {
            LL x,y,d=__gcd(P,mod[i]),tm=P/d*mod[i];
            exgcd(P/d,mod[i]/d,x,y);
            R=(R+mul((r[i]-R)/d,mul(x,P,tm),tm))%tm,P=tm;
        }
        return (R+P)%P;
    }

    LL f(int n,int p,int P) {
        if (!n) return 1;
        LL k=1,d=1;
        for (int i=1;i<=P;i++)
            if (i%p) k=k*i%P;
        k=quickpow(k,n/P,P);
        for (int i=P*(n/P);i<=n;i++)
            if (i%p) d=d*(i%P)%P;
        return f(n/p,p,P)*k%P*d%P;
    }

    LL g(int n,int p) {
        if (n<p) return 0;
        return n/p+g(n/p,p); 
    }

    LL exlucas(int n,int m,int P) {
        if (n<m or n<0 or m<0) return 0;
        LL *r=new LL[2*(int)sqrt(P)],*c=new LL[2*(int)sqrt(P)];
        int cnt=0;
        for (int i=2;i*i<=P;i++)
            if (P%i==0) {
                int tmp=1,phi;
                while (P%i==0) tmp*=i,P/=i;
                phi=tmp/i*(i-1);
                c[++cnt]=tmp;
                r[cnt]=f(n,i,tmp)*quickpow(f(m,i,tmp),phi-1,tmp)%tmp
                    *quickpow(f(n-m,i,tmp),phi-1,tmp)%tmp
                    *quickpow(i,g(n,i)-g(m,i)-g(n-m,i),tmp)%tmp;
            }
        if (P>1) {
            c[++cnt]=P;
            r[cnt]=f(n,P,P)*quickpow(f(m,P,P),P-2,P)%P
                *quickpow(f(n-m,P,P),P-2,P)%P
                *quickpow(P,g(n,P)-g(m,P)-g(n-m,P),P)%P;
        }
        LL res=excrt(cnt,r,c);
        delete[] r,c;
        return res;
    }
} using EXlucas::exlucas;

LL calc(int k) {
    LL res=0;
    for (int l=min(m-n,0)-1,r=min(m-n,0)+k+1;r>max(m-n,0);l--,r--)
        for (int i=(n+r)/(r-l);n-i*(r-l)<=n+m;i--)
            (res+=exlucas(n+m,n-i*(r-l),MOD)-exlucas(n+m,n-i*(r-l)+r,MOD))%=MOD;
    return (res+MOD)%MOD;
}

int main() {
    n=R(),m=R(),k=R();
    if (k<abs(n-m)) return W(0,2),0;
    if (k>=max(n,m)) return W(exlucas(n+m,n,MOD),2),0;
    W((calc(k)-calc(k-1)+MOD)%MOD,2);
    return 0;
}