记录编号	412419	评测结果	AA
题目名称	[SHOI 2015] 超能粒子炮·改	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.310 s
提交时间	2017-06-09 10:09:54	内存使用	41.86 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int p=2333;
ll n,m;
int T,C[p][p],S[p][p],mi[p],a[p],b[p],sum[p],val[p];
int lucas(int n,int m){
	if (n<p&&m<p) return C[n][m];
	return C[n%p][m%p]*lucas(n/p,m/p)%p;
}
int vio(){
	int ans=0;
	for (ll i=0;i<m;i++) ans=(ans+lucas(n,i))%p;
	return ans;
}
int main()
{
	freopen("cnlzb.in","r",stdin);
	freopen("cnlzb.out","w",stdout);
	for (int i=0;i<p;i++){
		S[i][0]=C[i][0]=1;
		for (int j=1;j<=i;j++) C[i][j]=(C[i-1][j-1]+C[i-1][j])%p;
	}
	for (int i=0;i<p;i++)
	for (int j=1;j<p;j++)
		S[i][j]=(C[i][j]+S[i][j-1])%p;
	mi[0]=1;
	for (int i=1;i<p;i++) mi[i]=mi[i-1]*2%p;
	scanf("%d",&T);
	while (T--){
		scanf("%lld%lld",&n,&m);m++;
		int bitn=0,bitm=0;
		for (;n;n/=p) a[++bitn]=n%p;
		for (;m;m/=p) b[++bitm]=m%p;
		sum[0]=val[bitm+1]=1;
		for (int i=1;i<=bitn;i++) sum[i]=mi[a[i]];
		for (int i=1;i<=bitm;i++) val[i]=C[a[i]][b[i]];
		for (int i=1;i<=bitn;i++) sum[i]=sum[i]*sum[i-1]%p;
		for (int i=bitm;i;i--) val[i]=val[i]*val[i+1]%p;
		int ans=0;
		for (int i=1;i<=bitm;i++)
			if (b[i]) ans=(ans+(ll)sum[i-1]*val[i+1]*S[a[i]][b[i]-1])%p;
		for (;bitn;a[bitn--]=0);
		for (;bitm;b[bitm--]=0);
		printf("%d\n",ans);
	}
	return 0;
}