SRM 500 Hard

SRM500Hard.cpp

#define MOD 500500573
#include<stdio.h>

int cnt[11], tot;
int inv[2501];
int fact[2501];
int invfact[2501];
long long one[2501];
int sq(int m, int n)
{
	if(n==1) return m;
	long long tmp;
	if(n&1){
		tmp = sq(m, n-1);
		tmp *= m;
		return tmp%MOD;
	}
	else {
		tmp = sq(m, n>>1);
		tmp *= tmp;
		return tmp%MOD;
	}
		
}
int getans()
{
	tot = cnt[1]+cnt[2]+cnt[3]+cnt[4]+cnt[5]+cnt[6]+cnt[7]+cnt[8]+cnt[9];
	int wtot = 0;
	for(int i=1;i<=9;i++)
		wtot += i*cnt[i];
		
	wtot %= MOD;
	
	long long oneone = one[tot], totfact;

	totfact = fact[tot];
	for(int i=1;i<=9;i++) if(cnt[i]) totfact = (totfact * invfact[cnt[i]]) % MOD;

	long long tmp1 = (wtot * oneone) % MOD;
	long long tmp2 = (totfact * inv[tot]) % MOD;
	//printf("%d %lld %lld %lld %d %d %d\n", wtot, tmp1, tmp2, totfact, fact[10], cnt[1], inv[cnt[1]]);
	return (tmp1 * tmp2) % MOD;
}
class ProductAndSum
{
public:
	int getSum(int p2, int p3, int p5, int p7, int s)
	{
		for(int i=1;i<=2500;i++) inv[i]=sq(i, MOD-2);
		fact[0]=1;
		invfact[0]=1;
		for(long long i=1;i<=2500;i++) fact[i]=(fact[i-1]*i)%MOD;
		for(int i=1;i<=2500;i++) invfact[i]=((long long)invfact[i-1]*inv[i])%MOD;
		one[1]=1;
		for(int i=2;i<=2500;i++) one[i]=(one[i-1]*10+1)%MOD;
		int ans=0;
		cnt[5] = p5;
		cnt[7] = p7;
		s -= 5 * p5;
		s -= 7 * p7;
		if(s < 0) return 0;
		for(int p6=0; s>=6*p6 && p2 >= 0 && p3 >= 0; p6++, p2--, p3--)
		{
			int ss = s - 6*p6;
			int op2 = p2;
			for(int p8=0; ss>=8*p8 && p2 >= 0; p8++, p2-=3)
			{
				int sss = ss - 8*p8;
				int op3 = p3;
				for(int p9=0; sss>=9*p9 && p3 >= 0; p9++, p3-=2)
				{
					int ssss = sss - 9*p9;
					int oop2 = p2;
					for(int p4=0; ssss>=4*p4 && p2 >= 0; p4++, p2-=2)
					{
						if((cnt[1]=(ssss-4*p4-2*p2-3*p3))<0) break;
						cnt[1]=ssss-4*p4-2*p2-3*p3; cnt[2]=p2; cnt[3]=p3;
						cnt[4]=p4; cnt[6]=p6; cnt[8]=p8;
						cnt[9]=p9;
						
						ans += getans();
						if(ans > MOD) ans -= MOD;
					}
					p2 = oop2;
				}
				p3 = op3;
			}
			p2 = op2;
		}
		return ans;
	}
};