题解 | 前缀平方和序列

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll N=1e3+1,mod=1e9+7;

ll fact[N];         //阶乘
ll in_fact[N];      //阶乘逆元

ll fast_p(ll a,ll b){
    ll res=1;
    a%=mod;

    while(b!=0){
        if(b&1){
            res=(res*a)%mod;
        }
        a=(a*a)%mod;
        b>>=1;
    }
    return res;
}

void pre(){
    fact[0]=1;
    in_fact[0]=1;

    for(ll i=1;i<N;i++){
        fact[i]=(fact[i-1]*i)%mod;
        in_fact[i]=fast_p(fact[i],mod-2);
    }
}

ll C(ll a,ll b){
    if(b<0||b>a)return 0;
    return fact[a]*in_fact[b]%mod*in_fact[a-b]%mod;
}


int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    ll n,x;
    cin>>n>>x;
    ll t=(ll)sqrt(x);
    pre();
    //cout<<fact[5]<<' '<<in_fact[4]<<'\n';
    cout<<C(t,n);


    return 0;
}