智能网站推广优化,做外贸网站企业,网站建设方案书 5个备案,2022最火代理产品Problem - H - Codeforces
题意#xff1a; 定义一个集合S为T的孩子是#xff0c;对于S中的每一个元素x#xff0c;在T中都能找到x1。 给定n#xff0c;k#xff0c;每一个集合中的元素x必须满足 1 x k 1xk 1xk且 c n t [ x ] 1 cnt[x…Problem - H - Codeforces
题意 定义一个集合S为T的孩子是对于S中的每一个元素x在T中都能找到x1。 给定nk每一个集合中的元素x必须满足 1 x k 1xk 1xk且 c n t [ x ] 1 cnt[x]1 cnt[x]1若n个集合重排后对于 1 i n 1in 1in都可以满足 S i − 1 S_{i-1} Si−1为 S i S_i Si的孩子则该n个集合是一个合法序列求所有合法序列的个数。 思路 定义 f [ i ] f[i] f[i]为最后一个集合中若 i i i存在只看 i i i的贡献可以构成合法的之前集合的总个数。 则 f [ 1 ] 1 , f [ i ] f [ i − 1 ] 1 f[1]1,f[i]f[i-1]1 f[1]1,f[i]f[i−1]1因为最后一个集合里1只能是自己冒出来的不能是由前面变来的之后每一个数都可以是自己冒出来的贡献为1也可以是将使集合中出现i-1的那个位置上的数提前出现一位导致原来的i-1变成现在的i。由于最后一个集合中出现每一个数都是独立的所以可以用乘法原理算得每种情况求出 p r e [ i ] pre[i] pre[i]表示至少有n-i个空集的集合有多少情况。 AC代码
#include bits/stdc.h
using namespace std;
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
#define int ll
#define pb push_back
#define eb emplace_back
#define m_p make_pair
const int mod 998244353;
#define mem(a,b) memset(a,b,sizeof a)
#define pii pairint,int
#define fi first
#define se second
const int inf 0x3f3f3f3f;
const ll N 2e550;
//__builtin_ctzll(x);后导0的个数
//__builtin_popcount计算二进制中1的个数
int fac[N],inv[N];ll qp(ll a,ll b){ll ans1;a%mod;while(b){if(b1) ansans*a%mod;aa*a%mod;b1;}return ans;
}void init(){fac[0]fac[1]inv[0]inv[1]1;for(int i2;iN;i){fac[i]1ll*fac[i-1]*i%mod; //阶乘inv[i]1ll*inv[mod%i]*(mod-mod/i)%mod; //逆元}for(int i2;iN;i){inv[i]1ll*inv[i]*inv[i-1]%mod;}
}void work() {init();int n,k;cinnk;ll ans0;for(int i1;imin(n,k);i){ll res(fac[i1]*qp(i1,k-i)%mod-fac[i]*qp(i,k-i1)%modmod)%mod;//至少有n-(i1)个空集-至少有n-i个空集ans(ansres*fac[n]%mod*inv[n-i]%mod)%mod;//恰有n-i个空集的情况}ans;coutans\n;
}signed main() {io;int t1;//cin t;while (t--) {work();}return 0;
}
