打卡信奥刷题（3102）用C++实现信奥题 P7224 [RC-04] 子集积

P7224 [RC-04] 子集积题目描述给出nnn个整数a1∼ana_1\sim a_na1​∼an​它们构成的多重集中有几个子集的元素积大于mmm空集的元素积等于111两个子集不同当且仅当它们中包含元素的下标不同。答案很大因此请输出它对998244353998244353998244353取模的值。输入格式第一行两个整数n,mn,mn,m。接下来一行nnn个正整数a1∼ana_1\sim a_na1​∼an​描述这个多重集。输出格式一行一个整数为答案对998244353998244353998244353取模的值。输入输出样例 #1输入 #14 4 1 1 2 3输出 #14输入输出样例 #2输入 #220 123456 1 5 12 24 189893 233333 2 22 134 3284 28456 261 50 10 1 2 2 2 2 22输出 #21036360说明/提示【样例111解释】以下子集符合要求{a3,a4}\{a_3,a_4\}{a3​,a4​}{a1,a3,a4}\{a_1,a_3,a_4\}{a1​,a3​,a4​}{a2,a3,a4}\{a_2,a_3,a_4\}{a2​,a3​,a4​}{a1,a2,a3,a4}\{a_1,a_2,a_3,a_4\}{a1​,a2​,a3​,a4​}。【数据范围】对于所有数据0≤n,m≤1060\le n,m\le 10^60≤n,m≤1061≤ai≤1061\le a_i\le 10^61≤ai​≤106。详细数据范围如下表测试点编号nnnmmmaia_iai​每测试点分数1110001112220001113∼63\sim 63∼6≤22\le 22≤224447∼107\sim 107∼10≤1000\le 1000≤1000≤1000\le 1000≤100044411∼1411\sim 1411∼14互不相同44415∼1915\sim 1915∼19≤2×105\le 2\times 10^5≤2×105≤2×105\le 2\times 10^5≤2×10555520∼2420\sim 2420∼24555C实现#includebits/stdc.h#defineintlonglong#defineMAX1000005#definemod998244353usingnamespacestd;inta[MAX],dp[MAX],f[MAX],inv[MAX],cnt[MAX],maxn,n,m;intkm(intq){//快速幂if(q0)return1;if(q1)return2;intpkm(q/2)%mod;if(q%2)returnp*p*2%mod;returnp*p%mod;}intC(intn,intm){//逆元求排列组合return(((f[n]*inv[n-m])%mod)*inv[m])%mod;}signedmain(){cin.tie(nullptr);cinnm;dp[1]f[0]inv[0]inv[1]f[1]1;intanskm(n);for(inti1;in;i)cina[i],cnt[a[i]],maxnmax(a[i],maxn);for(inti2;in;i)inv[i](mod-mod/i)*inv[mod%i]%mod;for(inti2;in;i){inv[i]inv[i-1]*inv[i]%mod,f[i]f[i-1]*i%mod;}for(inti2;imaxn;i){if(!cnt[i])continue;for(intjm-m%i;j0;j-i){//找i的倍数intk1,pi;while(kcnt[i]!(j%p)){//枚举i^kdp[j]dp[j/p]*C(cnt[i],k)%mod;dp[j]%mod,k,p*i;}}}intfakm(cnt[1]);for(inti1;im;i){ans-(dp[i]*fa)%mod;ans((ans%mod)mod)%mod;}coutans;return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容