2017计蒜之道复赛 E.商汤智能机器人(lucas定理+数位DP)

题解

  今天模拟赛T4的原题…
  看了一眼官方的题解没怎么看懂,感觉和我比赛时的写法可能不是很一样?也许是我没看懂…
  首先这个题要先推式子啦,推了挺久的…
  跳到(x+2,y)(x+2,y)的不好算,所以考虑枚举跳的次数。如果跳了ii(x+2,y)(x+2,y),那么总共跳了xix-i次,里面一定有x+y2\frac{x+y}{2}(x+1,y+1)(x+1,y+1)(x+2,y)(x+2,y)的跳法,方案数为:

(xix+y2)\binom{x-i}{\frac{x+y}{2}}

  而这两种跳法的分配方案数是:

(x+y2i)\binom{\frac{x+y}{2}}{i}

  所以可得总的方案数为:

i=0xy2(x+y2i)(xix+y2)\sum_{i=0}^{\frac{x-y}{2}}\binom{\frac{x+y}{2}}{i}\binom{x-i}{\frac{x+y}{2}}

  显然是要用lucas定理的。暴力算只有4040分…那怎么快速计算这个式子呢?
  观察一下lucas定理的另一个式子,其实就是一直用lucas定理化给化出来的:

(nm)=i=1digit(aibi)\binom{n}{m}=\prod_{i=1}^{digit} \binom{a_i}{b_i}

  其中aia_ibib_innmmpp进制下的第ii位。
  这个式子妙在哪里呢?如果需要进行组合数求和且模数较小的话,直接上数位DP统计pp进制下每一位的答案就可以把复杂度降到O(plogpn)O(plog_pn)了。
  这题比较难写的地方在于一个小trick。可以观察到式子里有减法,减完<0<0的话要借11退位,所以需要再开一个数组来计算。

代码

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#define int long long
#define ll long long
using namespace std;
const int maxn=500010, inf=1e9, mod=1e5+3;
int n, m, x, y, ans;
int fac[maxn], inv[maxn];
int f[233], g[233], a[233], b[233];
inline void read(int &k)
{
	int f=1; k=0; char c=getchar();
	while(c<'0' || c>'9') c=='-'&&(f=-1), c=getchar();
	while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
	k*=f;	
} 
int C(int n, int m){return n<m?0:1ll*fac[n]*inv[m]%mod*inv[n-m]%mod;}
inline int power(int a, int b)
{
	int ans=1;
	for(;b;b>>=1, a=1ll*a*a%mod)
	if(b&1) ans=1ll*ans*a%mod;
	return ans;
}
#undef int
int main()
{
	#define int long long
	read(x); read(y);
	if(((x+y)&1) || x<y) return puts("0"), 0;
	fac[0]=1; for(int i=1;i<mod;i++) fac[i]=1ll*fac[i-1]*i%mod;
	inv[mod-1]=power(fac[mod-1], mod-2);
	for(int i=mod-1;i;i--) inv[i-1]=1ll*inv[i]*i%mod;
	n=(x+y)>>1; m=(x-y)>>1;
	int now=x; while(now) a[++a[0]]=now%mod, now/=mod;
	now=n; while(now) b[++b[0]]=now%mod, now/=mod;
	f[1]=1;
	for(int i=1;i<=a[0];i++)
	{
		if(f[i])
		{
			for(int j=0;j<mod;j++)
			if(a[i]>=j) 
			f[i+1]=(f[i+1]+f[i]*C(b[i], j)%mod*C(a[i]-j, b[i]))%mod;
			else g[i+1]=(g[i+1]+f[i]*C(b[i], j)%mod*C(a[i]+mod-j, b[i]))%mod;
		}
		if(g[i])
		{
			for(int j=0;j<mod;j++)
			if(a[i]>=j+1) 
			f[i+1]=(f[i+1]+g[i]*C(b[i], j)%mod*C(a[i]-j-1, b[i]))%mod;
			else g[i+1]=(g[i+1]+g[i]*C(b[i], j)%mod*C(a[i]+mod-j-1, b[i]))%mod;
		}
	}
	printf("%lld\n", f[a[0]+1]);
}