[SHOI2015]超能粒子炮·改
题意
求\(\sum_{i=0}^{k} {C_n^i}\% 2333\) \(,(n,k\leq 10^{18})\)
思路
如果直接套卢卡斯还是比较容易想到分块求解的
由\(C_n^i = C_{n\%p}^{i\%p} \times C_{n/p}^{i/p}\)可知，\(i\%p\)相同的组合数另一部分分别是\(i/p,i/p+1,i/p+2...\)，这部分可以搓到一起
令\(S_n^k = \sum_{i=0}^{k}{C_n^i}\)具体来说，将这部分相同的部分放到一起，剩下的地方直接计算
相同的部分，后半部分可以递归计算：\[(\sum_{i=0}^{p-1}{C_{n\%p}^{i}})\times \sum_{i=0}^{k/p-1}{C_{n/p}^{i}}\]
剩下的部分,组合数用卢卡斯定理计算：\[(\sum_{i=0}^{k\%p}{C_{n\%p}^{i}}) \times C_{n/p}^{k/p}=S_{n\%p}^{k\%p}\times C_{n/p}^{k\%p}\]
预处理出\(C\)和\(S\)即可递归计算，感觉有些边界问题，然而数据水都能过qwq
（嘴上解释不清楚，但是自己推起来很简单的）
Code
#include<bits/stdc++.h>
#define Min(x,y) ((x)<(y)?(x):(y))
#define Max(x,y) ((x)>(y)?(x):(y))
using namespace std;
typedef long long ll;
const ll mod = 2333;
int T;
ll n,k,C[2500][2500];
ll sum[2500][2500];//Sigma(C(i,0~j))
ll jc[2500],inv[2500];
template <class T>
void read(T &x)
{
char c; int sign=1;
while((c=getchar())>'9'||c<'0') if(c=='-') sign=-1; x=c-48;
while((c=getchar())>='0'&&c<='9') x=(x<<1)+(x<<3)+c-48; x*=sign;
}
void init()
{
C[0][0]=C[1][0]=C[1][1]=1;
for(int i=2;i<=mod;++i)
{
C[i][0]=1;
for(int j=1;j<=i;++j) C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
}
for(int i=0;i<=mod;++i)
{
sum[i][0]=1;
for(int j=1;j<=mod;++j) sum[i][j]=(sum[i][j-1]+C[i][j])%mod;
}
}
ll lucas(ll n,ll m)
{
if(n<m) return 0;
if(!n||!m) return 1;
return C[n%mod][m%mod] * lucas(n/mod,m/mod) %mod;
}
ll solve(ll n,ll k)//Sigma(C(n,0~k))
{
if(!n) return 1;
if(n<mod&&k<mod) return sum[n][k];
ll p=k/mod;//有mod组相同的
ll c=k-p*mod;//剩下的单独算
ll ans=0;
if(p) ans += sum[n%mod][mod-1] * solve(n/mod,p-1)%mod;
ans += sum[n%mod][c] * lucas(n/mod,p)%mod;
return (ans%mod+mod)%mod;
}
int main()
{
init();
read(T);
while(T--)
{
read(n);read(k);
printf("%lld\n",solve(n,k));
}
return 0;
}1、Vue的进入和离开和列表的过渡
2、迭代器的使用，新格式化输出
3、Gradle中的GroupID和ArtifactID指的是什么？
4、BUUCTF | SQL COURSE 1
5、php抽象类和接口的区别