tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

AOJ 2436: Card

これらの一部または全部を適当に並べて数字を作ることを考えます。
答えを1,000,000,007 で割ったものを出力してください。

問題文がガバガバすぎる。

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
int mod=1000000007;
int b[210];
int kt[210];
int c[10];
long long dp[1100][1100];
long long C[1100][1100];
long long fact[1100];
long long inv[1100];
long long factinv[1100];
long long ks[1100];
int calc(vector<int>v){
	int n=v.size();
	for(int i=0;i<v.size();i++){
		kt[i]=0;
		int tmp=v[i];
		while(tmp){
			tmp/=10;
			kt[i]++;
		}
		if(kt[i]==0)kt[i]++;
	}
	for(int i=0;i<n;i++){
		ks[i]=0;
		for(int j=0;j<=i;j++){
			ks[i]=(ks[i]+fact[i]*factinv[i-j])%mod;
		}
	}
	for(int i=0;i<10;i++)c[i]=0;
	for(int i=0;i<n;i++)c[kt[i]]++;
	long long ret=0;
	for(int i=1;i<=5;i++){
		if(!c[i])continue;
		for(int j=0;j<1100;j++)for(int k=0;k<1100;k++)dp[j][k]=0;
		dp[0][0]=1;
		for(int j=1;j<=5;j++){
			int has=c[j];
			if(i==j)has--;
			while(has--){
				for(int k=n-1;k>=0;k--)for(int l=0;l<810;l++){
					if(!dp[k][l])continue;
					dp[k+1][l+j]=(dp[k+1][l+j]+dp[k][l]*(k+1))%mod;
				}
			}
		}
		long long sum=0;
		for(int j=0;j<n;j++)if(i==kt[j])sum+=v[j];
		for(int j=0;j<810;j++){
			for(int k=0;k<n;k++){
			//	if(dp[k][j]*sum%mod*ks[n-k-1])printf("%d %d %d: %lld %lld %lld\n",i,j,k,dp[k][j],ks[n-k-1],dp[k][j]*sum%mod*ks[n-k-1]%mod);
				ret=(ret+dp[k][j]*sum%mod*ks[n-k-1])%mod;
			}
			sum=sum*10%mod;
		}
	}
	return (int)ret;
}
int main(){
	C[0][0]=1;
	fact[0]=1;
	inv[1]=1;
	for(int i=2;i<1100;i++)inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
	factinv[0]=1;
	for(int i=1;i<1100;i++)factinv[i]=factinv[i-1]*inv[i]%mod;
	for(int i=1;i<1100;i++)fact[i]=fact[i-1]*i%mod;
	for(int i=0;i<1050;i++){
		for(int j=0;j<=i;j++){
			C[i+1][j]=(C[i+1][j]+C[i][j])%mod;
			C[i+1][j+1]=(C[i+1][j+1]+C[i][j])%mod;
		}
	}
	int a;scanf("%d",&a);
	for(int i=0;i<a;i++)scanf("%d",b+i);
	bool zr=false;
	vector<int>tmp;
	for(int i=0;i<a;i++){
		if(!b[i])zr=true;
		else tmp.push_back(b[i]);
	}
	int ret=0;
	if(zr){
		ret=mod-calc(tmp);
		tmp.push_back(0);
	}
	ret=(ret+calc(tmp))%mod;
	printf("%d\n",ret);
}