hnoi2008专题

bzoj1004[HNOI2008] Cards

题目链接：bzoj1004 题目大意：有3种颜色:红色,蓝色,绿色。要求染出Sr张红色,Sb张蓝色,Sg张绿色。M种不同的洗牌法,这里问有多少种不同的染色方案。两种染色方法相同当且仅当其中一种可以通过任意的洗牌法(即可以使用多种洗牌法,而每种方法可以使用多次)洗成另一种。要求出答案除以P的余数(P为质数)。100%数据满足 Max{Sr,Sb,Sg}≤20；m≤60,m+1<p<100 输入数据

1008: [HNOI2008]越狱（排列组合）

Description 　　监狱有连续编号为1…N的N个房间，每个房间关押一个犯人，有M种宗教，每个犯人可能信仰其中一种。如果相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱 Input 　　输入两个整数M，N.1<=M<=108,1<=N<=1012 Output 　　可能越狱的状态数，模100003取余 Sample Input 2 3 Sample Output

BZOJ1010: [HNOI2008]玩具装箱toy（斜率优化dp）

Description 　　P教授要去看奥运，但是他舍不下他的玩具，于是他决定把所有的玩具运到北京。他使用自己的压缩器进行压缩，其可以将任意物品变成一堆，再放到一种特殊的一维容器中。P教授有编号为1…N的N件玩具，第i件玩具经过压缩后变成一维长度为Ci.为了方便整理，P教授要求在一个一维容器中的玩具编号是连续的。同时如果一个一维容器中有多个玩具，那么两件玩具之间要加入一个单位长度的填充物，形

BZOJ 1008 [HNOI2008]越狱 (组合数简单公式)

[HNOI2008]越狱 Time Limit: 1 Sec Memory Limit: 162 MB Submit: 5714 Solved: 2439 [ Submit][ Status][ Discuss] Description 监狱有连续编号为1...N的N个房间，每个房间关押一个犯人，有M种宗教，每个犯人可能信仰其中一种。如果相邻房间的犯人的宗教相同，就

越狱hnoi2008

题目描述 Description 监狱有连续编号为1…N的N个房间，每个房间关押一个犯人，有M种宗教，每个犯人可能信仰其中一种。如果相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱输入描述 Input Description 输入两个整数M，N.1<=M<=10^8,1<=N<=10^12 输出描述 Output Description 可能越狱的状态数，模1000

洛谷 P3197 [HNOI2008]越狱

来来来，日常水一篇（滑稽）题目描述监狱有连续编号为1…N的N个房间，每个房间关押一个犯人，有M种宗教，每个犯人可能信仰其中一种。如果相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱输入输出格式输入格式：输入两个整数M，N.1<=M<=10^8,1<=N<=10^12 输出格式：可能越狱的状态数，模100003取余输入输出样例输入样例#1：

[bzoj1010]：[HNOI2008]玩具装箱toy

传送门 HNOI2008 All Clear! 这个题貌似有三种做法。。首先可以斜率优化dp 然后可以证（da）明（biao）发现决策单调性之后根据这个结论有两个做法： 1.每次算出来一个dp[i]，就往后二分查找影响区间的变化点x，然后将[x,n]涂上i 然后按照这样递推算出来就好了，涂色用线段树， O(nlog2n) O(nlog^2n) 2.用单调队列和二分查找，具体可以

[bzoj1007]：[HNOI2008]水平可见直线（单调栈）

传送门姑且算是计算几何第一题吧。。首先，最后的图形一定是一个凸包形状的东西。所以，我们按照k递增为第一关键字，b递减为第二关键字，排个序。然后我们就可以维护一个单调栈，处理结果了。方法：我们设当前直线与栈顶直线的交点为x1，栈顶直线与栈顶第二条直线的交点为x2 如果x1<=x2，那么弹出栈顶；否则将当前直线压入栈中。原理可以看这个图，直到看懂为止。懂了的话，那

[bzoj1005]：[HNOI2008]明明的烦恼（prufer序列+质因数分解+高精乘）

传送门首先，原来我写过这个题，然而我用的别人的高精板子，然后就没有然后了。这个故事告诉我们，千万不要用别人的板子。好，我们开始。首先大家都知道prufer序列这个东西吧（没看过的可以去Matrix67那里听课：http://www.matrix67.com/blog/archives/682）看完了之后，这个题就是组合数学了。首先我们声明一些变量： n->节点

Prufer序列+高精度--bzoj1005: [HNOI2008]明明的烦恼

传送门话说这还是我第一道关于 p r u f e r prufer prufer序列的题。。。长度 n − 2 n-2 n−2的 p r u f e r prufer prufer序列可以唯一表示一棵 n n n个节点的树，而且每个节点在序列中出现次数都是 d [ i ] − 1 d[i]-1 d[i]−1 所以如果给定每个点的 d [ i ] d[i] d[i]，所有不同的树就是 (

【HNOI2008】bzoj1009 GT考试

Description 　　阿申准备报名参加GT考试，准考证号为N位数X1X2….Xn(0<=Xi<=9),他不希望准考证号上出现不吉利的数字。他的不吉利数学A1A2…Am(0<=Ai<=9)有M位，不出现是指X1X2…Xn中没有恰好一段等于A1A2…Am. A1和X1可以为 0 Input 　　第一行输入N,M,K.接下来一行输入M位的数。 N<=10^9,M<=20,K<=1000 O

【HNOI2008】bzoj1004 Cards

Description 　　小春现在很清闲,面对书桌上的N张牌,他决定给每张染色,目前小春只有3种颜色:红色,蓝色,绿色.他询问Sun有多少种染色方案,Sun很快就给出了答案.进一步,小春要求染出Sr张红色,Sb张蓝色,Sg张绝色.他又询问有多少种方案,Sun想了一下,又给出了正确答案. 最后小春发明了M种不同的洗牌法,这里他又问Sun有多少种不同的染色方案. 两种染色方法相同当且仅当

[bzoj 1011] [HNOI2008]遥远的行星：近似算法（一种正确性显然的非乱搞的科学做法）

题意：给N个数Mi（1≤N≤10^5, 0≤Mi≤10^7）和实数a（0.01<a≤0.35），对每个1≤i≤N求 ∑aij=1MiMji−j \sum_{j=1}^{ai}\frac {M_iM_j} {i-j}，相对误差不超过5%即可。这种形式的和式不太好处理，也许用到某种奇妙的求和顺序、递推关系、或者数据结构？扫了一眼题解，黄学长的代码很短同时表示“这种题到底是什么鬼”，有题解标题为“根

[bzoj 1008] [HNOI2008]越狱：排列组合，快速幂

题意：N个数，每个数有M种取值，问有多少状态存在相等的相邻两项。(1<=M<=10^8,1<=N<=10^12) 正难则反。第一次提交WA了……又是int乘法溢出。我以为模数很小……实际上超过10^4就要警惕了。 #include <cstdio>using namespace std;typedef long long ll;const int MOD = 100003;ll f