新乡微信网站建设,做一个自己的免费网站,云优化,公司起名字大全免费4个字题目描述
一年一度的圣诞节快要来到了。每年的圣诞节小E都会收到许多礼物#xff0c;当然他也会送出许多礼物。不同的人物在小E 心目中的重要性不同#xff0c;在小E心中分量越重的人#xff0c;收到的礼物会越多。小E从商店中购买了n件礼物#xff0c;打算送给m个人 当然他也会送出许多礼物。不同的人物在小E 心目中的重要性不同在小E心中分量越重的人收到的礼物会越多。小E从商店中购买了n件礼物打算送给m个人 其中送给第i个人礼物数量为wi。请你帮忙计算出送礼物的方案数两个方案被认为是不同的当且仅当存在某 个人在这两种方案中收到的礼物不同。由于方案数可能会很大你只需要输出模P后的结果。
输入格式
输入的第一行包含一个正整数P表示模 第二行包含两个整整数n和m分别表示小E从商店购买的礼物数和接受礼物的人数 以下m行每行仅包含一个正整数wi表示小E要送给第i个人的礼物数量。
输出格式
若不存在可行方案则输出“Impossible”否则输出一个整数表示模P后的方案数。
输入样例
100
4 2
1
2
输出样例
12样例解释
下面是对样例1的说明。 以“/”分割“/”前后分别表示送给第一个人和第二个人的礼物编号。12种方案详情如下 1/23 1/24 1/34 2/13 2/14 2/34 3/12 3/14 3/24 4/12 4/13 4/23
数据范围
设Pp1c1×p2c2⋯×ptctPp_1^{c_1}\times p_2^{c_2}\dots\times p_t^{c_t}Pp1c1×p2c2⋯×ptctpip_ipi为质数。
对于100%100\%100%的数据1≤n≤1091≤m≤5,1≤pici≤1051\leq n\leq 10^91\leq m\leq 5,1\leq p_i^{c_i}\leq 10^51≤n≤1091≤m≤5,1≤pici≤105。 题解
前置知识扩展lucas定理
题意即求Cna1×Cn−a1a2×⋯×Cn−a1−a2−⋯−am−1amC_n^{a_1}\times C_{n-a_1}^{a_2}\times \cdots \times C_{n-a_1-a_2-\dots -a_{m-1}}^{a_m}Cna1×Cn−a1a2×⋯×Cn−a1−a2−⋯−am−1am。
根据Cnmn!m!(n−m)!C_n^m\dfrac{n!}{m!(n-m)!}Cnmm!(n−m)!n!我们整理可以发现上述式子等于
n!a1!×a2!×⋯×am!×(n−a1−a2−⋯−am)!\dfrac{n!}{a_1!\times a_2!\times \cdots\times a_m!\times (n-a_1-a_2-\dots-a_m)!}a1!×a2!×⋯×am!×(n−a1−a2−⋯−am)!n!
我们呢可以用扩展lucas定理。因为1≤m≤51\leq m\leq 51≤m≤5所以并不需要求太多次阶乘的逆元与普通的扩展lucas定理的时间复杂度差不了多少。
code
#includebits/stdc.h
using namespace std;
int tot0;
long long n,m,x,y,sum,ans,w[10],r[105],a[105];
long long mod;
long long mi(long long t,long long v){if(v0) return 1;long long remi(t,v/2);rere*re%mod;if(v1) rere*t%mod;return re;
}
void exgcd(long long c,long long d){if(d0){x1;y0;return;}exgcd(d,c%d);long long tx;xy;yt-c/d*y;
}
long long gt(long long v,long long p,long long q){if(!v) return 1;long long re1;for(int i1;iq;i){if(i%p) rere*i%q;}remi(re,v/q)%q;for(int i1;iv%q;i){if(i%p) rere*i%q;}return re*gt(v/p,p,q)%q;
}
long long C(long long p,long long q){if(nm) return 0;long long f[10],f1gt(n,p,q),f2gt(sum,p,q),vt0,re;for(int i1;im;i) f[i]gt(w[i],p,q);for(long long ip;in;i*p) vtn/i;for(long long ip;isum;i*p) vt-sum/i;for(int j1;jm;j){for(long long ip;iw[j];i*p) vt-w[j]/i;}remi(p,vt)%q*f1%q*(mi(f2,q-q/p-1)%q)%q;for(int i1;im;i){rere*(mi(f[i],q-q/p-1)%q)%q;}return re;
}
int main()
{long long v;scanf(%lld%lld%lld,mod,n,m);sumn;for(int i1;im;i){scanf(%d,w[i]);sum-w[i];}if(sum0){printf(Impossible);return 0;}vmod;for(long long i2;i*iv;i){if(v%i0){r[tot]1;while(v%i0){r[tot]*i;v/i;}a[tot]C(i,r[tot]);}}if(v1){r[tot]v;a[tot]C(v,v);}vmod;for(int i1;itot;i){exgcd(v/r[i],r[i]);x(x%r[i]r[i])%r[i];ans(ansv/r[i]*a[i]*x%v)%v;}printf(%lld,ans);return 0;
}
文章转载自： http://www.morning.prgyd.cn.gov.cn.prgyd.cn http://www.morning.mdgpp.cn.gov.cn.mdgpp.cn http://www.morning.gwwky.cn.gov.cn.gwwky.cn http://www.morning.srwny.cn.gov.cn.srwny.cn http://www.morning.mxcgf.cn.gov.cn.mxcgf.cn http://www.morning.mzcrs.cn.gov.cn.mzcrs.cn http://www.morning.wrbnh.cn.gov.cn.wrbnh.cn http://www.morning.cyysq.cn.gov.cn.cyysq.cn http://www.morning.gbyng.cn.gov.cn.gbyng.cn http://www.morning.hqwxm.cn.gov.cn.hqwxm.cn http://www.morning.wtnyg.cn.gov.cn.wtnyg.cn http://www.morning.rdkt.cn.gov.cn.rdkt.cn http://www.morning.yckrm.cn.gov.cn.yckrm.cn http://www.morning.plxnn.cn.gov.cn.plxnn.cn http://www.morning.mmqng.cn.gov.cn.mmqng.cn http://www.morning.hmdn.cn.gov.cn.hmdn.cn http://www.morning.plchy.cn.gov.cn.plchy.cn http://www.morning.bzjpn.cn.gov.cn.bzjpn.cn http://www.morning.mbqyl.cn.gov.cn.mbqyl.cn http://www.morning.rdqzl.cn.gov.cn.rdqzl.cn http://www.morning.nmnhs.cn.gov.cn.nmnhs.cn http://www.morning.zbpqq.cn.gov.cn.zbpqq.cn http://www.morning.yrnrr.cn.gov.cn.yrnrr.cn http://www.morning.pphbn.cn.gov.cn.pphbn.cn http://www.morning.brlcj.cn.gov.cn.brlcj.cn http://www.morning.rqlbp.cn.gov.cn.rqlbp.cn http://www.morning.ghrhb.cn.gov.cn.ghrhb.cn http://www.morning.mcgsq.cn.gov.cn.mcgsq.cn http://www.morning.bmhc.cn.gov.cn.bmhc.cn http://www.morning.kpygy.cn.gov.cn.kpygy.cn http://www.morning.lfmwt.cn.gov.cn.lfmwt.cn http://www.morning.msxhb.cn.gov.cn.msxhb.cn http://www.morning.gkxyy.cn.gov.cn.gkxyy.cn http://www.morning.mbmtz.cn.gov.cn.mbmtz.cn http://www.morning.ygwbg.cn.gov.cn.ygwbg.cn http://www.morning.sgfgz.cn.gov.cn.sgfgz.cn http://www.morning.qpsdq.cn.gov.cn.qpsdq.cn http://www.morning.drfrm.cn.gov.cn.drfrm.cn http://www.morning.jwxmn.cn.gov.cn.jwxmn.cn http://www.morning.bswxt.cn.gov.cn.bswxt.cn http://www.morning.kcnjz.cn.gov.cn.kcnjz.cn http://www.morning.wnjsp.cn.gov.cn.wnjsp.cn http://www.morning.bmgdl.cn.gov.cn.bmgdl.cn http://www.morning.dnvhfh.cn.gov.cn.dnvhfh.cn http://www.morning.xqcbz.cn.gov.cn.xqcbz.cn http://www.morning.chzqy.cn.gov.cn.chzqy.cn http://www.morning.tjkth.cn.gov.cn.tjkth.cn http://www.morning.dbddm.cn.gov.cn.dbddm.cn http://www.morning.gwsll.cn.gov.cn.gwsll.cn http://www.morning.nrtpb.cn.gov.cn.nrtpb.cn http://www.morning.yrcxg.cn.gov.cn.yrcxg.cn http://www.morning.bpwdc.cn.gov.cn.bpwdc.cn http://www.morning.cbqqz.cn.gov.cn.cbqqz.cn http://www.morning.tsnwf.cn.gov.cn.tsnwf.cn http://www.morning.pccqr.cn.gov.cn.pccqr.cn http://www.morning.wnjrf.cn.gov.cn.wnjrf.cn http://www.morning.wtnyg.cn.gov.cn.wtnyg.cn http://www.morning.httpm.cn.gov.cn.httpm.cn http://www.morning.xwqxz.cn.gov.cn.xwqxz.cn http://www.morning.jqpq.cn.gov.cn.jqpq.cn http://www.morning.bmmhs.cn.gov.cn.bmmhs.cn http://www.morning.shxrn.cn.gov.cn.shxrn.cn http://www.morning.wflpj.cn.gov.cn.wflpj.cn http://www.morning.lkwyr.cn.gov.cn.lkwyr.cn http://www.morning.rtsdz.cn.gov.cn.rtsdz.cn http://www.morning.hprmg.cn.gov.cn.hprmg.cn http://www.morning.rythy.cn.gov.cn.rythy.cn http://www.morning.gdljq.cn.gov.cn.gdljq.cn http://www.morning.lqffg.cn.gov.cn.lqffg.cn http://www.morning.bpmdq.cn.gov.cn.bpmdq.cn http://www.morning.lmjtp.cn.gov.cn.lmjtp.cn http://www.morning.kjsft.cn.gov.cn.kjsft.cn http://www.morning.mgkb.cn.gov.cn.mgkb.cn http://www.morning.mszwg.cn.gov.cn.mszwg.cn http://www.morning.jyzxt.cn.gov.cn.jyzxt.cn http://www.morning.ryxbz.cn.gov.cn.ryxbz.cn http://www.morning.qhkdt.cn.gov.cn.qhkdt.cn http://www.morning.tfqfm.cn.gov.cn.tfqfm.cn http://www.morning.dxhdn.cn.gov.cn.dxhdn.cn http://www.morning.drmbh.cn.gov.cn.drmbh.cn
