题意:求$\sum_{i=1}^{k}C(n,i)\%(P=2333)$
肯定要先拆开,不然怎么做呢(大雾)
把$C(n,i)$用$lucas$分解一下
于是原式$=\sum_{i=1}^{k}C(n/P,k/P)*C(n\%P,k\%P)\%P$
发现介个$k/P$是可以用整除分块搞的
于是拆开各个分块
$=C(n/P,0)*\sum_{i=0}^{P-1}C(n\%P,i)$
$+C(n/P,1)*\sum_{i=0}^{P-1}C(n\%P,i)$
$+...$
$+C(n/P,k/P-1)*\sum_{i=0}^{P-1}C(n\%P,i)$
$+C(n/P,k/P)*\sum_{i=0}^{k\%P}C(n\%P,i)$(最后一块不一定是整块,单独取出)
发现前面都有个$\sum_{i=0}^{P-1}C(n\%P,i)$,把它提出来
$=\sum_{j=0}^{k/P-1}C(n/P,j)*\sum_{i=0}^{P-1}C(n\%P,i)+C(n/P,k/P)*\sum_{i=0}^{k\%P}C(n\%P,i)$
根据$f$数组的定义再套进去
$=f[n/P][k/P-1]*f[n\%P][P-1]+C(n/P,k/P)*f[k\%P][n\%P]$
先预处理下标$<P$的$f$数组和组合数$C$,再递归一下,$C(n/P,k/P)$用$Lucas$定理搞
end.
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
const int P=;
int t;ll n,k,c[P+][P+],f[P+][P+];
ll lucas(ll a,ll b){
if(a<b) return ;
if(a==b) return ;
return b?lucas(a/P,b/P)*c[a%P][b%P]%P:;
}
ll F(ll a,ll b){
if(b<) return ;
if(!a||!b) return ;
if(a<P&&b<P) return f[a][b];
ll r1=f[a%P][P-]*F(a/P,b/P-)%P;
ll r2=lucas(a/P,b/P)*f[a%P][b%P]%P;
return (r1+r2)%P;
}
int main(){
for(int i=;i<=P;++i){
c[i][]=c[i][i]=;
for(int j=;j<i;++j)
c[i][j]=(c[i-][j-]+c[i-][j])%P;
}
for(int i=;i<=P;++i){
f[i][]=;
for(int j=;j<=P;++j)//注意f[P][P]以内的都要处理到
f[i][j]=(f[i][j-]+c[i][j])%P;
}
scanf("%d",&t);
while(t--){
scanf("%lld%lld",&n,&k);
printf("%lld\n",F(n,k));
}return ;
}
bzoj4591 / P4345 [SHOI2015]超能粒子炮·改的更多相关文章
-
【BZOJ4591】[SHOI2015]超能粒子炮&#183;改 (卢卡斯定理)
[BZOJ4591][SHOI2015]超能粒子炮·改 (卢卡斯定理) 题面 BZOJ 洛谷 题解 感天动地!终于不是拓展卢卡斯了!我看到了一个模数,它是质数!!! 看着这个东西就感觉可以递归处理. ...
-
洛谷 P4345 [SHOI2015]超能粒子炮&#183;改 解题报告
P4345 [SHOI2015]超能粒子炮·改 题意 求\(\sum_{i=0}^k\binom{n}{i}\),\(T\)组数据 范围 \(T\le 10^5,n,j\le 10^{18}\) 设\ ...
-
【bzoj4591】[Shoi2015]超能粒子炮&#183;改 Lucas定理
题目描述 曾经发明了脑洞治疗仪&超能粒子炮的发明家SHTSC又公开了他的新发明:超能粒子炮·改--一种可以发射威力更加强大的粒子流的神秘装置.超能粒子炮·改相比超能粒子炮,在威力上有了本质的提 ...
-
loj 2038 / 洛谷 P4345 [SHOI2015] 超能粒子炮・改 题解
好玩的推式子 题目描述 曾经发明了脑洞治疗仪与超能粒子炮的发明家 SHTSC 又公开了他的新发明:超能粒子炮・改--一种可以发射威力更加强大的粒子流的神秘装置. 超能粒子炮・改相比超能粒子炮,在威力上 ...
-
P4345 [SHOI2015]超能粒子炮&#183;改 Lucas
\(\color{#0066ff}{ 题目描述 }\) 曾经发明了脑洞治疗仪与超能粒子炮的发明家 SHTSC 又公开了他的新发明:超能粒子炮・改--一种可以发射威力更加强大的粒子流的神秘装置. 超能粒 ...
-
[洛谷P4345][SHOI2015]超能粒子炮&#183;改
题目大意:给你$n,k$,求:$$\sum\limits_{i=0}^k\binom n i\pmod{2333}$$题解:令$p=2333,f(n,k)\equiv\sum\limits_{i=0} ...
-
P4345 [SHOI2015]超能粒子炮&#183;改
传送门 看到数据和模数大小就知道要上 lucas 了 然后开始愉快地推公式: 答案为 $\sum _{i=0}^kC_{n}^{i}\ (mod\ 2333)$ 设 $f [ i ] [ j ] = ...
-
【bzoj4591】[Shoi2015]超能粒子炮&#183;改
设S(n,k)=Σ C(n,i) i=0..k 根据lucas定理可以得到 S(n,k) mod p = [ S(n/p,k/p-1)*S(n mod p,p-1)+C(n/p,k/p)*S(n mo ...
-
Bzoj 4591: [Shoi2015]超能粒子炮&#183;改 数论,Lucas定理,排列组合
4591: [Shoi2015]超能粒子炮·改 Time Limit: 10 Sec Memory Limit: 256 MBSubmit: 178 Solved: 70[Submit][Stat ...
随机推荐
-
selenium:org.openqa.selenium.WebDriverException: f.QueryInterface is not a function
今天用selenium2遇到问题 org.openqa.selenium.WebDriverException: f.QueryInterface is not a function 查了好久最后终于 ...
-
谈谈java开发
1.不要让未来的决策阻止你现在前进的方向 一步步列出每个步骤,那么对于现在应该专注于做什么,就一目了然了.你也不会浪费 时间去担心应该以后操心的事情. 2.不要让自信诱骗你忘事 当你去学习一个新概 ...
-
asp.net登录时验证码的制作与验证
1.新建一个页面,ImageCode.aspx 2.在Page_Load中添加如下代码 string tmp = RndNum(4); HttpCookie a = new HttpCookie(&q ...
-
简单方便地扩充Python的系统路径
参考: http://www.elias.cn/Python/PythonPath?from=Develop.PythonPath http://v2in.com/pth-file-usage-in- ...
-
Win7_Wifi热点
1. 怎样在Win7系统建立并开启Wifi热点 http://jingyan.baidu.com/article/48a42057a03cf7a9242504d0.html 2.
-
64位win2003 IIS6运行32位的.NET程序
做web服务迁移,从32位win2003迁移到64位win2003,数据库是32位Oracle在另外一台服务器上. 迁移之后数据库各种连不上,oracle的客户端32位的装完装64位的,odp.net ...
-
js本地预览图片
废话不说 直接上代码 <script type="text/javascript" src="http://code.jquery.com/jquery-late ...
-
GCTF2017部分write up
Misc stage1 拿到题看到是一张图片隐写 用神器Stegsolve看看发现左上角藏着一张二维码 截下来,不能直接扫,需要反色处理一下 扫出来是一串十六进制 看头几个十六进制数发现是pyc文件 ...
-
Bash的数组
Bash 2.x提供了创建一维数组的能力. 有多种方法创建,用内建命令declare -a或直接数组元素赋值. 向数组赋值时,如果不指定下标,下标自动从0开始,每次增加1. 数组的尺寸没有限制,下标也 ...
-
ajax和跨域
一.简介 ajax是什么? AJAX(Asynchronous JavaScript and XML) 是一种在无需重新加载整个网页的情况下,能够更新部分网页的技术. AJAX, (异步的JavaSc ...