拯救世界
不能一次 DFT 所有序列再一起乘起来，会爆模数的。。。
正确做法是 DFT 后卷积一次，再 IDFT 一次，并进位，这样做三次。。。
在学校机房里看的。
比较适合作为生成函数的入门例题。
但是要写高精度，在学校里还是算了。
只讲一下思路。
根据题目所给的十个限制，我们其实可以列出十个生成函数：
$F_1(x)=\sum_{n\ge 0}x^{6n}=\dfrac{1}{1-x^6}$
$F_2(x)=\sum_{n=0}^9x^n=\dfrac{1-x^{10}}{1-x}$
$F_3(x)=\sum_{n=0}^5x^n=\dfrac{1-x^6}{1-x}$
$F_4(x)=\sum_{n\ge 0}x^{4n}=\dfrac{1}{1-x^4}$
$F_5(x)=\sum_{n=0}^7x^n=\dfrac{1-x^8}{1-x}$
$G_1(x)=\sum_{n\ge 0}x^{2n}=\dfrac{1}{1-x^2}$
$G_2(x)=\sum_{n=0}^1x^n=\dfrac{1-x^2}{1-x}$
$G_3(x)=\sum_{n\ge0}x^{8n}=\dfrac{1}{1-x^8}$
$G_4(x)=\sum_{n\ge 0}x^{10n}=\dfrac{1}{1-x^{10}}$
$G_5(x)=\sum_{n=0}^3x^n=\dfrac{1-x^4}{1-x}$
然后这个题的组合意义是什么？
用 $n$ 块且满足条件，显然把 10 个生成函数乘起来，对于次数为 $n$ 的项的系数就是答案（实质就是背包，不如说背包的实质其实是生成函数的卷积）。
不多做解释。
然后我们发现这个题最后乘下来的答案非常漂亮：
$H(x)=\dfrac{1}{(1-x)^5}$
这玩意是什么？
熟悉的人一眼就可以看出来，不做赘述。
$H(x)=\sum_{n\ge 0}\dbinom{n+4}{n}x^n$
第 $n$ 项的系数就是 $\dbinom{n+4}{n}=\dfrac{(n+1)(n+2)(n+3)(n+4)}{24}$，就是答案。
但是这个题要高精度。还要用 NTT。
时间复杂度 $O(\log n\log \log n)$。
代码：
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
| #include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
const ll N=4e6,mo=2281701377ll,G=3ll;
namespace Aeft{
inline ll Pow(ll b,ll p) {
ll res=1;while(p) {if(p&1) res=res*b%mo;b=b*b%mo;p>>=1;}return res;
}
}using Aeft::Pow;
const ll invG=Pow(G,mo-2);
ll n,m,invn;
ll a[N+5],b[N+5],c[N+5],d[N+5],rev[N+5];
char s[N+5];
inline void NTT(ll *f,bool op) {
for(ll i=0;i<n;i++) if(i<rev[i]) swap(f[i],f[rev[i]]);
for(ll p=2;p<=n;p<<=1) {
ll len=p>>1,tG=Pow(op?invG:G,(mo-1)/p);
for(ll k=0;k<n;k+=p) {
for(ll l=k,buf=1;l<k+len;l++,buf=buf*tG%mo) {
ll t=buf*f[len+l]%mo;
f[len+l]=f[l]-t;if(f[len+l]<0) f[len+l]+=mo;
f[l]=f[l]+t;if(f[l]>mo) f[l]-=mo;
}
}
}
if(op) {for(ll i=0;i<n;i++) f[i]=f[i]*invn%mo;}
}
inline void Plus_(ll *a,ll x,ll *b) {
static ll buf[N+5];
for(ll i=0;i<n;i++) buf[i]=a[i];buf[0]+=x;
for(ll i=0;i<n;i++) {buf[i+1]+=buf[i]/10ll;buf[i]%=10ll;}
for(ll i=0;i<n;i++) b[i]=buf[i];
}
inline void Div_(ll *a,ll x) {
for(ll i=n-1;i>=0;i--) {a[i-1]+=(a[i]%x)*10ll;a[i]/=x;}
}
inline void Karry(ll *a) {
for(ll i=0;i<n;i++) {a[i+1]+=a[i]/10ll;a[i]%=10ll;}
}
int main() {
scanf("%s",s);n=strlen(s);
for(ll i=0;i<n;i++) {if(s[i]>=48&&s[i]<=57) a[n-i-1]=s[i]-48ll;}
for(m=n*4,n=1;n<=m;n<<=1);invn=Pow(n,mo-2);
for(ll i=0;i<n;i++) rev[i]=(rev[i>>1]>>1)|((i&1)?(n>>1):0);
Plus_(a,1,a);Plus_(a,1,b);Plus_(b,1,c);Plus_(c,1,d);
NTT(a,0);NTT(b,0);
for(ll i=0;i<n;i++) {a[i]=a[i]*b[i]%mo;}
NTT(a,1);Karry(a);NTT(a,0);
NTT(c,0);
for(ll i=0;i<n;i++) {a[i]=a[i]*c[i]%mo;}
NTT(a,1);Karry(a);NTT(a,0);
NTT(d,0);
for(ll i=0;i<n;i++) {a[i]=a[i]*d[i]%mo;}
NTT(a,1);Karry(a);Div_(a,24ll);Karry(a);
ll flg=0;
for(ll i=n-1;i>=0;i--) {
if(a[i]==0&&!flg) continue;
else {flg=1;putchar(a[i]+48ll);}
}
return 0;
}
|