打卡信奥刷题（3441）用C++实现信奥题 P10380 「ALFR Round 1」D 小山的元力

P10380 「ALFR Round 1」D 小山的元力题目描述小山有nnn个相同的元素他想将这nnn个元素分为mmm堆显然有很多种分法。对于每种分法定义aia_iai​为第iii堆的元素数量bii!×aib_ii!\times a_ibi​i!×ai​其中i!i!i!表示iii的阶乘以及c∑i1mbic\sum\limits_{i1}^mb_ici1∑m​bi​。而小山的元力为所有分法的ccc值之和。小山想知道他的元力是多少由于答案可能很大所以最终答案应对ppp取模保证ppp为质数。输入格式一行三个整数n,m,pn,m,pn,m,p含义见题目描述。输出格式一个数表示小山的元力。输入输出样例 #1输入 #13 2 37输出 #118说明/提示样例解释将333个元素分为222堆的方案为0 31 22 13 0小山的元力为(1!×02!×3)(1!×12!×2)(1!×22!×1)(1!×32!×0)18(1!\times02!\times3)(1!\times12!\times2)(1!\times22!\times1)(1!\times32!\times0)18(1!×02!×3)(1!×12!×2)(1!×22!×1)(1!×32!×0)18。数据范围子任务分值限制000202020n,m≤5n,m\le5n,m≤5111808080-对于100%100\%100%的数据1≤n,m≤1061\le n,m\le10^61≤n,m≤1061≤p≤1071\le p\le10^71≤p≤107。C实现#includebits/stdc.husingnamespacestd;#defineintlonglongconstintN1e65;intn,m,P;intfac[N],inv[N],a[N],ans0;intsum[N];intqpow(inta,intb){intres1,basea;while(b){if(b1)res*base;base*base;res%P;base%P;b1;}returnres;}intC(intn,intm){returnfac[n]*inv[n-m]%P*inv[m]%P;}intLucas(intn,intm){if(m0)return1;returnLucas(n/P,m/P)*C(n%P,m%P)%P;}signedmain(){cinnmP;fac[0]fac[1]inv[0]inv[1]sum[1]1;for(inti2;iN-5;i){fac[i]fac[i-1]*i%P;sum[i](sum[i-1]fac[i])%P;inv[i](P-P/i)*inv[P%i]%P;}for(inti1;iN-5;i){inv[i]inv[i-1]*inv[i]%P;}if(m1){coutn%P\n;return0;}for(intj1;jn;j){intnowLucas(m-2n-j,m-2);ans(sum[m]*j%P*now%P);ans%P;}coutans%P\n;return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容