评价高的企业网站开发,佛山品牌推广,用html5做的音乐网站,招聘网58同城招聘发布P2000 拯救世界
题意#xff1a;
为了拯救世界#xff0c;小 a 和 uim 决定召唤出 kkksc03 大神和 lzn 大神。根据古籍记载#xff0c;召唤出任何一位大神#xff0c;都需要使用金木水火土五种五行神石来摆一个特定的大阵。而在古籍中#xff0c;记载是这样的#xff1…P2000 拯救世界
题意
为了拯救世界小 a 和 uim 决定召唤出 kkksc03 大神和 lzn 大神。根据古籍记载召唤出任何一位大神都需要使用金木水火土五种五行神石来摆一个特定的大阵。而在古籍中记载是这样的
kkksc03 大神召唤方法
金神石的块数必须是 6 的倍数。
木神石最多用 9 块。
水神石最多用 5 块。
火神石的块数必须是 4 的倍数。
土神石最多用 7 块。
lzn 大神召唤方法:
金神石的块数必须是 2 的倍数。
木神石最多用 1 块。
水神石的块数必须是 8 的倍数。
火神石的块数必须是 10 的倍数。
土神石最多用 33块。
现在是公元 1999 年 12 月 31 日小 a 和 uim 从 00:00:00 开始找一直找到 23:00:00终于还是没找到神石。不过他们在回到家后在自家地窖里发现了一些奇怪的东西一查古籍哎呦妈呀怎么不早点来呢这里有一些混沌之石可以通过敲击而衰变成五行神石。于是他们拼命地敲终于敲出了n块神石在 23:59:59 完成了两座大阵。然而kkksc03 大神和 lzn 大神确实出现了但是由于能量不够无法发挥神力。只有把所有用 n 块神石可能摆出的大阵都摆出来才能给他们充满能量。这下小 a 和 uim 傻了眼了赶快联系上了你让你帮忙算一下一共有多少种大阵。
题解
很明显生成函数题目 我们考虑每个石头的情况 kkksc03: 金神石的块数必须是 6 的倍数。f11x6x12..f11x^6x^{12}..f11x6x12.. 木神石最多用9块f21x1x2x3...x9f21x^1x^2x^3...x^9f21x1x2x3...x9 水神石最多用5块f31x1x2x3x4x5f31x^1x^2x^3x^4x^5f31x1x2x3x4x5 火神石的块数必须是 4 的倍数。f41x4x8x12...f41x^4x^{8}x^12...f41x4x8x12... 土神石最多用7块f51x1x2x3x4x5x6x7f51x^1x^2x^3x^4x^5x^6x^7f51x1x2x3x4x5x6x7 lzn大神 金神石的块数必须是 2 的倍数。f61x2x4...f61x^2x^{4}...f61x2x4... 木神石最多用1块f71x1f71x^1f71x1 水神石的块数必须是 8 的倍数f81x8x16x24....f81x^8x^{16}x^{24}....f81x8x16x24.... 火神石的块数必须是 10 的倍数。f91x10x20x30...f91x^{10}x^{20}x^{30}...f91x10x20x30... 土神石最多用3块f101x1x2x3f101x^1x^2x^3f101x1x2x3 答案就是Ff1∗f2∗f3∗f4∗f5∗f6∗f7∗f8∗f9∗f101(1−x)5Ff1*f2*f3*f4*f5*f6*f7*f8*f9*f10\frac{1}{(1-x)^5}Ff1∗f2∗f3∗f4∗f5∗f6∗f7∗f8∗f9∗f10(1−x)51 1(1−x)5∑i0∞C5i−1ixi∑i0∞C4iixi\frac{1}{(1-x)^5}\sum_{i0}^{∞}C_{5i-1}^{i}x^i\sum_{i0}^{∞}C_{4i}^{i}x^i(1−x)51i0∑∞C5i−1ixii0∑∞C4iixi 第n项的系数是C4nn(n4)(n3)(n2)(n1)4!C_{4n}^{n}\frac{(n4)(n3)(n2)(n1)}{4!}C4nn4!(n4)(n3)(n2)(n1) 因为n很大高精度也没法计算所以要用NTT加速一下 FFT/NTT如何实现高精度乘法的 都是到FFT可以处理多项式乘法那我们完全可以将一个高精度整数写成多项式形式。 对于每一个n的十进制数我们可以看作一个n-1次多项式A满足: A(x)a0a1∗101a2∗102....an−1∗10n−1A(x)a_{0}a_{1}*10^1a_{2}*10^2....a_{n-1}*10^{n-1}A(x)a0a1∗101a2∗102....an−1∗10n−1 对于两个大整数相乘我们就可以直接卷起来 关于FFT高精度乘法可以看这个【模板】A*B Problem升级版FFT快速傅里叶
代码
#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]);
}
