Dispwnl

Crazy Up

扩展Lucas略解

$a.$ 要求$C_{n}^{m}\%p$的值，如果$p$是质数，可以用$Lucas$定理$O(\log n)$解决但是如果$p$不是质数怎么做呢预处理阶乘然后O(1)出解这里就需要用到扩展$Lucas$定理了 $b.$ 可以把$p$拆成$p_1^{k_1}\times p_2^{k_2}\times …\times p_l^{k_l}$，其中$p_i$为质因数...

Posted by Dispwnl on February 13, 2019

[BZOJ4765]普通计算姬

题面 Description “奋战三星期，造台计算机”。小G响应号召，花了三小时造了台普通计算姬。普通计算姬比普通计算机要厉害一些。普通计算机能计算数列区间和，而普通计算姬能计算树中子树和。更具体地，小G的计算姬可以解决这么个问题：给定一棵n个节点的带权树，节点编号为1到n，以root为根，设sum[p]表示以点p为根的这棵子树中所有节点的权值和。计算姬支持下列两种操作: 1 给定两...

Posted by Dispwnl on February 13, 2019

[BZOJ3782]上学路线

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

Posted by Dispwnl on February 13, 2019

[BZOJ2142]礼物

题目 Description 一年一度的圣诞节快要来到了。每年的圣诞节小E都会收到许多礼物，当然他也会送出许多礼物。不同的人物在小E心目中的重要性不同，在小E心中分量越重的人，收到的礼物会越多。小E从商店中购买了n件礼物，打算送给m个人，其中送给第i个人礼物数量为wi。请你帮忙计算出送礼物的方案数（两个方案被认为是不同的，当且仅当存在某个人在这两种方案中收到的礼物不同）。由于方案数可...

Posted by Dispwnl on February 13, 2019

[SHOI2008]堵塞的交通

题目题目描述有一天，由于某种穿越现象作用，你来到了传说中的小人国。小人国的布局非常奇特，整个国家的交通系统可以被看成是一个$2$行$C$列的矩形网格，网格上的每个点代表一个城市，相邻的城市之间有一条道路，所以总共有$2C$个城市和$3C-2$条道路。小人国的交通状况非常槽糕。有的时候由于交通堵塞，两座城市之间的道路会变得不连通，直到拥堵解决，道路才会恢复畅通。初来咋到的你决心毛遂...

Posted by Dispwnl on February 12, 2019

[BZOJ2989]数列

题目 Description 给定一个长度为n的正整数数列a[i]。定义2个位置的graze值为两者位置差与数值差的和，即$graze(x,y)=\vert x-y\vert +\vert a[x]-a[y]\vert$。 2种操作（k都是正整数）： 1.Modify x k：将第x个数的值修改为k。 2.Query x k：询问有几个i满足graze(x,i)<=k。因...

Posted by Dispwnl on February 12, 2019

[SDOI2017]相关分析

[SDOI2017]相关分析题目描述 Frank对天文学非常感兴趣，他经常用望远镜看星星，同时记录下它们的信息，比如亮度、颜色等等，进而估算出星星的距离，半径等等。 Frank不仅喜欢观测，还喜欢分析观测到的数据。他经常分析两个参数之间（比如亮度和半径）是否存在某种关系。现在Frank要分析参数$X$与$Y$之间的关系。他有$n$组观测数据，第ii组观测数据记录了$x_i$和$y...

Posted by Dispwnl on January 27, 2019

[SDOI2014]向量集

题目题目描述维护一个向量集合，在线支持以下操作： “A x y $(\vert x\vert ，\vert y\vert \le 10^8)$”：加入向量(x，y); ” Q x y l r $(\vert x\vert，\vert y\vert \le 10^8，1 \le L \le R \le T)$，其中T为已经加入的向量个数)询问第L个到第R个加入的向量与向量(...

Posted by Dispwnl on January 23, 2019

[SDOI2013]保护出题人

题目题目描述出题人铭铭认为给SDOI2012出题太可怕了，因为总要被骂，于是他又给SDOI2013出题了。参加SDOI2012的小朋友们释放出大量的僵尸，企图攻击铭铭的家。而你作为SDOI2013的参赛者，你需要保护出题人铭铭。僵尸从唯一一条笔直道路接近，你们需要在铭铭的房门前放置植物攻击僵尸，避免僵尸碰到房子。第一关，一只血量为$a_1$点的墦尸从距离房子$x_1$米处...

Posted by Dispwnl on January 21, 2019

[HNOI2007]最小矩形覆盖

题目题目描述给定一些点的坐标，要求求能够覆盖所有点的最小面积的矩形，输出所求矩形的面积和四个顶点坐标输入输出格式输入格式：第一行为一个整数n（3<=n<=50000），从第2至第n+1行每行有两个浮点数，表示一个顶点的x和y坐标，不用科学计数法输出格式：第一行为一个浮点数，表示所求矩形的面积（精确到小数点后5位），接下来4行每行表示一个顶点坐标，要求第...

Posted by Dispwnl on January 21, 2019