建网站传播文化的好处,做家政下载什么网站或什么群呢,电商代运营公司十强,百度快照怎么看正题
题目链接:https://www.luogu.com.cn/problem/P2000 题目大意
十种东西#xff0c;有要求 金神石A的块数必须是 6 的倍数。 木神石A最多用 9 块。 水神石A最多用 5 块。 火神石A的块数必须是 4 的倍数。 土神石A最多用 7 块。 金神石B的块数必须是 2 的倍数。 木神石B最…正题
题目链接:https://www.luogu.com.cn/problem/P2000 题目大意
十种东西有要求 金神石A的块数必须是 6 的倍数。 木神石A最多用 9 块。 水神石A最多用 5 块。 火神石A的块数必须是 4 的倍数。 土神石A最多用 7 块。 金神石B的块数必须是 2 的倍数。 木神石B最多用 1 块。 水神石B的块数必须是 8 的倍数。 火神石B的块数必须是 10 的倍数。 土神石B最多用 3 块。 要求所有物品物件和为nnn求方案数。 解题思路
考虑生成函数用生成函数分别表示就是 (1x6x12x18...)∗(x1x2...x9)∗...(1x^6x^{12}x^{18}...)*(x^1x^2...x^9)*...(1x6x12x18...)∗(x1x2...x9)∗... 推下去我们可以化简后得出 11−x6∗1−x101−x∗1−x61−x∗11−x4∗1−x81−x\frac{1}{1-x^6}*\frac{1-x^{10}}{1-x}*\frac{1-x^6}{1-x}*\frac{1}{1-x^4}*\frac{1-x^8}{1-x}1−x61∗1−x1−x10∗1−x1−x6∗1−x41∗1−x1−x8
∗*∗
11−x2∗1−x21−x∗11−x8∗11−x10∗11−x3\frac{1}{1-x^2}*\frac{1-x^2}{1-x}*\frac{1}{1-x^8}*\frac{1}{1-x^{10}}*\frac{1}{1-x^3}1−x21∗1−x1−x2∗1−x81∗1−x101∗1−x31 然后约分后得到 原式1(1−x)5Cn44原式\frac{1}{(1-x)^5}C^{4}_{n4}原式(1−x)51Cn44
最后化简成组合数我是不会的但是换种方法可以理解为 1(1−x)2(∑i0∞xi)5\frac{1}{(1-x)^2}(\sum_{i0}^{\infty}x^i)^5(1−x)21(i0∑∞xi)5 就是将nnn个数划分成五段的方案数可以为空
这样就可以化简成那个组合数
然后考虑高精度计算Cn44(n1)∗(n2)∗(n3)∗(n4)24C^4_{n4}\frac{(n1)*(n2)*(n3)*(n4)}{24}Cn4424(n1)∗(n2)∗(n3)∗(n4)
因为数据很大需要NTTNTTNTT优化高精度这里的方法是
因为原本的乘法需要模101010不是质数很难搞这里我们可以先让他模一个大质数计算完后再统一进位这里需要保证两个位上的数相乘不会大于那个大质数
然后除单精就好了 codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N5e610,XJQ998244353;
char s[N];
ll n,L,invn;
ll a[N],b[N],r[N];
ll power(ll x,ll b){ll ans1;while(b){if(b1)ansans*x%XJQ;xx*x%XJQ;b1;}return ans;
}
void NTT(ll *x,ll op){for(ll i0;in;i)if(ir[i])swap(x[i],x[r[i]]);for(ll p2;pn;p1){ll lp1,tmppower(3,(XJQ-1)/p);if(op-1)tmppower(tmp,XJQ-2);for(ll k0;kn;kp){ll buf1;for(ll ik;ikl;i){ll ttbuf*x[il]%XJQ;x[li](x[i]-ttXJQ)%XJQ;x[i](x[i]tt)%XJQ;bufbuf*tmp%XJQ;}}}if(op-1)for(ll i0;in;i)x[i]x[i]*invn%XJQ;return;
}
void mul(ll x){for(ll i0;iL;i)b[L-i-1]s[i]-0;b[0]x;NTT(a,1);NTT(b,1);for(ll i0;in;i)a[i]a[i]*b[i]%XJQ,b[i]0;NTT(a,-1);for(ll i0;in;i){(a[i1]a[i]/10)%XJQ;a[i]%10;}return;
}
int main()
{scanf(%s,s);Lstrlen(s);for(ll i0;iL;i)a[L-i-1]s[i]-0;for(n1;nL*5;n1);for(ll i0;in;i)r[i](r[i1]1)|((i1)?(n1):0);invnpower(n,XJQ-2);a[0];for(ll i2;i4;i)mul(i);for(ll in-1;i0;i--)a[i-1]a[i]%24*10,a[i]/24;ll wn-1;while(!a[w])w--;for(;w0;w--)printf(%lld,a[w]);
}
