计数__牛客网

C++

kilomatutinal

这道题好简单喵~

设n0等于缺失数数量，w等于可填入数字的数量的话。

可能性公式为 C ( n0 + w−1 , w−1 ) 喵！

等同于在w个洞洞里插入n0个棍子且每个洞可以插无数个棍子时有多少种可能喵~

理解这个后困难的就只有快速幂和C( a , b )的计算了；

众所周知，C( a , b )的计算公式为 $\frac{a!}{b!*(a-b)!}$

又众所周知(a/b)(mod k)不等于a(mod k)/b(mod k)

所以作除数还要变成逆元形式喵！

又根据众所周知的费马小定理可知

a^-1(mod k)等于a^k-2(mod k)

把这些一结合就出来代码啦喵~

#include <bits/stdc++.h>
using namespace std;
using ll=long long;

const ll mod=1000000007;

vector<ll> jie(1e6+1e3+5);//阶乘的结果

ll mi(ll a,ll b)//快速幂
{
    ll ans=1;
    while(b)
    {
        if(b&1) ans=(ans*a)%mod;
        b>>=1;
        a=(a*a)%mod;
    }
    return ans;
}

ll c(ll a,ll b)
{
    b=min(b,a-b);//取较少的b减少计算量
    ll mu=jie[a];
    ll zi=mi(jie[b]*jie[a-b]%mod,mod-2);//这里一定要%mod
    return mu*zi%mod;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    
    /*>>>>>>>>>>>>>>预处理阶乘>>>>>>>>>>>*/
    jie[0]=1;
    for(ll i=1;i<=1e6+1e3;i++)
    {
        jie[i]=jie[i-1]*i%mod;
    }
    /*>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>*/
    ll f=1000;//前一个非缺失数，初始是1000
    ll n0=0;//连续缺失数的计数
    ll n;cin >> n;
    ll ans=1;//总方案数
    for(ll i=0;i<n;i++)
    {
        ll num;cin >> num;
        if(num==0)//如果该数是缺失数
        {
            n0++;
        }
        else//如果不是缺失数
        {
            if(n0!=0)//之前有缺失数
            {
                ll w=f-num+1;//可填入数字的数量
                ans=ans*c(n0+w-1,w-1)%mod;
                n0=0;//缺失数数量清零
            }
            f=num;//更新前一个非缺失数
        }
    }
    if(n0!=0)//最后不要放过漏网之鱼
    {
        ans=ans*c(n0+f-1,f-1)%mod;
    }
    cout << ans;
}
/*
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣤⣤⡀⣀⣠⣤⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣀⡀⢀⣴⣾⣷⣶⣾⣿⣿⣿⣿⣿⣿⣿⣿⣷⣾⣿⣷⣦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣾⣿⣿⣿⣿⣿⣿⣿⠿⠛⠛⠉⠉⠉⠉⠉⠉⠛⠻⠿⣿⣿⣿⣿⣿⣶⣤⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⢠⣾⣿⣿⣿⡿⠿⠛⠉⠉⠉⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠙⠿⣿⣿⣿⣷⣄⡀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⣀⣿⣿⣿⠟⠁⠀⠀⠀⠀⠀⠀⠀⣰⡆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠿⣿⣿⣿⡄⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⣠⣾⣿⣿⠟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣶⣄⠀⠀⠀⠀⠀⢀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⣻⣿⣿⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⢹⣿⡿⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⣿⠁⠈⢢⡀⠀⠀⠀⢸⡇⢀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠻⣿⡟⠒⢦⡀⠀⠀⠀
⠀⠀⣠⣤⣤⣼⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠸⡇⠀⠀⠀⠉⢢⣄⠀⠀⢿⠊⠳⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⣷⡄⠀⢷⠀⠀⠀
⠀⢰⠇⠀⣰⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡇⠀⠀⠀⠀⡌⣹⠗⠦⣬⣇⠀⠉⢢⡀⠀⠀⠀⠀⠀⠀⠀⠀⠘⣿⡀⢸⡄⠀⠀
⠀⡟⠀⣼⣯⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⣆⢹⡀⠀⠀⠀⠉⠁⠀⠀⢀⣀⡁⠀⠀⠉⠳⢴⡆⠀⠀⠀⠀⠀⠀⢹⣧⠈⡇⠀⠀
⠀⡇⠀⠀⢻⣦⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣾⠻⠉⠛⠂⠀⠀⠀⠀⠀⠀⠻⠿⣿⣿⣿⣶⣦⡀⠛⣇⠀⠀⠀⠀⠀⣈⣿⠀⡇⠀⠀
⢸⡇⠀⠀⢠⣿⣷⣦⣀⡸⣷⣦⣶⡂⠉⠉⠉⢁⣤⣶⡶⠀⠀⠀⣀⣀⡴⠀⠀⠀⠀⠀⠀⠈⠉⠉⠁⠀⡟⢀⣴⣟⣰⣾⣿⣏⣠⠇⠀⠀
⠈⡇⠀⠀⢸⣿⠁⠉⣿⠛⠛⠃⡇⠀⠀⢠⣶⣿⡿⠛⠁⠀⠀⠉⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠼⢿⠟⠿⢿⡏⠀⠘⣿⡀⠀⠀⠀
⠀⢷⣀⣀⣿⠇⠀⠀⢿⡇⠀⢀⢱⡀⠀⠛⠛⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣼⠀⠀⢸⠇⠀⠀⢹⣿⣄⠀⠀
⠀⠀⣉⣿⡏⠀⠀⠀⠀⠀⠀⢸⣇⣳⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡰⣿⠃⠀⠀⠀⠀⠀⠀⣿⠈⢧⠀
⠀⠘⣿⣿⠁⠀⠀⠀⠀⠀⠀⠘⣿⡛⣶⠀⠀⣠⠔⠒⠛⠒⠦⡀⠀⠀⠀⠀⣠⡤⠶⠤⢤⣀⠀⠀⠀⢀⣏⡄⠀⠀⠀⠀⠀⡀⣿⡆⠈⣧
⣠⡾⠛⣿⣿⣧⠀⠀⠀⠀⢸⣿⠾⢿⡿⠀⣰⠃⠀⠀⠀⠀⠀⢹⡄⠀⠀⡼⠁⠀⠀⠀⠀⠈⠙⣦⠀⢸⣿⡇⣾⣣⡀⠀⢰⣿⣿⣿⣤⠾
⡟⠀⠀⠻⣿⡟⢷⡄⣤⡀⠈⣿⡀⣸⠇⠀⠏⠀⠀⠀⠀⠀⠀⠀⡇⠀⠀⡇⢀⡀⠀⠀⠀⠀⢀⡟⠀⠀⠋⣿⣿⣿⡇⣠⣿⠿⠛⢷⡀⠀
⠀⠀⠀⠀⣿⣇⣨⣿⣿⣿⣦⣽⣷⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠁⠀⠀⠃⠀⠙⠢⠤⠤⠴⢾⠀⠀⠀⠀⢸⣷⣿⣿⠟⠁⠀⠀⠈⣧⠀
⠀⠀⠀⠀⠈⠉⠉⠁⠈⠉⠈⢉⣿⡁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠀⠀⠀⠀⢸⡇⠀⠀⠀⠀⠀⠀⠀⣿⠀
*/

