2024牛客寒假算法基础集训营1 补题

KrowFeather / 2024-02-05 / 原文

2024牛客寒假算法基础集训营1 补题

F-鸡数题！

F-鸡数题！_2024牛客寒假算法基础集训营1 (nowcoder.com)

1、对于任意的$i，a_i>0$

2、对于任意的整数$1≤i≤m−1，a_i<a_{i+1}$

3、$a_1∣a_2∣...∣a_{m−1}∣a_m=2n−1$（之中|为按位或操作）；

4、对于任意的$i≠j$，满足$a_i\& a_j=0$（之中&为按位与操作）。

实际上就是把n个1放入m个数中，第二类斯特林数，不过这题数据范围比较大，需要使用容斥求法计算斯特林数

公式为$S(n,k)=\Sigma_{i=0}^{k}(-1)^i\binom{k}{i}(k-i)^n$

AC代码如下：

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define int long long
using ull = unsigned long long;                                                                           
using ll = long long;
using i128 = __int128_t;
using pii = pair<int,int>;
using psi = pair<string,int>;
constexpr ll MOD = 1e9+7;
//-------------------------------------------------------->>>>>>>>>>
const int mod = 1e9+7;
const int N = 1e6+100;
int fac[N+2],invfac[N+2];
int qpow(int a,int b,int mod){
    int res=1;while(b){if(b&1){res=res*a%mod;}a=a*a%mod;b>>=1;}return res;
}
int inv(int x){return qpow(x,mod-2,mod);}
void init(int n){
    fac[0] = 1;for (int i = 1; i <= n; ++i) fac[i] = fac[i - 1] * i % mod;
    invfac[n] = inv(fac[n]);for (int i = n - 1; i >= 0; --i) invfac[i] = (invfac[i + 1] * (i + 1)) % mod;   
}
int C(int n,int m){
    if (n < m || m < 0) return 0;return fac[n]*invfac[m]%mod*invfac[n-m]%mod;
}
int S(int n,int k){
    int ans=0;
    for(int i=0;i<=k;i++){
        ans=(ans+mod)%mod;
        ans=(ans+(i%2?-1:1)*C(k,i)%mod*qpow(k-i,n,mod)%mod)%mod;
    }  
    ans=ans*invfac[k]%mod;
    return ans;
}
inline void solve(){
    int n,k;
    cin>>n>>k;
    cout<<S(n,k)<<"\n";
}
inline void prework(){
    init(1e5+10);
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    cout<<fixed<<setprecision(12);
    prework();
    int T=1; 
    // cin>>T;
    while(T--){
        solve();
    }
    return 0;
}