【BZOJ 3028】食物

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3028
神犇题解:http://blog.csdn.net/regina8023/article/details/44995939

解题报告

这题看上去一眼不可做啊!第一反应:还要写高精?
但想一想似乎物品非常妙妙:

我们强行将其分为四组:{汉堡,可乐} {蜜桃多,土豆片炒肉} {包子,鸡块} {鸡腿,面包}
我们发现每一组都能凑出每一个自然数,且方案唯一
于是问题变为将$n$个球分为$4$组,每组可以为空的方案数

这是插板法的经典问题,于是搞一个组合数就可以了
什么组合数太大?
我们注意到答案实际是$\frac{n^{\bar 3}}{6}$,所以我们取个模就可以了

当然你也可以强行搞生成函数然后泰勒展开得到一样的结论
但我不会泰勒展开 QwQ

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int MOD = 10007;
const int REV = 1668;

int main() {
	int n=0; char pat[600]; cin>>pat+1;
	for (int i=1;i<=strlen(pat+1);i++)
		n = (n * 10 + pat[i] - '0') % MOD;
	cout<<n*(n+1ll)*(n+2)*REV%MOD;
	return 0;
}

【BZOJ 4115】[WF2015] Tile Cutting

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4115
神犇题解:http://www.cnblogs.com/clrs97/p/4779789.html
英文题面:https://online.acmicpc.org/problems/tiles
英文题解:http://blog.brucemerry.org.za/2015/05/analysis-of-icpc-2015-world-finals.html

解题报告

卧槽,这样乱找题做吃枣药丸啊!
一言不合就FFT+生成函数,FFT还好,生成函数完全不会啊 QwQ
只能先弃坑了,以后慢慢来填 _ (:з」∠) _

—– UPD 2017.1.22 —–
最近听集训队神犇讲了生成函数
然而并没有学会 QwQ
不过做这个题还是足够啦!

考虑最终的切法长这样:

那么平行四边形的面积就是 $ad+bc$
设面积为$i$的答案为 $ans(i)$,$x$ 的约数个数为 $d(x)$
那么就可以得到: $ans(i) = \sum {[ad + bc = i]} = \sum {[x + y = i]} \cdot d(x) \cdot d(y)$
然后看一眼就能发现这货是个卷积的形式,于是搞一波FFT就可以啦!