LOJ6671 EntropyIncreaser 与 Minecraft （生成函数）
题面
EntropyIncreaser 是组合计数大师。
EntropyIncreaser 很喜欢玩麦块。当然，EntropyIncreaser 拥有非同常人的超能力，他玩的是MOD版的 n 维麦块，换成数学语言也就是
Z
n
\mathbb{Z}^n
Zn 空间。他现在手里有一个特制的
T
N
T
\tt TNT
TNT方块：若将它放在
(
x
1
,
x
2
,
…
,
x
n
)
(x_1,x_2,…,x_n)
(x1,x2,…,xn)（注意
x
i
x_i
xi 可能为负数）处，它将拥有
∑
i
=
1
n
∣
x
i
∣
∑_{i=1}^n|x_i|
∑i=1n∣xi∣ 的威力值。EntropyIncreaser 只是想看看这种特制
T
N
T
\tt TNT
TNT的爆炸场面，他并不希望对其他东西造成太大的损害，所以这个
T
N
T
\tt TNT
TNT方块的威力值必须
⩽
p
⩽p
⩽p 。
EntropyIncreaser 想请你告诉他，一共有多少不同的位置放置
T
N
T
\tt TNT
TNT，使其满足他的要求。答案对
1
0
9
+
7
10^9+7
109+7 取模。
EntropyIncreaser 想了一秒就知道了答案。但他决定还是考考你。
Sample Input
3 5
Sample Output
231
题解
决定了！就用生成函数表达对这道题的尊敬！
其实这道题是可以当作生成函数入门训练题的。
我们对每一维坐标的绝对值进行考虑，若
∣
x
i
∣
≠
0
|x_i|\not=0
∣xi∣=0 那么有正负两种情况，贡献为 2，若为 0，则只有一种情况，贡献为 1 。
因此，单个维度贡献的生成函数就是
f
(
x
)
=
1
+
2
x
+
2
x
2
+
.
.
.
=
2
x
−
1
−
1
f(x)=1+2x+2x^2+...=\frac{2}{x-1}-1
f(x)=1+2x+2x2+...=x−12−1
继续推下去吧！ 我们可以得到总答案关于威力值的生成函数
F
(
x
)
=
f
n
(
x
)
=
(
2
x
−
1
−
1
)
n
F(x)=f^n(x)=\left(\frac{2}{x-1}-1\right)^n
F(x)=fn(x)=(x−12−1)n
用二项式定理：
F
(
x
)
=
(
2
x
−
1
−
1
)
n
=
∑
i
=
0
n
(
1
x
−
1
)
i
2
i
(
−
1
)
n
−
i
C
(
n
,
i
)
=
∑
i
=
0
n
(
1
+
x
+
x
2
+
.
.
.
)
i
2
i
(
−
1
)
n
−
i
C
(
n
,
i
)
F(x)=\left(\frac{2}{x-1}-1\right)^n=\sum_{i=0}^{n}\left(\frac{1}{x-1}\right)^i2^i(-1)^{n-i}C(n,i)\\ =\sum_{i=0}^{n}(1+x+x^2+...)^i2^i(-1)^{n-i}C(n,i)
F(x)=(x−12−1)n=i=0∑n(x−11)i2i(−1)n−iC(n,i)=i=0∑n(1+x+x2+...)i2i(−1)n−iC(n,i)
那么用隔板法可以得出，它的第
q
q
q 项就是
[
[
q
]
]
f
(
x
)
n
=
∑
i
=
0
n
C
(
q
+
i
−
1
,
i
−
1
)
2
i
(
−
1
)
n
−
i
C
(
n
,
i
)
[[q]]f(x)^n=\sum_{i=0}^{n}C(q+i-1,i-1)2^i(-1)^{n-i}C(n,i)
[[q]]f(x)n=i=0∑nC(q+i−1,i−1)2i(−1)n−iC(n,i)
我们要找的答案即
∑
q
=
0
p
[
[
q
]
]
f
(
x
)
n
=
∑
i
=
0
n
(
∑
q
=
0
p
C
(
q
+
i
−
1
,
i
−
1
)
)
2
i
(
−
1
)
n
−
i
C
(
n
,
i
)
=
∑
i
=
0
n
C
(
p
+
i
,
i
)
2
i
(
−
1
)
n
−
i
C
(
n
,
i
)
\sum_{q=0}^{p}[[q]]f(x)^n=\sum_{i=0}^{n}\left(\sum_{q=0}^{p}C(q+i-1,i-1)\right)2^i(-1)^{n-i}C(n,i)\\ =\sum_{i=0}^{n}C(p+i,i)2^i(-1)^{n-i}C(n,i)
q=0∑p[[q]]f(x)n=i=0∑n(q=0∑pC(q+i−1,i−1))2i(−1)n−iC(n,i)=i=0∑nC(p+i,i)2i(−1)n−iC(n,i)
成了！接下来只需要预处理阶乘求组合数，时间复杂度
O
(
n
)
O(n)
O(n) 。
CODE
#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 3000005
#define ENDL putchar('\n')
#define LL long long
#define DB double
#define lowbit(x) ((-x) & (x))
LL read() {
LL f = 1,x = 0;char s = getchar();
while(s < '0' || s > '9') {if(s=='-')f = -f;s = getchar();}
while(s >= '0' && s <= '9') {x=x*10+(s-'0');s = getchar();}
return f * x;
}
const int MOD = 1000000007;
int n,m,i,j,s,o,k;
int fac[MAXN],inv[MAXN],invf[MAXN];
int qkpow(int a,int b) {
int res = 1;
while(b > 0) {
if(b & 1) res = res *1ll* a % MOD;
a = a *1ll* a % MOD; b >>= 1;
}return res;
}
int C(int n,int m) {
if(m < 0 || m > n) return 0;
return fac[n] *1ll* invf[n-m] % MOD *1ll* invf[m] % MOD;
}
int main() {
fac[0]=fac[1]=inv[0]=inv[1]=invf[0]=invf[1]=1;
for(int i = 2;i <= 3000000;i ++) {
fac[i] = fac[i-1]*1ll*i % MOD;
inv[i] = (MOD-inv[MOD%i]) *1ll* (MOD/i) % MOD;
invf[i] = invf[i-1] *1ll* inv[i] % MOD;
}
n = read();m = read();
int ans = 0,po2 = 1;
for(int i = 0;i <= n;i ++) {
(ans += C(m+i,i)*1ll*po2 % MOD * (((n-i)&1) ? (MOD-1ll):1ll) % MOD *1ll* C(n,i) % MOD) %= MOD;
(po2 += po2) %= MOD;
}
printf("%d\n",ans);
return 0;
}
最新文章
- UI第十五节——UIWebView
- [译]Exploring Angular 1.3: Binding to Directive Controllers
- C++用PostMessage模拟按钮点击
- 网络编程-socket
- 关于JavaScript中apply与call的用法意义及区别
- Ubuntu 开启 Crontab 计划任务日志
- linux服务器监控流量sh脚本
- 深入了解VSTS的Unit Test测试属性
- undefined reference to `png_set_longjmp_fn'
- java后台获取国际化资源文件
- 如何找到w3wp与w3svc的对应关系
- lldpd启动脚本分析
- 对象Equals相等性比较的通用实现
- MVC MVC+EF快速搭建
- MySQL 字符串截取SUBSTRING()函数
- Linux Ubuntu 16.04 初次安装使用总结zzz
- git常用命令总结--廖雪峰老师Git教程命令总结
- ES7 and ES8 特性
- UVA12558-Efyptian Fractions(HARD version)(迭代加深搜索)
- 「Splay」区间翻转