AOJ 2436 Card

だいぶ想定解まで迫ったもののO(N^4)から落とせず、解説を見てしまった。
桁数でまとめる発想がなかったのは頭悪すぎたので反省

typedef long long ll;
#define MOD 1000000007
const int SIZE = 100100;
ll inv[SIZE+10],fac[SIZE+10],facinv[SIZE+10];
ll Pow[1010],kai[210];
ll val[210];
ll nCr(int n,int r)
{
	if(n<r)return -1;
	if(n<0||r<0)return -1;
	return ((fac[n]*facinv[r]%MOD)*facinv[n-r])%MOD;
}
ll func(int n)
{
	ll ret = 0ll;
	for(int i=0;i<=n;i++)ret = (ret+(nCr(n,i)*kai[i])%MOD)%MOD;
	return ret;
}
void init()
{
	fac[0]=1ll;
	for(int i=1;i<=SIZE;i++)fac[i]=(fac[i-1]*i)%MOD;
	inv[1]=1ll;
	for(int i=2;i<=SIZE;i++)inv[i]=((-(MOD/i)*inv[MOD%i])%MOD+MOD)%MOD;
	facinv[0]=1ll;
	for(int i=1;i<=SIZE;i++)facinv[i]=(facinv[i-1]*inv[i])%MOD;
	Pow[0]=1ll;
	for(int i=0;i<1000;i++)Pow[i+1]=(Pow[i]*10ll)%MOD;
	kai[0]=1ll;
	for(int i=1;i<=200;i++)kai[i]=(kai[i-1]*i)%MOD;
	for(int i=0;i<=200;i++)val[i]=func(i);
}
int cnt_digit(ll x)
{
	if(x==0ll)return 1;
	int ret = 0;
	while(x){ret++;x/=10ll;}
	return ret;
}
ll dp[210][1010];
int n;
ll a[210];
int dig[210];
ll digit_sum[5];
int del[5];
int zero=-1;
int N;
void culc_dp(int unuse)
{
	memset(dp,0,sizeof(dp));
	dp[0][0]=1ll;
	for(int i=0;i<N;i++)
	{
		if(i==unuse)continue;
		for(int j=i;j>=0;j--)
		{
			for(int k=0;k<=j*4;k++)
			{
				if(dp[j][k]==0)continue;
				dp[j+1][k+dig[i]]+=dp[j][k];
				dp[j+1][k+dig[i]]%=MOD;
			}
		}
	}
}
ll solve()
{
	ll ans = 0ll;
	for(int d=1;d<=4;d++)
	{
		if(del[d]==-1)continue;
		culc_dp(del[d]);
		for(int i=0;i<N;i++)
		{
			for(int j=0;j<=4*N;j++)
			{
				if(dp[i][j]==0)continue;
				ans += (((((((val[N-i-1]*kai[i])%MOD)*digit_sum[d])%MOD)*dp[i][j])%MOD)*Pow[j])%MOD;
				ans %= MOD;
			}
		}
	}
	return ans;
}

int main()
{
	init();
	memset(del,-1,sizeof(del));
	scanf("%d",&n);
	N=n;
	for(int i=0;i<n;i++)scanf("%lld",&a[i]);
	for(int i=0;i<n;i++)
	{
		dig[i]=cnt_digit(a[i]);
		digit_sum[dig[i]]+=a[i];
		del[dig[i]]=i;
		if(a[i]==0)zero=i;
	}
	ll ans = solve();
	//cout << solve() << ' ';
	if(zero!=-1)
	{
		swap(a[zero],a[n-1]);
		N--;
		memset(del,-1,sizeof(del));
		memset(digit_sum,0,sizeof(digit_sum));
		for(int i=0;i<N;i++)
		{
			dig[i]=cnt_digit(a[i]);
			digit_sum[dig[i]]+=a[i];
			del[dig[i]]=i;
		}
		ans -= solve();
		//cout << solve() << endl;
		ans = ((ans%MOD)+MOD)%MOD;
	}
	printf("%lld\n",ans);
	return 0;
}