发表于 2026-01-29 15:44:49 回复(2)

pandaC222

我讨厌数学

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 0x3f3f3f3f3f3f3f3f;
const int mod=1e9+7;
const int mx=1e6+1000;
int fac[mx+1];
int fastpow(int x,int p){
    int ans=1;
    while(p){
        if(p&1) ans=ans*x%mod;
        x=x*x%mod;
        p>>=1;
    }
    return ans%mod;
}
int inv(int x){
    return fastpow(x,mod-2);
}
int c(int a,int b){
    return fac[a]*inv(fac[b])%mod*inv(fac[a-b])%mod;
}
void solve(){
    int n;cin>>n;
    vector<int> a(n+2);
    a[0]=1000,a[n+1]=1;
    for(int i=1;i<=n;i++) cin>>a[i];
    int r=0;
    int ans=1;
    for(int i=1;i<=n;i++){
        if(a[i]==0){
            r=i+1;
            while(a[r]==0){
                r++;
            }
            int l=r-i;
            int cnt=abs(a[r]-a[i-1])+1;
//             cout<<l<<" "<<cnt<<" ";
//             cout<<c(cnt+l-1,cnt-1)<<" ";
            ans=ans*c(cnt+l-1,cnt-1)%mod;
            i=r-1;
        }
    }
    cout<<ans%mod;
}
signed main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t=1;
    fac[0]=1;
    for(int i=1;i<=mx;i++){
        fac[i]=fac[i-1]*i%mod;
    }
    // cin>>t;
    while(t--){
        solve();
    }return 0;
}

发表于 2026-01-29 14:30:11 回复(0)

C++

Reisentyan

前两天学卡特兰数，大脑过拟合了。

原来还是组合数学的插板法

将一串 0 的长度视为 n 个小球

将前后的差值 k 视作 k-1 个板子

目标是在 n 个小球之间插 k-1 个板子，问有多少种

注意到，代码要写成这样：

void solve()
{
    ll n = q_;
    vector<ll>num(n + 2, 0), jie(1100 + (n << 1), 0);
    jie[0] = 1; ffp(i, 1, (1000 + (n << 1)))jie[i] = jie[i - 1] * i % MOD;
    ffp(i, 1, n)
    {
        num[i] = q_;
    }
    num[0] = 1000; num[n + 1] = 1; int p = 0;
    ll ans = 1;
    ffp(i, 1, n + 1)
    {
        if (num[i] == 0)continue;
        ll k = num[p] - num[i] + 1;
        ll h = i - p - 1;
        ans *= jie[h + k - 1] * inv(jie[h]) % MOD * inv(jie[k - 1]) % MOD;
        ans %= MOD;
        p = i;
    }
    cout << ans << endl;
}

发表于 2026-01-29 16:15:41 回复(0)

C++

牛客203596504号

使用C++的小伙伴可以通过编译期预计算，把10万以内的阶乘和对应逆元填充成数组。
运行时直接用查表法，速度无与伦比。

发表于 2026-01-29 23:42:41 回复(0)

计数

问题信息

热门推荐

相关试题