建一个wordpress网站成本,微企点做网站怎么样,第三方检测机构,查商标官网正题
题目链接:https://www.luogu.com.cn/problem/P4640 题目大意 nnn种物品#xff0c;其中ttt种物品是有个数限制的#xff0c;第iii种限制为bib_ibi#xff0c;求选出mmm个物品的方案数%p\% p%p的值 1≤n,m,bi≤109,0≤t≤15,p∈[1,105]∩Pri1\leq n,m,b_i\leq 10^9,0…正题
题目链接:https://www.luogu.com.cn/problem/P4640 题目大意
nnn种物品其中ttt种物品是有个数限制的第iii种限制为bib_ibi求选出mmm个物品的方案数%p\% p%p的值 1≤n,m,bi≤109,0≤t≤15,p∈[1,105]∩Pri1\leq n,m,b_i\leq 10^9,0\leq t\leq 15,p\in[1,10^5]\cap Pri1≤n,m,bi≤109,0≤t≤15,p∈[1,105]∩Pri 解题思路
看上去就很OGF\text{OGF}OGF的题目 对于有限制的物品为f(x)1−xbi11−xf(x)\frac{1-x^{b_i1}}{1-x}f(x)1−x1−xbi1其他都是f(x)11−xf(x)\frac{1}{1-x}f(x)1−x1。
然后nnn个乘起来的话然后求前mmm次项的系数。
分子因为只有ttt个有值直接暴力乘起来。下面那个分母是1(1−x)n\frac{1}{(1-x)^n}(1−x)n1
所以对于上面如果有一个axm−kax^{m-k}axm−k那么就会产生贡献 a∑i0k(ni−1n)a(nkn)a\sum_{i0}^{k}\binom{ni-1}{n}a\binom{nk}{n}ai0∑k(nni−1)a(nnk) 相等于选出0∼k0\sim k0∼k个球放进nnn个盒子里开一个垃圾箱把没用的球放进去就好了
然后模数小开LucasLucasLucas就好了
时间复杂度O(2tlogpn)O(2^t\log_p n)O(2tlogpn) code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N1e510;
ll n,t,m,p,b[20],ans,inv[N],fac[N];
ll C(ll n,ll m)
{return fac[n]*inv[m]%p*inv[n-m]%p;}
ll L(ll n,ll m){if(nm)return 0;if(np)return C(n,m);return L(n/p,m/p)*L(n%p,m%p)%p;
}
signed main()
{scanf(%lld%lld%lld%lld,n,t,m,p);for(ll i0;it;i)scanf(%lld,b[i]),b[i];inv[1]1;for(ll i2;ip;i)inv[i]p-inv[p%i]*(p/i)%p;inv[0]fac[0]1;for(ll i1;ip;i)fac[i]fac[i-1]*i%p,inv[i]inv[i-1]*inv[i]%p;ll MS(1t); for(ll s0;sMS;s){ll f1,sum0;for(ll i0;it;i)if((si)1)f-f,sumb[i];(ansL(nm-sum,n)*f)%p;}printf(%lld\n,(ansp)%p);return 0;
}
