思路:
很容易知道所有的情况共有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; }