10160번: 암호

https://www.acmicpc.net/problem/10160

#include<stdio.h>
#define MaxN
long long int n, k, ans;
long long int dy[1000010][10], f[10][10];
int main()
{
    int i, j, l;
 
    scanf("%lld%lld", &n, &k);
    f[1][1] = k - 1; f[1][2] = 1;
    f[2][1] = k - 2; f[2][2] = f[2][3] = 1;
    f[3][1] = k - 2; f[3][4] = f[3][6] = 1;
    f[4][1] = k - 2; f[4][2] = f[4][5] = 1;
    f[5][1] = k - 2; f[5][2] = 1;
    f[6][1] = k - 2; f[6][2] = f[6][7] = 1;
    f[7][1] = k - 2; f[7][6] = 1;
    dy[1][1] = k - 1;
    dy[1][2] = 1;
    for (i = 2; i <= n; i++)
    {
        for (j = 1; j <= 7; j++)
        {
            for (l = 1; l <= 7; l++)
            {
                dy[i][j] = (dy[i][j] + dy[i - 1][l] * f[l][j]) % 1000000009;
            }
        }
    }
    for (i = 1; i <= 7; i++)
    {
        ans = (ans + dy[n][i]) % 1000000009;
    }
    printf("%lld", ans);
    return 0;
}

1013번: Contact

https://www.acmicpc.net/problem/1013

#include<stdio.h>
const int MAX_N = 200, f[][10] = { { 7,2,3,3,7,6,3,9,7,9 },{ 1,9,9,4,5,5,8,8,1,9 } };
int n, t, p;
char str[MAX_N + 1];
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%s", str);
        p = 0;
        for (int i = 0; str[i]; i++) p = f[str[i] - '0'][p];
        puts(p == 4 || p == 5 || p == 8 ? "YES" : "NO");
    }
    return 0;
}

#include<cstdio>
#include<regex>
using namespace std;
int t;
char str[201];
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%s", str);
        puts(regex_match(str, regex("(100+1+|01)+")) ? "YES" : "NO");
    }
    return 0;
}