上手いこと探索。
半分全列挙をmap DPで早くしたらオーバーキルみたいな感じになってしまった。上手いこと探索系は苦手なのでしょうがない。
#include<stdio.h> #include<algorithm> #include<map> #include<string.h> using namespace std; char in[20]; map<int,int> dpL[8][3][71]; map<int,int> dpR[8][3][71]; long long ret=0; long long lt[71]; long long rt[71]; int main(){ scanf("%s",in); int n=strlen(in); int L=n/2; int R=n-L; dpL[0][0][0][1]=dpR[0][0][0][1]=1; for(int i=0;i<L;i++){ for(int j=0;j<3;j++){ for(int l=0;l<10;l++){ int tj=j; if(j==0&&l<in[i]-'0')tj=1; else if(j==0&&l>in[i]-'0')tj=2; for(int k=0;k<=(10*i);k++){ for(map<int,int>::iterator it=dpL[i][j][k].begin();it!=dpL[i][j][k].end();it++){ // printf("%d %d %d %d: %d %d\n",i,j,k,l,(*it).first,(*it).second); if(!dpL[i+1][tj][k+l].count((*it).first*(l+1)))dpL[i+1][tj][k+l][(*it).first*(l+1)]=(*it).second; else dpL[i+1][tj][k+l][(*it).first*(l+1)]+=(*it).second; } } } } } for(int i=0;i<R;i++){ for(int j=0;j<3;j++){ for(int l=0;l<10;l++){ int tj=j; if(j==0&&l<in[i+L]-'0')tj=1; else if(j==0&&l>in[i+L]-'0')tj=2; for(int k=0;k<=(10*i);k++){ for(map<int,int>::iterator it=dpR[i][j][k].begin();it!=dpR[i][j][k].end();it++){ if(!dpR[i+1][tj][k+l].count((*it).first*(l+1)))dpR[i+1][tj][k+l][(*it).first*(l+1)]=(*it).second; else dpR[i+1][tj][k+l][(*it).first*(l+1)]+=(*it).second; } } } } } int S=0; long long T=1; for(int i=0;i<n;i++){ S+=in[i]-'0'; T*=in[i]-'0'+1; } for(int i=0;i<71;i++)for(int j=0;j<3;j++){ for(map<int,int>::iterator it=dpL[L][j][i].begin();it!=dpL[L][j][i].end();it++)lt[i]+=(*it).second; for(map<int,int>::iterator it=dpR[R][j][i].begin();it!=dpR[R][j][i].end();it++)rt[i]+=(*it).second; } for(int i=0;i<71;i++)for(int j=0;j<71;j++){ if(i+j<S){ ret+=lt[i]*rt[j]; // printf("%d %d\n",lt[i],rt[j]); }else if(i+j==S){ for(int k=0;k<3;k++)for(int l=0;l<3;l++){ for(map<int,int>::iterator it1=dpL[L][k][i].begin();it1!=dpL[L][k][i].end();it1++) for(map<int,int>::iterator it2=dpR[R][l][j].begin();it2!=dpR[R][l][j].end();it2++){ //printf("%d %d: %d %d %d %d\n",k,l,(*it1).first,(*it1).second,(*it2).first,(*it2).second); if((long long)(*it1).first*(*it2).first<T)ret+=(long long)(*it1).second*(*it2).second; if((long long)(*it1).first*(*it2).first==T){ if(k==1||(k==0&&l==1))ret+=(long long)(*it1).second*(*it2).second; } } } } } printf("%lld\n",ret); }