Codeforces #232, Division 1, A ( Division 2, B ) : On Number of Decompositions into Multipliers

問題文

http://codeforces.com/contest/397/problem/C

概要

　n 項からなる数列 a が与えられる。 とする。n 項からなる整数の列であって、総乗が m と等しくなるものの数を mod で求めよ。

解法

　m の値がかなり大きくなり得るので、途中までの積を保存しつつ DP するようなことはできません。より効率的な方法を考える必要があります。
　列の総乗が m になるので、列に含まれる値全部の素因数と m の素因数が等しくなることが分かります。従って、m を素因数分解して、各素因数毎に独立に計算し、最後に統合するという方向性を思索できます。各素因数について、先程の議論*1から、あるある素因数が、答えとなる列全体でいくつあるかは各 a の素因数分解によって知ることができると分かります。後は、その素因数をどの項にいくつ割り振るか先頭から順に決めていく DP をすることで、ある一つの素因数について、割り振りとして可能なパターンの総数を求めることができます。この DP とはすなわち、

• dp[ i 項まで決めた ][ ｊ 個使った ] := 総数

としてこの値を順に計算していくような DP です。こうして求まる値の積を計算すれば、全体での答えになります。この方法ならば、一行目に書いた方法よりもかなり効率的に計算をすることができます。実際に時間・空間の制限に間に合うことを確認していきます。
　まず、a の各要素に関する制約から、考慮すべき素因数は 種類程度になります。a の内、最も多くの素因数をもつ要素 b に含まれる素因数の数は高々 log b 個なので、全体では n log b 個程度になります。それらを n 項の内どこに割り振るかを先頭から順に決めていく DP は時間・空間共に の計算量で完了することができます。全体ではこれに考慮すべき素因数の数（定数）がかかりますが、TL, ML 共に制限内で解を出すことができます。

コード

typedef long long LL;
typedef vector<int> VI;
typedef vector<VI> VVI;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( v, c ) for ( auto &v : c )

#define fst first
#define snd second

const int MOD = 1000000007;

// 素因数分解 O( √N )
vector< long long > primeFactorization( long long N );

LL solve( const int N, const int a )
{
	VVI dp( N + 1, VI( a + 1 ) );
	dp[0][0] = 1;
	
	REP( i, 0, N )
	{
		REP( j, 0, a + 1 )
		{
			if ( j + 1 <= a )
			{
				( dp[i][ j + 1 ] += dp[i][j] ) %= MOD;
			}
			( dp[ i + 1 ][j] += dp[i][j] ) %= MOD;
		}
	}

	return dp[N][a];
}

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int n;
	cin >> n;
	
	map<int,int> counts;
	REP( i, 0, n )
	{
		LL a;
		cin >> a;
		vector<LL> fs = primeFactorization( a );
		FOR( f, fs )
		{
			counts[f]++;
		}
	}

	LL res = 1;
	FOR( c, counts )
	{
		if ( c.fst == 1 )
		{
			continue;
		}

		( res *= solve( n, c.snd ) ) %= MOD;
	}
	cout << res << endl;

	return 0;
}

*1:という程大げさではない