bzoj1856
这是一道无比涨姿势的题目
首先总结一下这种输入几个数的题目,
一般不是递推就是数学题
显然,这道题用递推是无法做到O(n)的复杂度的
那我们就考虑这是一道数学题了
我已开始纠结在正向思维了,正向求好像确实不容易;
某牛的报告点醒了我,我们设符合条件的序列为x,不符合的为y
则x+y=c(n+m,n);
现在我们只要求出y即可
然后弱渣的我又卡住了,
还是大牛的报告引用:我们不妨将0看做-1,那么对于一个不合法的序列,必然存在一个位置使得前缀和为-1,我们设这个最小的位置为k,即:a1+a2+……ak=-1,那么前缀和k-1为0,且ak=-1。接着,若我们将所有n+m个的这前k个数字取反,那么得到一个新的数列含有n+1个1和 m-1个-1,这个新的数列有C(n+m,n+1)种。不合法序列与新构造的这个序列是一一对应的关系。
太神了。怎么想到的orz
所以,ans=c(n+m,n)-c(n+m,n+1);
因为n>m, 所以c(m+n,n)-c(n+m,n+1);
(其实现在来看,这就是一个经典的卡特兰数的模型的变形)
由于是组合还需要取模,就要涉及到除法取模;
能回避除法取模的递推法(杨辉三角)复杂度肯定会TLE,
然后我又涨姿势了,
a/b ≡ac (mod p);
bc ≡1 (mod p) 我们把c叫做b的乘法逆元;
一个数a除以另一个数b同余于a乘以b的乘法逆元模p
怎么证呢?
我们把乘法逆元的式子变换一下得 bc=pk+1 k∈Z
则b=(pk+1)/c
则a/b=a*c*(pk+1)≡ac (mod p)
乘法逆元存在的充要条件是gcd(b,p)=1
由于p=20100403>n+m,且是一个质数
显然gcd(b,p)=1;
那么怎么求乘法逆元呢?
看到之前的变换式我们也不难想到,扩展欧几里得
这道题唯一让我欣慰的地方就是,扩展欧几里得写对了……
const mo=;
var ans:int64;
n,m,i:longint; procedure exgcd(a,b:int64;var x,y:int64);
var xx,yy:int64;
begin
if b= then
begin
x:=;
y:=;
end
else begin
exgcd(b,a mod b,x,y);
xx:=x;
yy:=y;
x:=yy;
y:=xx-a div b*yy;
end;
end; function re(a,p:int64):int64;
var x,y:int64;
begin
exgcd(a,p,x,y);
x:=(x+mo) mod mo;
exit(x);
end; function get(x:int64):int64;
var i:int64;
begin
i:=;
get:=;
while i<x do
begin
inc(i);
get:=get*i mod mo;
end;
end; function c(x,y:int64):int64;
var a,b,d:int64;
begin
a:=get(x);
b:=get(y);
d:=get(x-y);
c:=a*re(b,mo) mod mo*re(d,mo) mod mo;
end; begin
readln(n,m);
ans:=c(n+m,n)-c(n+m,n+);
ans:=(ans+mo) mod mo;
writeln(ans);
end.
最新文章
- HTTPS 原理解析(转)
- AX Dynamic 2012 tabletype:TempDB使用
- java.lang.UnsupportedClassVersionError
- FLASH CC 2015 CANVAS (六)如何像FLASH那样实现场景(多canvas)
- 通过ModuleImplAdvertisement向自定义服务传递参数
- 翻译:WebApi 认证--用户认证Oauth解析
- [Bhatia.Matrix Analysis.Solutions to Exercises and Problems]ExI.2.9
- CodeForces 670D Magic Powder
- filter和listener的生命周期
- 巨高兴,偶的文章 “如何在服务器上配置ODBC来访问本机DB2for Windows服务器”被推荐至CSDN博客首页
- 【pycharm】pycharm修改文件名快捷键
- 10-05 Java 内部类概述和讲解
- jmeter☞工作区介绍(三)
- Uva 11549 - Calculator Conundrum 找规律加map
- IOS开发之新浪微博OAuth2
- 【Android】6.0 第6章 对话框--本章示例主界面
- .net core RabbitMQ 消息队列
- 使用 redis 减少 秒杀库存 超卖思路
- 【Error】SSL InsecurePlatform error when using Requests package
- 解析XMl文档和字符串
热门文章
- YII千万级PV架构经验分享--理论篇
- ECSHOP添加购物车加图片飞入效果
- 快速搭建Web环境 Angularjs + Express3 + Bootstrap3
- what is the “handover” and ";soft handover"; in mobile communication system?
- 大学生IT博客大赛最技术50强与最生活10强文章
- 在这里总结一些iOS开发中的小技巧,能大大方便我们的开发,持续更新。
- 【无聊放个模板系列】BZOJ 3172 (AC自动机)
- Java经典书籍
- ANDROID_MARS学习笔记_S01_004dpi、dp(dip)及计算
- Qt: 自动调整到最合适的大小(不是很明白)