企业官网建设流程全解析

P10380 「ALFR Round 1」D 小山的元力

题目描述

小山有nnn个相同的元素，他想将这nnn个元素分为mmm堆，显然有很多种分法。对于每种分法，定义aia_iai​为第iii堆的元素数量，bi=i!×aib_i=i!\times a_ibi​=i!×ai​（其中i!i!i!表示iii的阶乘），以及c=∑i=1mbic=\sum\limits_{i=1}^mb_ic=i=1∑m​bi​。而小山的元力为所有分法的ccc值之和。小山想知道他的元力是多少，由于答案可能很大，所以最终答案应对ppp取模（保证ppp为质数）。

输入格式

一行三个整数n,m,pn,m,pn,m,p，含义见题目描述。

输出格式

一个数表示小山的元力。

输入输出样例 #1

输入 #1

3 2 37

输出 #1

18

说明/提示

样例解释

将333个元素分为222堆的方案为：

1. 0 3
2. 1 2
3. 2 1
4. 3 0

小山的元力为：(1!×0+2!×3)+(1!×1+2!×2)+(1!×2+2!×1)+(1!×3+2!×0)=18(1!\times0+2!\times3)+(1!\times1+2!\times2)+(1!\times2+2!\times1)+(1!\times3+2!\times0)=18(1!×0+2!×3)+(1!×1+2!×2)+(1!×2+2!×1)+(1!×3+2!×0)=18。

数据范围

对于100%100\%100%的数据，1≤n,m≤1061\le n,m\le10^61≤n,m≤106，1≤p≤1071\le p\le10^71≤p≤107。

C++实现

#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=1e6+5;intn,m,P;intfac[N],inv[N],a[N],ans=0;intsum[N];intqpow(inta,intb){intres=1,base=a;while(b){if(b&1)res*=base;base*=base;res%=P;base%=P;b>>=1;}returnres;}intC(intn,intm){returnfac[n]*inv[n-m]%P*inv[m]%P;}intLucas(intn,intm){if(m==0)return1;returnLucas(n/P,m/P)*C(n%P,m%P)%P;}signedmain(){cin>>n>>m>>P;fac[0]=fac[1]=inv[0]=inv[1]=sum[1]=1;for(inti=2;i<=N-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(inti=1;i<=N-5;i++){inv[i]=inv[i-1]*inv[i]%P;}if(m==1){cout<<n%P<<"\n";return0;}for(intj=1;j<=n;j++){intnow=Lucas(m-2+n-j,m-2);ans+=(sum[m]*j%P*now%P);ans%=P;}cout<<ans%P<<"\n";return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容