题目相关
题目背景：
公元 2000 年，根据预言家诺查丹玛斯的预言，世界就要毁灭了！！！
题目描述：
为了拯救世界，小 a 和 uim 决定召唤出 kkksc03 大神和 lzn 大神。根据古籍记载，召唤出任何一位大神，都需要使用金木水火土五种五行神石来摆一个特定的大阵。而在古籍中，记载是这样的：
kkksc03 大神召唤方法：
- 金神石的块数必须是 $6$ 的倍数。
- 木神石最多用 $9$ 块。
- 水神石最多用 $5$ 块。
- 火神石的块数必须是 $4$ 的倍数。
- 土神石最多用 $7$ 块。
lzn 大神召唤方法:
- 金神石的块数必须是 $2$ 的倍数。
- 木神石最多用 $1$ 块。
- 水神石的块数必须是 $8$ 的倍数。
- 火神石的块数必须是 $10$ 的倍数。
- 土神石最多用 $3$ 块。
现在是公元 1999 年 12 月 31 日，小 a 和 uim 从 00:00:00 开始找，一直找到 23:00:00，终于，还是没找到神石。不过，他们在回到家后在自家地窖里发现了一些奇怪的东西，一查古籍，哎呦妈呀，怎么不早点来呢？这里有一些混沌之石，可以通过敲击而衰变成五行神石。于是，他们拼命地敲，终于敲出了 $n$ 块神石，在 23:59:59 完成了两座大阵。然而，kkksc03 大神和 lzn 大神确实出现了，但是由于能量不够，无法发挥神力。只有把所有用 $n$ 块神石可能摆出的大阵都摆出来，才能给他们充满能量。这下小 a 和 uim 傻了眼了，赶快联系上了你，让你帮忙算一下，一共有多少种大阵。
输入输出格式：
输入格式：
输入一个正整数 $n$。
输出格式：
输出用 $n$ 块混沌之石能摆出的大阵的种数。
输入输出样例：
数据范围：
$10^{100000}≤n<10^{100001}$
博主乱搞
蒟蒻解析：
拯救世界？搭嘎,口头哇路题目太难告辞。
看到这么一堆条件求组合数大概就只能来生成函数了。我们把每一条列一下：
\begin{align}
1+x^6+x^{12}+\cdots&=\frac{1}{1-x^6}\\
1+x+x^2+\cdots+x^{9}&=\frac{1-x^{10}}{1-x}\\
1+x+x^2+\cdots+x^{5}&=\frac{1-x^{6}}{1-x}\\
1+x^4+x^{8}+\cdots&=\frac{1}{1-x^4}\\
1+x+x^{2}+\cdots+x^7&=\frac{1-x^8}{1-x}\\
1+x^2+x^{4}+\cdots&=\frac{1}{1-x^2}\\
1+x&=1+x\\
1+x^8+x^{16}+\cdots&=\frac{1}{1-x^8}\\
1+x^{10}+x^{20}+\cdots&=\frac{1}{1-x^{10}}\\
1+x+x^2+x^3&=\frac{1-x^4}{1-x}\\
\end{align}
然后我们把上面这些式子乘起来，得到：
$$\frac{(1-x^{10})(1-x^6)(1-x^8)(1+x)(1-x^4)}{(1-x^6)(1-x)(1-x)(1-x^4)(1-x)(1-x^2)(1-x^8)(1-x^{10})(1-x)}=\frac{1}{(1-x)^5}$$
然后因为 $\frac{1}{(1-x)^k}=\sum\limits_{i}^{\infty}{C_{i+k-1}^{k-1}{x^i}}$ ，得到答案就是 $C_{n+4}^{4}=(n+1)(n+2)(n+3)(n+4)/24$ 。
然后这就是一个简单的高精度乘法与除法了。
我们发现普通的高精度乘法太慢了，所以我们还要用 NTT 或 FFT 来优化一下乘法才能过（太毒瘤了）。然后本题就解决了。
蒟蒻代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
| #include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define ll long long
#define il inline
#define mod 998244353
#define g 3
ll ksm(ll x,ll k){
ll res=1;
while (k){
if (k&1) res=(res*x)%mod;
x=(x*x)%mod; k>>=1;
}
return res;
}
const int maxn=1000010;
char sa[maxn]; int n;
char sb[maxn]; int m;
ll aa[maxn*4],bb[maxn*4];
int rev[maxn*4];
int lim,limits;
ll origin[maxn*4];
void ntt(ll *a,int len,int inv){
for (int i=0;i<len;++i){
if (i<rev[i]) swap(a[i],a[rev[i]]);
}
for (int mid=1;mid<len;mid<<=1){
ll tmp=ksm((inv==1)?g:ksm(g,mod-2),(mod-1)/(mid*2));
for (int i=0;i<len;i+=mid<<1){
ll omega=1;
for (int j=0;j<mid;++j,omega=omega*tmp%mod){
ll x=a[i+j],y=omega*a[i+j+mid]%mod;
a[i+j]=(x+y)%mod; a[i+j+mid]=(x-y+mod)%mod;
}
}
}
}
void mul(){
limits=1; lim=0;
while (limits<=m+n) limits<<=1,++lim;
memset(rev,0,sizeof(rev));
for (int i=0;i<limits;++i){
rev[i]=(rev[i>>1]>>1)|((i&1)<<(lim-1));
}
ntt(aa,limits,1); ntt(bb,limits,1);
for (int i=0;i<=limits;++i){
aa[i]=(aa[i]*bb[i])%mod;
}
ntt(aa,limits,-1);
ll inv=ksm(limits,mod-2);
for (int i=0;i<=n+m;++i){
aa[i]=aa[i]*inv%mod;
}
int maxlen=n+m;
while (!aa[maxlen]) --maxlen;
for (int i=0;i<=maxlen;++i){
aa[i+1]+=aa[i]/10;
aa[i]%=10;
}
if (aa[maxlen+1]) maxlen++;
m=maxlen;
}
int main(){
scanf("%s",sa);
int lenn=strlen(sa);
for (int i=0;i<lenn;++i){
origin[lenn-i-1]=sa[i]-'0';
}
lenn--;
for (int i=0;i<=lenn;++i) aa[i]=origin[i];
aa[0]+=1; m=lenn;
for (int i=0;i<=m;++i){
aa[i+1]+=aa[i]/10; aa[i]%=10;
}
if (aa[m+1]) ++m;
for (int i=0;i<=lenn;++i) bb[i]=origin[i];
bb[0]+=2; n=lenn;
for (int i=0;i<=n;++i){
bb[i+1]+=bb[i]/10; bb[i]%=10;
}
if (bb[n+1]) ++n;
mul();
memset(bb,0,sizeof(bb));
for (int i=0;i<=lenn;++i) bb[i]=origin[i];
bb[0]+=3; n=lenn;
for (int i=0;i<=n;++i){
bb[i+1]+=bb[i]/10; bb[i]%=10;
}
if (bb[n+1]) ++n;
mul();
memset(bb,0,sizeof(bb));
for (int i=0;i<=lenn;++i) bb[i]=origin[i];
bb[0]+=4; n=lenn;
for (int i=0;i<=n;++i){
bb[i+1]+=bb[i]/10; bb[i]%=10;
}
if (bb[n+1]) ++n;
mul();
for (int i=m;i>=0;--i){
if (i>0) aa[i-1]+=(aa[i]%24)*10;
aa[i]/=24;
}
while (aa[m]==0) m--;
for (int i=m;i>=0;--i) printf("%lld",aa[i]);
return 0;
}
|
