集合操作

集合操作

https://ac.nowcoder.com/acm/contest/7413/B

思路:
很容易知道所有的情况共有2^n个,然后我们思考不可能存在的情况有多少种。
我们知道每次都可以从前m+1个种取一个。
当我们左边减少0个,那么右边m+1到n中任意数字减少都不行,因此答案有2^(n-m-1)-1种(真子集都是不存在的情况,-1是因为自己一个不去)
当我们左边m+1个中减少1个,那么答案为C(m+1, 1)(2^(n-m-2)-1)
若从左边m+1个中减少2个,那么答案为C(m+2, 2)
(2^(n-m-3)-1)
。。。
以此类推直到最后情况即n-m-i-1==0即可
代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+1000;
const ll MOD=998244353;
ll inv[maxn+10],fac[maxn+10];

ll fast_pow(ll a,ll b)
{
    ll ans=1;
    while(b){
        if(b&1ll)ans=a*ans%MOD;
        a=a*a%MOD;
        b>>=1ll;
    }
    return ans;
}
void pre()
{
    inv[0]=1ll;
    fac[0]=1ll;
    for(int i=1;i<=maxn;i++){
        fac[i]=fac[i-1]*i%MOD;
        inv[i]=fast_pow(fac[i],MOD-2ll);
    }
}
ll C(ll a,ll b)
{
    return fac[a]*inv[b]%MOD*inv[a-b]%MOD;
}
int main()
{
    pre();
    ll n, m, ans;
    cin >> n >> m;
    ans = fast_pow(2, n);
    ll less = 0;
    for(int i = 0; n-m-i-1 >= 0; i++){
        less = (less+C(m+i, i)*(fast_pow(2, n-m-i-1) - 1)%MOD)%MOD;
    }
    cout << ((ans-less)+MOD)%MOD << endl;
}
全部评论

相关推荐

在debug的柠檬精很迷人:好消息:现在HR挑三拣四 15年后 HR跪着求要简历 坏消息:被挑的是这代人,到时候求人的也是这代人。真好。
点赞 评论 收藏
分享
程序员牛肉:主要是因为小厂的资金本来就很吃紧,所以更喜欢有实习经历的同学。来了就能上手。 而大厂因为钱多,实习生一天三四百的就不算事。所以愿意培养你,在面试的时候也就不在乎你有没有实习(除非是同级别大厂的实习。) 按照你的简历来看,同质化太严重了。项目也很烂大街。 要么换项目,要么考研。 你现在选择工作的话,前景不是很好了。
点赞 评论 收藏
分享
评论
2
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务