「SHOI2015」超能粒子炮・改

题目链接

算法：

         我们设每一组n与k的数据的所求答案为，（聪明的人已经发现了秘密所在）

         则,设模数p=2333.

         根据卢卡斯定理，原式=，

         且可以把它拆成

          进一步化为

                         =

           根据对CNLZP(n,k)的定义，原式= 

            此时计算的时间复杂度已绰绰有余（没错就是笔者不会算），预处理组合数，套用卢卡斯定理即可。

            借https://35178.blog.luogu.org/solution-p4345博客中的时间复杂度：

Code:

#include
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define rep2(i,j,k) for(int i=j;i>=k;i--)
#define mo 2333
using namespace std;
template void read(T &num){char c=getchar();num=0;T f=1;while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){num=(num<<3)+(num<<1)+(c^48);c=getchar();}num*=f;
}
template void qwq(T x){if(x>9)qwq(x/10);putchar(x%10+'0');
}
template void write(T x){if(x<0){x=-x;putchar('-');}qwq(x);putchar('\n');
}
int c[2400][2400];
inline void C(){rep(i,0,mo-1){rep(j,0,mo-1){if(i

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！