bzoj4591 / P4345 [SHOI2015]超能粒子炮·改

时间:2022-09-26 17:03:42

P4345 [SHOI2015]超能粒子炮·改

题意:求$\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]超能粒子炮·改的更多相关文章

  1. 【BZOJ4591】&lbrack;SHOI2015&rsqb;超能粒子炮&&num;183&semi;改 (卢卡斯定理)

    [BZOJ4591][SHOI2015]超能粒子炮·改 (卢卡斯定理) 题面 BZOJ 洛谷 题解 感天动地!终于不是拓展卢卡斯了!我看到了一个模数,它是质数!!! 看着这个东西就感觉可以递归处理. ...

  2. 洛谷 P4345 &lbrack;SHOI2015&rsqb;超能粒子炮&&num;183&semi;改 解题报告

    P4345 [SHOI2015]超能粒子炮·改 题意 求\(\sum_{i=0}^k\binom{n}{i}\),\(T\)组数据 范围 \(T\le 10^5,n,j\le 10^{18}\) 设\ ...

  3. 【bzoj4591】&lbrack;Shoi2015&rsqb;超能粒子炮&&num;183&semi;改 Lucas定理

    题目描述 曾经发明了脑洞治疗仪&超能粒子炮的发明家SHTSC又公开了他的新发明:超能粒子炮·改--一种可以发射威力更加强大的粒子流的神秘装置.超能粒子炮·改相比超能粒子炮,在威力上有了本质的提 ...

  4. loj 2038 &sol; 洛谷 P4345 &lbrack;SHOI2015&rsqb; 超能粒子炮・改 题解

    好玩的推式子 题目描述 曾经发明了脑洞治疗仪与超能粒子炮的发明家 SHTSC 又公开了他的新发明:超能粒子炮・改--一种可以发射威力更加强大的粒子流的神秘装置. 超能粒子炮・改相比超能粒子炮,在威力上 ...

  5. P4345 &lbrack;SHOI2015&rsqb;超能粒子炮&&num;183&semi;改 Lucas

    \(\color{#0066ff}{ 题目描述 }\) 曾经发明了脑洞治疗仪与超能粒子炮的发明家 SHTSC 又公开了他的新发明:超能粒子炮・改--一种可以发射威力更加强大的粒子流的神秘装置. 超能粒 ...

  6. &lbrack;洛谷P4345&rsqb;&lbrack;SHOI2015&rsqb;超能粒子炮&&num;183&semi;改

    题目大意:给你$n,k$,求:$$\sum\limits_{i=0}^k\binom n i\pmod{2333}$$题解:令$p=2333,f(n,k)\equiv\sum\limits_{i=0} ...

  7. P4345 &lbrack;SHOI2015&rsqb;超能粒子炮&&num;183&semi;改

    传送门 看到数据和模数大小就知道要上 lucas 了 然后开始愉快地推公式: 答案为 $\sum _{i=0}^kC_{n}^{i}\ (mod\ 2333)$ 设 $f [ i ] [ j ] = ...

  8. 【bzoj4591】&lbrack;Shoi2015&rsqb;超能粒子炮&&num;183&semi;改

    设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 ...

  9. Bzoj 4591&colon; &lbrack;Shoi2015&rsqb;超能粒子炮&&num;183&semi;改 数论&comma;Lucas定理&comma;排列组合

    4591: [Shoi2015]超能粒子炮·改 Time Limit: 10 Sec  Memory Limit: 256 MBSubmit: 178  Solved: 70[Submit][Stat ...

随机推荐

  1. selenium&colon;org&period;openqa&period;selenium&period;WebDriverException&colon; f&period;QueryInterface is not a function

    今天用selenium2遇到问题 org.openqa.selenium.WebDriverException: f.QueryInterface is not a function 查了好久最后终于 ...

  2. 谈谈java开发

    1.不要让未来的决策阻止你现在前进的方向 一步步列出每个步骤,那么对于现在应该专注于做什么,就一目了然了.你也不会浪费   时间去担心应该以后操心的事情. 2.不要让自信诱骗你忘事 当你去学习一个新概 ...

  3. asp&period;net登录时验证码的制作与验证

    1.新建一个页面,ImageCode.aspx 2.在Page_Load中添加如下代码 string tmp = RndNum(4); HttpCookie a = new HttpCookie(&q ...

  4. 简单方便地扩充Python的系统路径

    参考: http://www.elias.cn/Python/PythonPath?from=Develop.PythonPath http://v2in.com/pth-file-usage-in- ...

  5. Win7&lowbar;Wifi热点

    1. 怎样在Win7系统建立并开启Wifi热点 http://jingyan.baidu.com/article/48a42057a03cf7a9242504d0.html 2.

  6. 64位win2003 IIS6运行32位的&period;NET程序

    做web服务迁移,从32位win2003迁移到64位win2003,数据库是32位Oracle在另外一台服务器上. 迁移之后数据库各种连不上,oracle的客户端32位的装完装64位的,odp.net ...

  7. js本地预览图片

    废话不说  直接上代码 <script type="text/javascript" src="http://code.jquery.com/jquery-late ...

  8. GCTF2017部分write up

    Misc stage1 拿到题看到是一张图片隐写 用神器Stegsolve看看发现左上角藏着一张二维码 截下来,不能直接扫,需要反色处理一下 扫出来是一串十六进制 看头几个十六进制数发现是pyc文件 ...

  9. Bash的数组

    Bash 2.x提供了创建一维数组的能力. 有多种方法创建,用内建命令declare -a或直接数组元素赋值. 向数组赋值时,如果不指定下标,下标自动从0开始,每次增加1. 数组的尺寸没有限制,下标也 ...

  10. ajax和跨域

    一.简介 ajax是什么? AJAX(Asynchronous JavaScript and XML) 是一种在无需重新加载整个网页的情况下,能够更新部分网页的技术. AJAX, (异步的JavaSc ...