TopCoder SRM500 Div1 1000 其他

原文链接https://www.cnblogs.com/zhouzhendong/p/SRM500-1000.html

SRM500 Div1 1000

设 \(v_1,v_2,\cdots ,v_9\) 分别为一个数中 \(1-9\) 的出现次数。

那么可以列出如下方程组：

\[\begin{eqnarray*}
v_1+2v_2+3v_3+\cdots +9v_9 &=& S\\
v_2+2v_4+3v_8+v_6 &=& p_2\\
v_3+v_6+2v_9 &=& p_3\\
v_5 &=& p_5\\
v_7 &=& p_7
\end{eqnarray*}
\]

有 9 个变量，5 个方程，所以只需要枚举其中 4 个就可以得到所有的。于是问题被转化成了知道 \(v_1\cdots v_9\)，求这些数对答案的贡献。先假设所有的 \(t=\sum_{1\leq i \leq 9}v_i\) 个数都互不相同，则任意一个数在任意一个位置都会产生 \((t-1)!\) 次贡献，所以总贡献为 \(a=(\sum_{0\leq i <t} 10 ^i)(\sum_{1\leq i\leq 9}iv_i)((t-1)!)\) 。由于值相同的数是等价的，所以最终得到的贡献为 \(a/(\prod _{1\leq i \leq 9}v_i!)\) 。

代码

static const int N=3005,mod=500500573;

int Pow(int x,int y){

	int ans=1;

	for (;y;y>>=1,x=1LL*x*x%mod)

		if (y&1)

			ans=1LL*ans*x%mod;

	return ans;

}

int Fac[N],Inv[N],Iv[N],sum[N];

void prework(int n){

	for (int i=Fac[0]=1;i<=n;i++)

		Fac[i]=1LL*Fac[i-1]*i%mod;

	Inv[n]=Pow(Fac[n],mod-2);

	for (int i=n;i>=1;i--)

		Inv[i-1]=1LL*Inv[i]*i%mod;

	for (int i=1;i<=n;i++)

		Iv[i]=1LL*Inv[i]*Fac[i-1]%mod;

	sum[0]=0;

	for (int i=1;i<=n;i++)

		sum[i]=(10LL*sum[i-1]+1)%mod;

}

int v1,v2,v3,v4,v5,v6,v7,v8,v9;

int calc(){

	static int t;

	t=v1+v2+v3+v4+v5+v6+v7+v8+v9;

	return 1LL*Fac[t-1]*sum[t]%mod

			*(v1*1+v2*2+v3*3+v4*4+v5*5+v6*6+v7*7+v8*8+v9*9)%mod

			*Inv[v1]%mod*Inv[v2]%mod*Inv[v3]%mod

			*Inv[v4]%mod*Inv[v5]%mod*Inv[v6]%mod

			*Inv[v7]%mod*Inv[v8]%mod*Inv[v9]%mod;

}

int getSum(int p2, int p3, int p5, int p7, int S){

	prework(3000);

	int ans=0;

	S-=p5*5+p7*7;

	v5=p5,v7=p7;

	for (v2=0;v2<=p2;v2++)

		for (v4=0;v2+v4*2<=p2;v4++)

			for (v8=0;v8*3+v4*2+v2<=p2;v8++){

				v6=p2-v2-v4*2-v8*3;

				int s2=S-v2*2-v4*4-v8*8-v6*6;

				if (s2<0||p3<v6)

					continue;

				for (v9=(p3-v6)/2;v9>=0;v9--){

					v3=p3-v6-v9*2;

					v1=s2-v9*9-v3*3;

					if (v1<0)

						continue;

					ans=(ans+calc())%mod;

				}

			}

	return ans;

}