# 斯德哥尔摩 的博客

### P1037 产生数

posted on 2018-10-21 11:48:28 | under 刷题 |

P1037 产生数

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define MAXN 11
#define MAXM 1010
using namespace std;
int m;
int num[MAXN];
bool map[MAXN][MAXN];
struct Number{
int len,val[MAXM];
len=0;
int date=0;char c=0;
while(c<'0'||c>'9')c=getchar();
while(c>='0'&&c<='9'){val[++len]=c-'0';c=getchar();}
for(int i=1;i<=len/2;i++)swap(val[i],val[len-i+1]);
}
void print(){
for(int i=len;i>=1;i--)putchar(val[i]+'0');
putchar('\n');
}
void clean(){
len=0;
memset(val,0,sizeof(val));
}
void new_number(int k){
clean();
while(k){
val[++len]=k%10;
k/=10;
}
}
friend Number operator *(const Number &p,const Number &q){
Number s;
s.clean();
s.len=p.len+q.len+2;
for(int i=1;i<=q.len;i++){
int c=0;
for(int j=1;j<=p.len;j++){
s.val[i+j-1]+=q.val[i]*p.val[j]+c;
c=s.val[i+j-1]/10;
s.val[i+j-1]%=10;
}
s.val[i+p.len]+=c;
}
while(!s.val[s.len])s.len--;
return s;
}
}n,ans;
int date=0,w=1;char c=0;
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
return date*w;
}
void floyd(){
for(int k=0;k<=9;k++)
for(int i=0;i<=9;i++)
for(int j=0;j<=9;j++)
map[i][j]|=(map[i][k]&map[k][j]);
}
void work(){
Number x;
ans.new_number(1);
for(int i=1;i<=n.len;i++){
x.new_number(num[n.val[i]]);
ans=ans*x;
}
ans.print();
}
void init(){
int x,y;
for(int i=1;i<=m;i++){
map[x][y]=true;
}
floyd();
for(int i=0;i<=9;i++){
map[i][i]=true;
for(int j=0;j<=9;j++)if(map[i][j])num[i]++;
}
}
int main(){
init();
work();
return 0;
}