「洛谷P2000」拯救世界

发表于 | 分类于 | | 浏览量： 次

kkk牛逼！

传送门

洛谷P2000

题解

生成函数裸题。

依次来看召唤每一位大神所需的每种石头的情况：

  • 金神石的块数必须是6的倍数：$1+x^6+x^{12}+\dots=\frac{1}{1-x^6}$

  • 木神石最多用9块：$1+x+x^2+\dots+x^9=\frac{1-x^{10}}{1-x}$

  • 水神石最多用5块：$1+x+x^2+\dots+x^5=\frac{1-x^6}{1-x}$

  • 火神石的块数必须是4的倍数：$1+x^4+x^8+\dots=\frac{1}{1-x^4}$

  • 土神石最多用7块：$1+x+x^2+\dots+x^7=\frac{1-x^8}{1-x}$

  • 金神石的块数必须是2的倍数：$1+x^2+x^4+\dots=\frac{1}{1-x^2}$

  • 木神石最多用1块：$1+x=\frac{1-x^2}{1-x}$

  • 水神石的块数必须是8的倍数：$1+x^8+x^{16}+\dots=\frac{1}{1-x^8}$

  • 火神石的块数必须是10的倍数：$1+x^{10}+x^{20}+\dots=\frac{1}{1-x^{10}}$

  • 土神石最多用3块：$1+x+x^2+x^3=\frac{1-x^4}{1-x}$

然后把它们全都乘起来，就有：

然后再把这个式子展开，就是：

答案就是上面这个多项式$x^n$项前面的系数。

通过隔板法可以求出答案为$\tbinom{n+5-1}{5-1}=\frac{n\cdot (n+1) \cdot(n+2)\cdot(n+3)}{24}$。

由于数据范围很大，所以上NTT来优化高精度乘法即可。

代码

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
115
116
117
118
119
120
121
122
123
124
125
126
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int TT=998244353;
int r[263000];char n[100005];
inline int read()
{
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
	return ret*f;
}
inline int QP(int a,int b)
{
	int ret=1,w=a;
	while(b)
	{
		if(b&1) ret=(LL)ret*w%TT;
		w=(LL)w*w%TT;b>>=1;
	}
	return ret;
}
inline void NTT(int* A,int limit,int type)
{
	for(int i=0;i<limit;i++)
		if(i<r[i])
			swap(A[i],A[r[i]]);
	for(int mid=1;mid<limit;mid<<=1)
	{
		int gn=QP(3,(TT-1)/(mid<<1));
		if(type<0) gn=QP(gn,TT-2);
		for(int j=0;j<limit;j+=mid<<1)
		{
			int g=1;
			for(int k=0;k<mid;k++,g=(LL)g*gn%TT)
			{
				int x=A[j+k],y=(LL)g*A[j+k+mid]%TT;
				A[j+k]=(x+y)%TT;
				A[j+k+mid]=(x-y+TT)%TT;
			}
		}
	}
	if(type<0)
	{
		int inv=QP(limit,TT-2);
		for(int i=0;i<=limit;i++) A[i]=(LL)A[i]*inv%TT;
	}
}
struct BigInteger
{
	int len,a[263000];
	BigInteger(){len=0;memset(a,0,sizeof(a));}
	BigInteger(char* S)
	{
		len=0;memset(a,0,sizeof(a));
		int n=strlen(S+1);
		reverse(S+1,S+1+n);
		len=(n+1)/2;
		for(int i=1;i<=n;i++) S[i]-='0';
		for(int i=1;i<=len;i++)
			a[i]=S[i*2-1]+S[i*2]*10;
	}
	BigInteger operator * (BigInteger b)
	{
		BigInteger a=*this,c;
		c.len=a.len+b.len;
		int limit=1,l=0;
		while(limit<=c.len){limit<<=1;l++;}
		for(int i=0;i<limit;i++)
			r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
		NTT(a.a+1,limit,1);
		NTT(b.a+1,limit,1);
		for(int i=1;i<=limit;i++)
			c.a[i]=(LL)a.a[i]*b.a[i]%TT;
		NTT(c.a+1,limit,-1);
		for(int i=1;i<=c.len;i++)
		{
			c.a[i+1]+=c.a[i]/100;
			c.a[i]%=100;
		}
		if(!c.a[c.len]) c.len--;
		return c;
	}
	void operator /= (int b)
	{
		for(int i=len;i;i--)
		{
			a[i-1]+=(a[i]%b)*100;
			a[i]/=b;
		}
		a[0]=0;
		if(!a[len]) len--;
	}
	inline void Inc()
	{
		a[1]++;
		for(int i=1;i<=len;i++)
		{
			if(a[i]<100) break;
			a[i+1]+=a[i]/100;
			a[i]%=100;
		}
		if(a[len+1]) len++;
	}
	void Print()
	{
		printf("%d",a[len]);
		for(int i=len-1;i>0;i--)
			printf("%02d",a[i]);
		putchar('\n');
	}
}A,B,C,D,ans;
int main()
{
	scanf("%s",n+1);
	A=n;A.Inc();
	B=A;B.Inc();
	C=B;C.Inc();
	D=C;C.Inc();
	ans=A*B*C*D;
	ans/=24;
	ans.Print();
	return 0;
}