今回時間だけ見ればみなEasyと大差ないし、これ450ptでもいい気がする。
https://community.topcoder.com/stat?c=problem_statement&pm=14550
解法
以下を考えると、sum(dp(L))が解となる。
dp(L) := 条件を満たす長さLの数列の数
ここで、要素数Lの数列がどうすれば条件を満たすかを考える。
今回の条件を満たすには、まず各要素1の数列を準備し、結局各素数p[i]を合計a[i]いずれかの要素に掛ける、ということを繰り返す。
ただし、1のままの要素が残っていてはならない。
前者については重複組み合わせでを求めればよい。
あとは包除原理の要領で1のままの要素が残っているケースを引こう。
L個中ちょうどK個しか1より大きな値が入っていないケースは、通りなので、K<Lの各Kに対し、左の値を引いていこう。
ll mo=1000000007; ll dp[3000]; ll combi(ll N_, ll C_) { const int NUM_=400001; static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1]; if (fact[0]==0) { inv[1]=fact[0]=factr[0]=1; for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo; for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo; } if(C_<0 || C_>N_) return 0; return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo; } ll hcomb(int P_,int Q_) { return (P_==0&&Q_==0)?1:combi(P_+Q_-1,Q_);} class OrderedProduct { public: int count(vector <int> a) { int sum=0; FORR(r,a) sum+=r; int i,j; ll ret=0; for(i=1;i<=sum;i++) { dp[i]=1; FORR(r,a) { (dp[i] *= hcomb(i,r))%=mo; } for(j=1;j<i;j++) { (dp[i] += mo - dp[j]*combi(i,j)%mo)%=mo; } ret += dp[i]; } return ret%mo; } }
まとめ
どっかでこの問題出てそう。