Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom5月前

05/17
20:58
一般动规与递推 容斥原理 数学其他 组合数/lucas

[bzoj 4767] 两双手

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

老W是个棋艺高超的棋手,他最喜欢的棋子是马,更具体地,他更加喜欢马所行走的方式。老W下棋时觉得无聊,便决定加强马所行走的方式,更具体地,他有两双手,其中一双手能让马从(u,v)移动到(u+Ax,v+Ay)而另一双手能让马从(u,v)移动到(u+Bx,v+By)。小W看见老W的下棋方式,觉得非常有趣,他开始思考一个问题:假设棋盘是个无限大的二维平面,一开始马在原点(0,0)上,若用老W的两种方式进行移动,他有多少种不同的移动方法到达点(Ex,Ey)呢?两种移动方法不同当且仅当移动步数不同或某一步所到达的点不同。老W听了这个问题,觉得还不够有趣,他在平面上又设立了n个禁止点,表示马不能走到这些点上,现在他们想知道,这种情况下马有多少种不同的移动方法呢?答案数可能很大,你只要告诉他们答案模(10^9+7)的值就行。

Read More →

[bzoj 4767] 两双手

@krydom5月前

05/17
20:54
一般动规与递推 中国剩余定理 容斥原理 组合数/lucas

[bzoj 3782] 上学路线

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

 小C所在的城市的道路构成了一个方形网格,它的西南角为(0,0),东北角为(N,M)。小C家住在西南角,学校在东北角。现在有T个路口进行施工,小C不能通过这些路口。小C喜欢走最短的路径到达目的地,因此他每天上学时都只会向东或北行走;而小C又喜欢走不同的路径,因此他问你按照他走最短路径的规则,他可以选择的不同的上学路线有多少条。由于答案可能很大,所以小C只需要让你求出路径数mod P的值。

Read More →

[bzoj 3782] 上学路线

@krydom7月前

04/5
15:16
组合数/lucas 高精度

[bzoj 4807] 車

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

众所周知,車是中国象棋中最厉害的一子之一,它能吃到同一行或同一列中的其他棋子。車跟車显然不能在一起打起来,于是rly一天又借来了许多许多的車在棋盘上摆了起来……他想知道,在N×M的矩形方格中摆最多个数的車使其互不吃到的情况下方案数有几种。但是,由于上次摆炮摆得实在太累,他为了偷懒,打算增加一个条件:对于任何一个車A,如果有其他一个車B在它的上面(車B行号小于車A),那么車A必须在車B的右边(車A列号大于車B)。
棋子都是相同的。

Read More →

[bzoj 4807] 車

@krydom1年前

09/11
12:38
快速幂 组合数/lucas

[bzoj 4487] [Jsoi2015]染色问题

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

 棋盘是一个n×m的矩形,分成n行m列共n*m个小方格。现在萌萌和南南有C种不同颜色的颜料,他们希望把棋盘用这些颜料染色,并满足以下规定:
1.  棋盘的每一个小方格既可以染色(染成C种颜色中的一种) ,也可以不染色。
2.  棋盘的每一行至少有一个小方格被染色。
3.  棋盘的每一列至少有一个小方格被染色。
4.  种颜色都在棋盘上出现至少一次。
以下是一些将3×3棋盘染成C = 3种颜色(红、黄、蓝)的例子:
aa1
请你求出满足要求的不同的染色方案总数。只要存在一个位置的颜色不同,
即认为两个染色方案是不同的

Read More →

[bzoj 4487] [Jsoi2015]染色问题

@krydom1年前

08/12
09:45
组合数/lucas

[bzoj 4517] [Sdoi2016]排列计数

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

求有多少种长度为 n 的序列 A,满足以下条件:
1 ~ n 这 n 个数在序列中各出现了一次
若第 i 个数 A[i] 的值为 i,则称 i 是稳定的。序列恰好有 m 个数是稳定的
满足条件的序列可能很多,序列数对 10^9+7 取模。

Read More →

[bzoj 4517] [Sdoi2016]排列计数

@krydom2年前

01/2
15:51
组合数/lucas

[bzoj 2982] combination

00:00/00:00

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

 LMZ有n个不同的基友,他每天晚上要选m个进行[河蟹],而且要求每天晚上的选择都不一样。那么LMZ能够持续多少个这样的夜晚呢?当然,LMZ的一年有10007天,所以他想知道答案mod 10007的值。(1<=m<=n<=200,000,000)

Read More →

[bzoj 2982] combination

@krydom2年前

12/31
20:38
组合数/lucas

Round Numbers [poj 3252]

00:00/00:00

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

输入两个十进制正整数a和b,求闭区间[a,b]内有多少个Round Number?

所谓的Round Number就是把一个十进制数转换为一个无符号二进制数,若该二进制数中0的个数大于等于1的个数,则它就是一个Round Number。

注意,转换所得的二进制数,最高位必然是1,最高位的前面不允许有0。

Read More →

Round Numbers [poj 3252]