いろはちゃんコンテスト Day1 : K - ルーレット

方針ミスって手間取った。
https://atcoder.jp/contests/iroha2019-day1/tasks/iroha2019_day1_k

問題

N個の数列がある。
各数列から1つずつ数値を選び、選んだものを連結して1つの大きな数値を作ることを考える。
全選び方の組み合わせにおける数値の総和を求めよ。

解法

下の位から順に、(10^(桁数)*組み合わせ数)の総和を求めていこう。
桁数別に組み合わせ数を持とうとするとTLE/MLEするので注意。

int N;
int M[202020];
vector<int> A[202020];
ll S[202020];
int L[202020][11];
ll mo=1000000007;

ll ret=0;
ll p10[2020202];
ll dp[202020];
ll SM[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	SM[0]=1;
	FOR(i,N) {
		cin>>M[i];
		FOR(j,M[i]) {
			cin>>x;
			A[i].push_back(x);
			S[i]+=x;
			y=0;
			while(x) y++, x/=10;
			L[i][y]++;
		}
		SM[i+1]=SM[i]*M[i]%mo;
		S[i]%=mo;
	}
	p10[0]=1;
	FOR(i,2020100) p10[i+1]=p10[i]*10%mo;
	
	dp[0]=1;
	int ma=0;
	FOR(i,N) {
		j=N-1-i;
		(ret+=dp[i]*S[j]%mo*SM[j])%=mo;
		for(x=1;x<=10;x++) if(L[j][x]) {
			(dp[i+1]+=dp[i]*p10[x]%mo*L[j][x])%=mo;
		}
	}
	cout<<ret<<endl;
	
}

まとめ

ええ、最初桁数を持とうとして破たんしました。