P4370 [Code+#4]组合数问题2

· · 题解

可以通过杨辉三角与组合数的关系得到，C(n,n/2)是值最大的。

通过BFS扩展k次，每次用set判断是否重复选择

用set存下x* n+y看set的size是否变大判断该点是否被扩展过了

但是优先队列在比较$C()$大小时需要比较的时$C()$未$mod$时的大小，这样会导致炸$long$ $long

比较C(x,y)的大小可以转化为比较log(x!)-log(y!)-log((x-y)!)

预处理i=1->n的log(i!)公式： lg_1=0，lg_i=lg_{i-1}+log(i)

代码：

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define int LL
#define N 1000006
#define mod 1000000007
LL inv[N],fac[N];
double lg[N];
LL mul(int a,int b)
{
    LL ans=1;
    while(b)
    {
        if(b&1) ans=ans*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return ans;
}
LL C(int x,int y)
{
    if(x<y) return 0;
    if(y==0) return 1;
    if(x==y) return 1;
    return fac[x]*inv[y]%mod*inv[x-y]%mod;
}
struct node{
    int x,y;
    bool operator <(const node t)const{
        return lg[x]-lg[y]-lg[x-y]<lg[t.x]-lg[t.y]-lg[t.x-t.y];
    }
};
priority_queue<node> q;
set<LL> s;
int dx[6]={0,-1,1,0,0};
int dy[6]={0,0,0,-1,1};

signed main()
{
    int n,k;
    scanf("%lld%lld",&n,&k);
    fac[1]=1;
    lg[1]=0;
    for(int i=2;i<=n;i++) 
    {
        fac[i]=fac[i-1]*i%mod;
        lg[i]=lg[i-1]+log(i);
    }
    inv[n]=mul(fac[n],mod-2);
    for(int i=n-1;i>=1;i--) inv[i]=inv[i+1]*(i+1)%mod;
    s.insert(n*n+n/2);
    q.push((node){n,n/2});
    LL ans=0;
    for(int i=1;i<=k;i++)
    {
        node nw=q.top();q.pop();
//      cout<<"LPL"<<nw.x<<' '<<nw.y<<endl;
        ans=(ans+C(nw.x,nw.y))%mod;
        for(int j=1;j<=4;j++)
        {
            int x=nw.x+dx[j],y=nw.y+dy[j];
            if(x<0||x>n||y<0||y>n) continue;
            int p=s.size();
            s.insert(x*n+y);
            if(s.size()==p) continue;
            q.push((node){x,y});
        }
    }
    return printf("%lld\n",ans),0;
}