记录编号 444736 评测结果 AAAAA
题目名称 [NOIP 2002]产生数 最终得分 100
用户昵称 GravatarHeHe 是否通过 通过
代码语言 C++ 运行时间 0.001 s
提交时间 2017-09-04 08:00:16 内存使用 0.56 MiB
显示代码纯文本
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

inline char getc(void) { 
    static char buf[1 << 18], *fs, *ft;
    return (fs == ft && (ft = (fs = buf) + fread(buf, 1, 1 << 18, stdin)), fs == ft) ? EOF : *fs++;
}

inline unsigned read(char *s) { 
    register char *p = s;
    while(!isgraph(*p = getc()));
    while(isgraph(*(++p) = getc()));
    *p = '\0'; return p - s;
}

inline int read(void) { 
    register int res = 0;
    register char tmp = getc();
    while(!isdigit(tmp)) tmp = getc();
    while(isdigit(tmp))
        res = ((res + (res << 2)) << 1) + (tmp ^ 0x30),
        tmp = getc();
    return res;
}

class Bignum{ 
    private:
        char s[110];
        unsigned len;
    public:
        Bignum() { 
            memset(s, 0x00, sizeof(s));
            len = 1;
        }
        Bignum(int x) { *this = x;}

        Bignum operator = (int x) { 
            char *p = s;
            memset(this, 0x00, sizeof(Bignum));
            do{ 
                *(p++) = x % 10;
                x /= 10;
            }while(x);
            len = p - s; 
            return *this;
        }

        Bignum operator * (const Bignum &a) { 
            static Bignum b;
            memset(&b, 0x00, sizeof(Bignum));
            b.len = len + a.len;
            for(unsigned i = 0; i < len; ++i) 
                for(unsigned j = 0; j < a.len; ++j) { 
                    b.s[i + j] += s[i] * a.s[j];
                    if(b.s[i + j] > 9) 
                        b.s[i + j + 1] += b.s[i + j] / 10,
                        b.s[i + j] %= 10;
                }
            while(!b.s[b.len - 1]) --b.len;
            return b;
        }

        void print(void) { 
            for(unsigned i = len - 1; ~i; --i) 
                putchar(s[i] | 0x30);
            return ;
        }
};

struct EDGE{ 
    int to;
    EDGE *ne;
    EDGE(int t, EDGE *n) { 
        to = t, ne = n;
    }
};

char s[310];
bool f[10][10];
int len, n, cnt[10];
Bignum ans = 1;

int main() { 
#ifndef LOCAL
    freopen("build.in", "r", stdin);
    freopen("build.out", "w", stdout);
#endif
    len = read(s), n = read();
    for(int i = 0; i < len; ++i) s[i] ^= 0x30;
    for(int i = 0; i < n; ++i) f[read()][read()] = true;
    for(int i = 0; i < 10; ++i) f[i][i] = true;
    for(int k = 0; k < 10; ++k) 
        for(int i = 0; i < 10; ++i) 
            for(int j = 0; j < 10; ++j) 
                if(f[i][k] && f[k][j]) 
                    f[i][j] = true;
    for(int i = 0; i < 10; ++i) 
        for(int j = 0; j < 10; ++j) 
            if(f[i][j]) ++cnt[i];
    for(int i = 0; i < len; ++i)
        ans = ans * cnt[(int)s[i]];
    ans.print();
    return 0;
}