結果

問題 No.1595 The Final Digit
ユーザー hirakich1000000007
提出日時 2021-05-10 21:54:06
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 1 ms / 2,000 ms
コード長 10,777 bytes
コンパイル時間 360 ms
コンパイル使用メモリ 36,096 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-01 14:21:41
合計ジャッジ時間 1,025 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#if 0
cat <<EOF >mistaken-paste
#endif
// thx Ebi-chan!
// pragma GCC optimize("unroll-loops")
// pragma GCC optimize("O3")
#pragma GCC diagnostic ignored "-Wincompatible-pointer-types"
#define _USE_MATH_DEFINES
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <math.h>
#include <time.h>
#define BIG 2000000007LL
#define VERYBIG 200000000000000007LL
#define ULTRABIG 300000000000000000000LL
#define MOD 1000000007LL
#define FOD  998244353LL
#define HOD 1000000009LL
#define IOD  100000007LL
typedef uint64_t ull;
typedef  int64_t ll;
#define N_MAX 1048576
#ifdef __cplusplus
#include <queue>
#include <stack>
// #include <tuple>
#include <set>
#include <map>
#include <string>
#include <algorithm>
// #include <functional>
// #include <array>
#include <iostream>
using std::queue;
using std::priority_queue;
using std::stack;
// using std::tuple;
using std::set;
using std::map;
using std::vector;
using std::greater;
using std::pair;
using std::string;
// using std::get;
// using std::function;
// using std::array;
using std::cin;
using std::cout;
using std::endl;
template <typename T, typename U>
pair<T, U> operator+(pair<T, U> l, pair<T, U> r) {
    return pair<T, U>(l.first + r.first, l.second + r.second);
}
#endif
#ifndef M_PI
#define M_PI 3.14159265358979323846264338327950
#endif
typedef struct {
    ll a;
    ll b;
} hwll;
typedef struct {
    ll a;
    ll b;
    ll c;
} hwllc;
typedef struct {
    hwll a;
    hwll b;
} linell;
typedef struct {
    double a;
    double b;
} hwreal;
ll n, m;
ll h, w;
ll k;
ll q;
ll va, vb, vc, vd, ve, vf;
ull ua, ub, uc, ud, ue, uf;
long double vra, vrb, vrc;
double vda, vdb, vdc;
char ch, dh;
ull umin (ull x, ull y) {
    return (x < y) ? x : y;
}
ull umax (ull x, ull y) {
    return (x > y) ? x : y;
}
ll smin (ll x, ll y) {
    return (x < y) ? x : y;
}
ll smax (ll x, ll y) {
    return (x > y) ? x : y;
}
double dmin (double x, double y) {
    return (x < y) ? x : y;
}
double dmax (double x, double y) {
    return (x > y) ? x : y;
}
ull gcd (ull x, ull y) {
    if (y == 0) {
        return x;
    } else {
        return gcd(y, x % y);
    }
}
ull bitpow (ull a, ull x, ull modulo) {
    ull result = 1;
    while (x) {
        if (x & 1) {
            result *= a;
            result %= modulo;
        }
        x /= 2;
        a = (a * a) % modulo;
    }
    return result;
}
ull divide (ull a, ull b, ull modulo) {
    return (a * bitpow(b, modulo - 2, modulo)) % modulo;
}
ull udiff (ull a, ull b) {
    if (a >= b) {
        return a - b;
    } else {
        return b - a;
    }
}
ll sdiff (ll a, ll b) {
    if (a >= b) {
        return a - b;
    } else {
        return b - a;
    }
}
int bitcount (ull n) {
    int result = 0;
    while (n) {
        if (n & 1) result++;
        n /= 2;
    }
    return result;
}
#define BEGCMP(NAME) int32_t NAME (const void *left, const void *right)
#define DEFLR(TYPE) TYPE l=*(TYPE*)left,r=*(TYPE*)right
#define CMPRET(L, R) if((L)<(R))return-1;if((L)>(R))return+1
// int32_t pullcomp (const void *left, const void *right) {
//  ull l = *(ull*)left;
//  ull r = *(ull*)right;
//  if (l < r) {
//      return -1;
//  }
//  if (l > r) {
//      return +1;
//  }
//  return 0;
// }
BEGCMP(pullcomp){
    DEFLR(ull);
    CMPRET(l, r);
    return 0;
}
BEGCMP(prevcomp){
    DEFLR(ll);
    CMPRET(r, l);
    return 0;
}
BEGCMP(pllcomp){
    DEFLR(ll);
    CMPRET(l, r);
    return 0;
}
BEGCMP(pcharcomp){
    DEFLR(char);
    CMPRET(l, r);
    return 0;
}
BEGCMP(pdoublecomp){
    DEFLR(double);
    CMPRET(l, r);
    return 0;
}
int32_t pstrcomp (const void *left, const void *right) {
    char* l = *(char**)left;
    char* r = *(char**)right;
    return strcmp(l, r);
}
BEGCMP(phwllABcomp){
    DEFLR(hwll);
    CMPRET(l.a, r.a);
    CMPRET(l.b, r.b);
    return 0;
}
BEGCMP(phwllREVcomp){
    DEFLR(hwll);
    CMPRET(l.b, r.b);
    CMPRET(l.a, r.a);
    return 0;
}
BEGCMP(ptriplecomp){
    DEFLR(hwllc);
    CMPRET(l.a, r.a);
    CMPRET(l.b, r.b);
    CMPRET(l.c, r.c);
    return 0;
}
BEGCMP(ptripleREVcomp){
    DEFLR(hwllc);
    CMPRET(l.b, r.b);
    CMPRET(l.a, r.a);
    CMPRET(l.c, r.c);
    return 0;
}
BEGCMP(ptripleCABcomp){
    DEFLR(hwllc);
    CMPRET(l.c, r.c);
    CMPRET(l.a, r.a);
    CMPRET(l.b, r.b);
    return 0;
}
BEGCMP(phwrealcomp){
    DEFLR(hwreal);
    CMPRET(l.a, r.a);
    CMPRET(l.b, r.b);
    return 0;
}
int32_t pquadcomp (const void *left, const void *right) {
    linell l = *(linell*)left;
    linell r = *(linell*)right;
    ll ac = phwllABcomp(&(l.a), &(r.a));
    if (ac) return ac;
    ll bc = phwllABcomp(&(l.b), &(r.b));
    if (bc) return bc;
    return 0;
}
int32_t pfracomp (const void *left, const void *right) {
    hwll l = *(hwll*)left;
    hwll r = *(hwll*)right;
    CMPRET(l.a * r.b, l.b * r.a);
    return 0;
}
bool isinrange (ll left, ll x, ll right) {
    return (left <= x && x <= right);
}
bool isinrange_soft (ll left, ll x, ll right) {
    return (left <= x && x <= right) || (left >= x && x >= right);
}
void sw (ll *l, ll *r) {
    if (*l == *r) return;
    ll t = *l;
    *l = *r;
    *r = t;
}
void uw (ull *l, ull *r) {
    if (*l == *r) return;
    ull t = *l;
    *l = *r;
    *r = t;
}
ull frac[N_MAX * 10], invf[N_MAX * 10];
void f_init (ll n, ll m) {
    frac[0] = 1;
    for (ll i = 1; i <= n; i++) {
        frac[i] = frac[i - 1] * i % m;
    }
    invf[n] = divide(1, frac[n], m);
    for (ll i = n - 1; i >= 0; i--) {
        invf[i] = invf[i + 1] * (i + 1) % m;
    }
}
ull ncr (ll n, ll r, ull m) {
    if (n < 0 || r < 0 || n < r) return 0;
    return frac[n] * (invf[r] * invf[n - r] % m) % m;
}
ll a[N_MAX * 10];
// ull a[N_MAX + 5];
// ll a[3005][3005];
ll b[N_MAX * 5];
// ull b[N_MAX + 5];
// ll b[3005][3005];
ll c[N_MAX * 5];
ll d[N_MAX * 5];
ll e[N_MAX * 4];
char s[N_MAX + 1];
// char s[3010][3010];
char t[N_MAX + 1];
// char t[3010][3010];
char u[N_MAX + 1];
hwll xy[N_MAX];
hwllc tup[N_MAX];
// ll table[3005][3005];
ll table[2005][2005];
ull gin[N_MAX];
// here we go
// ull parent[501910], size[501910], edges[501910];
// void init (ull n) {
//  for (ll i = 0; i < n; i++) {
//      parent[i] = i;
//      size[i] = 1;
//  }
// }
// ll find (ull x) {
//  if (parent[x] == x) return x;
//  return parent[x] = find(parent[x]);
// }
// bool unite (ull v, ull u) {
//  v = find(v);
//  u = find(u);
//  if (v == u) return false;
//  if (size[v] < size[u]) {
//      ull tmp = v;
//      v = u;
//      u = tmp;
//  }
//  size[v] += size[u];
//  parent[u] = v;
//  return true;
// }
ll func1 (ll x) {
    ll result = 0;
    for (ll i = 1; i <= n; i++) {
        ll y = x - i;
        if (y < 2) continue;
        
        if (y > n * 2) y = n * 2;
        result += d[y];
    }
    // printf("%lld: %lld\n", x, result);
    return result;
}
ll func2 (ll x, ll sum) {
    ll result = 0;
    for (ll i = 1; i <= x; i++) {
        ll y = sum - i;
        if (y < 2 || y > n * 2) continue;
        result += c[y];
    }
    // printf("%lld %lld: %lld\n", x, sum, result);
    return result;
}
void query (ll x, ll y) {
    ll s = 0, t = 0;
    for (ll i = 0; i < 10; i++) {
        if (x & (1LL << i)) {
            b[s++] = i;
        }
        if (y & (1LL << i)) {
            c[t++] = i;
        }
    }
    puts("Yes");
    printf("%lld", s);
    for (ll i = 0; i < s; i++) printf(" %lld", b[i] + 1);
        putchar('\n');
    printf("%lld", t);
    for (ll i = 0; i < t; i++) printf(" %lld", c[i] + 1);
        putchar('\n');
    exit(0);
}
ll dp[123456][3][2];
ll mat[6][6];
ll matp[6][6], powg[6][6], tmp[6][6];
void matpow (ll x) {
    ll i, j, ki;
    for (i = 0; i < 6; i++) {
        for (j = 0; j < 6; j++) {
            matp[i][j] = ((i == j) ? 1 : 0);
            powg[i][j] = mat[i][j];
        }
    }
    while (x) {
        if (x % 2) {
            for (i = 0; i < 6; i++) {
                for (j = 0; j < 6; j++) {
                    tmp[i][j] = 0;
                    for (ki = 0; ki < 6; ki++) {
                        tmp[i][j] += (matp[i][ki] * powg[ki][j]) % MOD;
                    }
                    tmp[i][j] %= MOD;
                }
            }
            for (i = 0; i < 6; i++) {
                for (j = 0; j < 6; j++) {
                    matp[i][j] = tmp[i][j];
                }
            }
        }
        x /= 2;
            for (i = 0; i < 6; i++) {
                for (j = 0; j < 6; j++) {
                    tmp[i][j] = 0;
                    for (ki = 0; ki < 6; ki++) {
                        tmp[i][j] += (powg[i][ki] * powg[ki][j]) % MOD;
                    }
                    tmp[i][j] %= MOD;
                }
            }
            for (i = 0; i < 6; i++) {
                for (j = 0; j < 6; j++) {
                    powg[i][j] = tmp[i][j];
                }
            }
    }
}
ll solve () {
    ll i, j, ki, li;
    // ull result = 0;
    ll result = 0;
    double dresult = 0;
    // ull maybe = 0;
    ll maybe = 0;
    // ull sum = 0;
    ll sum = 0;
    ll item;
    ll *dpcell;
    va %= 10;
    vb %= 10;
    vc %= 10;
    k -= 3;
    ll index = 0;
    while (true) {
        ll vd = (va + vb + vc) % 10;
        va = vb;
        vb = vc;
        vc = vd;
        index++;
        item = (va * 100 + vb * 10 + vc);
        if (b[item] > 0) {
            k = (k - b[item]) % (index - b[item]) + b[item];
            break;
        }
        a[index] = item;
        b[item] = index;
        // if (k == index) {
        //  break;
        // }
    }
    result = a[k] % 10;
    printf("%lld\n", result);
    // printf("%.15f\n", dresult);
    // puts(s);
    return 0;
    success:
    // puts("YES");
    puts("Yes");
    // printf("%lld\n", result);
    // puts("0");
    // puts("First");
    return 0;
    fail:
    // puts("NO");
    // puts("No");
    // puts("0");
    puts("-1");
    // puts("-1 -1 -1");
    // puts(":(");
    return 1;
}
int main (int argc, char *argv[]) {
    int32_t i, j;
    // scanf("%llu", &m);
    // scanf("%lld", &w);
    // scanf("%lld%lld", &h, &w);
    // scanf("%lld", &n, &m);
    // scanf("%lld", &k, &n, &m);
    // scanf("%llu%llu", &h, &w);
    // scanf("%lld", &q);
    scanf("%lld%lld%lld", &va, &vb, &vc, &vd);
    // va--;
    // vb--;
    // scanf("%llu%llu%llu", &ua, &ub, &uc, &ud, &ue);
    // scanf("%s", s);
    // scanf("%s", t);
    // scanf("%s", u);
    scanf("%lld", &k);
    // scanf("%lld", &m);
    // scanf("%lld", &n);
    // for (i = 0; i < n; i++) {
    //  // scanf("%s", s[i]);
    //  // scanf("%lld", &c[i]);
    //  scanf("%lld", &a[i]);
    // }
    // scanf(" %c", &ch);
    // scanf("%llu", &q);
    for (i = 0; i < 0; i++) {
        // scanf("%lld%lld", &xy[i].a, &xy[i].b);
        // scanf("%lld%lld%lld", &tup[i].a, &tup[i].b, &tup[i].c);
        // scanf("%lld", &c[i]);
        scanf("%lld", &a[i]);
        // scanf("%lld", &b[i]);
        // scanf("%lld", &c[i]);
        // scanf("%lld", &d[i]);
        // scanf("%lld", &e[i]);
        // a[i]--;
        // b[i]--;
        // c[i]--;
        // d[i]--;
        // xy[i].a--;
        // xy[i].b--;
        // tup[i].a--;
        // tup[i].b--;
    }
    // scanf("%lld%lld", &va, &vb);
    // scanf("%llu", &m);
    // scanf("%llu", &q);
    // scanf("%s", t);
    // for (i = 0; i < n; i++) {
    //  // scanf("%lld%lld", &xy[i].a, &xy[i].b);
    //  // xy[i].a--;
    //  // xy[i].b--;
    //  // scanf("%lld", &a[i], &b[i]);
    //  // scanf("%lld", &b[i]);
    //  // a[i]--;
    //  // b[i]--;
    //  scanf("%lld", &c[i]);
    //  // scanf("%lld", &d[i]);
    //  // scanf("%lld", &e[i]);
    //  c[i]--;
    //  // d[i]--;
    // }
    // for (i = 0; i < q; i++) {
    //  // scanf("%lld%lld", &xy[i].a, &xy[i].b);
    //  scanf("%lld", &c[i]);
    //  // xy[i].a--;
    //  // xy[i].b--;
    // }
    // for (i = 0; i < h; i++) {
    //  for (j = 0; j < w; j++) {
    //      scanf("%lld", &table[i][j]);
    //      // table[i][j]--;
    //  }
    // }
    // for (i = 0; i < n; i++) {
    //  scanf("%s", s[i]);
    // }
    // for (i = 0; i < n; i++) {
    //  scanf("%s", t[i]);
    // }
    // scanf("%llu", &q);
    // for (i = 0; i < q; i++) {
    //  scanf("%lld%lld%lld", &e[i], &c[i], &d[i]);
    //  c[i]--;
    // }
    solve();
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0