結果

問題 No.1648 Sum of Powers
ユーザー 👑 ygussany
提出日時 2021-08-05 09:23:41
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 148 ms / 2,000 ms
コード長 2,353 bytes
コンパイル時間 255 ms
コンパイル使用メモリ 32,896 KB
実行使用メモリ 6,528 KB
最終ジャッジ日時 2024-10-03 16:11:58
合計ジャッジ時間 10,828 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 56
権限があれば一括ダウンロードができます

ソースコード

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

#include <stdio.h>
#define DIM 2
const int Mod = 998244353;
void copy_matrix(int d, long long A[][DIM], long long B[][DIM])
{
    int i, j;
    for (i = 0; i < d; i++) for (j = 0; j < d; j++) B[i][j] = A[i][j];
}
void prod_matrix(int d, long long A[][DIM], long long B[][DIM], long long C[][DIM])
{
    int i, j, k;
    for (i = 0; i < d; i++) {
        for (j = 0; j < d; j++) {
            for (k = 0, C[i][j] = 0; k < d; k++) C[i][j] += A[i][k] * B[k][j] % Mod;
            C[i][j] %= Mod;
        }
    }
}
void pow_matrix(int d, long long A[][DIM], long long k, long long B[][DIM])
{
    int i, j;
    long long C[2][DIM][DIM], D[DIM][DIM];
    copy_matrix(d, A, C[0]);
    for (i = 0; i < d; i++) for (j = 0; j < d; j++) B[i][j] = 0;
    for (i = 0; i < d; i++) B[i][i] = 1;
    for (i = 0, j = 1; k > 0; i ^= 1, j ^= 1, k >>= 1) {
        prod_matrix(d, C[i], C[i], C[j]);
        if (k % 2 == 1) {
            prod_matrix(d, B, C[i], D);
            copy_matrix(d, D, B);
        }
    }
}
void copy_vector(int d, long long x[], long long y[])
{
    int i;
    for (i = 0; i < d; i++) y[i] = x[i];
}
void prod_matrix_vector(int d, long long A[][DIM], long long x[], long long y[])
{
    int i, j;
    for (i = 0; i < d; i++) {
        for (j = 0, y[i] = 0; j < d; j++) y[i] += A[i][j] * x[j] % Mod;
        y[i] %= Mod;
    }
}
#define HASH 200003
const int H_Mod = HASH;
typedef struct List {
    struct List *next;
    int N;
    long long z[DIM];
} list;
int hash_func(long long x[])
{
    return ((x[0] << 20) + x[1]) % H_Mod;
}
int main()
{
    long long A, B, P, Q;
    scanf("%lld %lld %lld %lld", &A, &B, &P, &Q);
    
    int h, i;
    long long S[DIM][DIM] = {{0, 1}, {Mod - B, A}}, T[DIM][DIM], x[DIM] = {2, A}, z[DIM];
    list *hash[HASH] = {}, d[100001], *p;
    for (i = 1; i <= 100000; i++) {
        pow_matrix(2, S, (long long)i * 100000, T);
        prod_matrix_vector(2, T, x, z);
        d[i].N = i;
        d[i].z[0] = z[0];
        d[i].z[1] = z[1];
        h = hash_func(z);
        for (p = hash[h]; p != NULL; p = p->next) if (p->z[0] == z[0] && p->z[1] == z[1]) break;
        if (p == NULL) {
            d[i].next = hash[h];
            hash[h] = &(d[i]);
        }
    }
    for (i = 0, z[0] = Q, z[1] = P; i < 100000; i++) {
        h = hash_func(z);
        for (p = hash[h]; p != NULL; p = p->next) if (p->z[0] == z[0] && p->z[1] == z[1] && (long long)p->N * 100000 - i + 1 >= 2) break;
        if (p != NULL) break;
        copy_vector(2, z, x);
        prod_matrix_vector(2, S, x, z);
    }
    printf("%lld\n", (long long)p->N * 100000 - i + 1);
    fflush(stdout);
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0