Deep_Kevin的娱乐空间

专题测试 第一题：整数的 lqp 拆分整数拆分是个很有趣的问题。给你一个正整数 N，对于 N 的一个整数拆分就是满足任意 m>0, a1,a2,a3…am>0，且 a1+a2+a3+…+am=N 的一个有序集合。通过长时间的研究我们 发现了计算对于 N 的整数拆分的总数有一个很简单的递推式，但是因为这个递推式实在太 简单了，如果出这样的题目，大家会对比赛毫无兴趣的。 然后...

正题      这个游戏整整玩了我三天。      题意就是要你求。还要你求。那我们暂且先不理会nm这玩意儿。      利用二项式定理，化简一下可以得到：            看到了喜闻乐见的卷积形式，但是我们难以求出可用于卷积的两个数组。      这个其实可以用生成函数来解决，在我的博客中就以这个模型来介绍生成函数，大家可以看看。      所以我们最后再用这两...

正题      [ZJOI2010]排列计数      首先，我们先转化问题，要求，就相当于要求。      那么这就像当与一棵n个节点的完全二叉树，那么我们统计一下每棵子树的大小，然后下去更新算一下组合数就可以了。#include<cstdio>#include<cstdlib>#include<cstring>#include<...

正题      [HAOI2010]计数      “给您一个字符串，要你求这个字符串在他的全排列中排第几”，题面很明显可以转化为这一个问题。      那么对于每一位，我们就可以计算当前这位小于它的所有全排列。      具体做法就是先把枚举到的j先删除，然后拿剩下的数进行全排列。具体的全排列公式是            但是很明显会爆long long，所以不想打高精度...

正题      第四题：[SDOI2009]虔诚的墓主人      这个东西，根据题意我们可以知道当前点的虔诚度为C(up,k)*C(down,k)*C(left,k)*C(right,k);      这里的四个英文单词，分别表示上面的常青树个数，下面的常青树个数，左边的常青树个数和右边的。      我们现在要做的事情就是如何维护这四个值。      对于30分做法，很明显就是用四个数组来存储...