TopCoder SRM 720 Div1 Easy SumProduct

この日AIM Techと合わせてConstruction系連続で大量にレートを溶かした。
https://community.topcoder.com/stat?c=problem_statement&pm=14661

問題

桁数がblank1、blank2の2つの整数A,Bを作ることを考える。
A,Bの各桁において、0～9の各数iは合計で最大amount[i]回まで登場してよい。
また、ともにleading zeroを含んでも構わない。

そのようなA,Bの対に対し、A*Bの総和を求めよ。

解法

Aのある桁がx、Bのある桁がyであるようなケースを考えよう。
のこり(blank1+blank2-2)個の桁を、残されたamount[i]で埋める組み合わせは二項係数を使ったDPで求めることができる。
その組み合わせをf(x,y)通りとする。

さて、x,yの位置が各桁にある場合を考えると、を答えに勘案することになる。
まとめると、としてが解となる。

class SumProduct {
	public:
	int findSum(vector <int> amount, int blank1, int blank2) {
		ll pat[2]={1,1};
		int i;
		FOR(i,blank1-1) pat[0]=(pat[0]*10+1)%mo;
		FOR(i,blank2-1) pat[1]=(pat[1]*10+1)%mo;
		
		int x,y,j,z;
		ll ret=0;
		for(x=1;x<=9;x++) if(amount[x]) {
			amount[x]--;
			for(y=1;y<=9;y++) if(amount[y]) {
				amount[y]--;
				
				ZERO(from);
				from[blank1+blank2-2]=1;
				FOR(i,10) {
					ZERO(to);
					
					for(j=0;j<=blank1+blank2-2;j++) if(from[j]) {
						FOR(z,min(j,amount[i])+1) (to[j-z]+=from[j]*combi(j,z))%=mo;
					}
					swap(from,to);
				}
				
				(ret += x*y*pat[0]%mo*pat[1]%mo*from[0])%=mo;
				amount[y]++;
			}
			amount[x]++;
		}
		return ret;
		
	}
}

まとめ

Easyにしてはちょっとしんどい。