結果

問題 No.1889 K Consecutive Ks (Hard)
ユーザー 👑 ygussany
提出日時 2022-03-19 19:11:05
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 1,175 ms / 6,000 ms
コード長 5,465 bytes
コンパイル時間 1,377 ms
コンパイル使用メモリ 42,536 KB
実行使用メモリ 170,584 KB
最終ジャッジ日時 2024-10-05 02:09:48
合計ジャッジ時間 15,995 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

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

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <stdio.h>
#define N_MAX 200000
#define M_MAX 200000
const int Mod = 998244353,
    bit[21] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576},
    bit_inv[21] = {1, 499122177, 748683265, 873463809, 935854081, 967049217, 982646785, 990445569, 994344961, 996294657, 997269505, 997756929, 
        998000641, 998122497, 998183425, 998213889, 998229121, 998236737, 998240545, 998242449, 998243401},
    root[21] = {1, 998244352, 911660635, 372528824, 929031873, 452798380, 922799308, 781712469, 476477967, 166035806, 258648936, 584193783, 63912897, 
        350007156, 666702199, 968855178, 629671588, 24514907, 996173970, 363395222, 565042129},
    root_inv[21] = {1, 998244352, 86583718, 509520358, 337190230, 87557064, 609441965, 135236158, 304459705, 685443576, 381598368, 335559352, 
        129292727, 358024708, 814576206, 708402881, 283043518, 3707709, 121392023, 704923114, 950391366};
int ntt_b[20][524288], ntt_c[20][524288], ntt_x[20][524288], ntt_y[20][524288];
void NTT(int k, int a[], int z[])
{
    if (k == 0) {
        z[0] = a[0];
        return;
    }
    
    int i, d = bit[k-1], tmpp;
    long long tmp;
    for (i = 0; i < d; i++) {
        ntt_b[k][i] = a[i*2];
        ntt_c[k][i] = a[i*2+1];
    }
    NTT(k - 1, ntt_b[k], ntt_x[k]);
    NTT(k - 1, ntt_c[k], ntt_y[k]);
    for (i = 0, tmp = 1; i < d; i++, tmp = tmp * root[k] % Mod) {
        tmpp = tmp * ntt_y[k][i] % Mod;
        z[i] = ntt_x[k][i] + tmpp;
        if (z[i] >= Mod) z[i] -= Mod;
        z[i+d] = ntt_x[k][i] - tmpp;
        if (z[i+d] < 0) z[i+d] += Mod;
    }
}
void NTT_reverse(int k, int z[], int a[])
{
    if (k == 0) {
        a[0] = z[0];
        return;
    }
    
    int i, d = bit[k-1], tmpp;
    long long tmp;
    for (i = 0; i < d; i++) {
        ntt_x[k][i] = z[i*2];
        ntt_y[k][i] = z[i*2+1];
    }
    NTT_reverse(k - 1, ntt_x[k], ntt_b[k]);
    NTT_reverse(k - 1, ntt_y[k], ntt_c[k]);
    for (i = 0, tmp = 1; i < d; i++, tmp = tmp * root_inv[k] % Mod) {
        tmpp = tmp * ntt_c[k][i] % Mod;
        a[i] = ntt_b[k][i] + tmpp;
        if (a[i] >= Mod) a[i] -= Mod;
        a[i+d] = ntt_b[k][i] - tmpp;
        if (a[i+d] < 0) a[i+d] += Mod;
    }
}
// Compute the product of two polynomials a[0-da] and b[0-db] using NTT in O(d * log d) time
void prod_poly_NTT(int da, int db, int a[], int b[], int c[])
{
    int i, k;
    for (k = 0; bit[k] <= da + db; k++);
    for (i = da + 1; i < bit[k]; i++) a[i] = 0;
    for (i = db + 1; i < bit[k]; i++) b[i] = 0;
    
    static int x[524288], y[524288], z[524288];
    NTT(k, a, x);
    if (db == da) {
        for (i = 0; i <= da; i++) if (a[i] != b[i]) break;
        if (i <= da) NTT(k, b, y);
        else for (i = 0; i < bit[k]; i++) y[i] = x[i];
    } else NTT(k, b, y);
    for (i = 0; i < bit[k]; i++) z[i] = (long long)x[i] * y[i] % Mod;
    NTT_reverse(k, z, c);
    for (i = 0; i <= da + db; i++) c[i] = (long long)c[i] * bit_inv[k] % Mod;
}
// Compute the product of two polynomials a[0-da] and b[0-db] naively in O(da * db) time
void prod_poly_naive(int da, int db, int a[], int b[], int c[])
{
    int i, j;
    for (i = 0; i <= da + db; i++) c[i] = 0;
    for (i = 0; i <= da; i++) {
        for (j = 0; j <= db; j++) {
            c[i+j] += (long long)a[i] * b[j] % Mod;
            if (c[i+j] >= Mod) c[i+j] -= Mod;
        }
    }
}
// Compute the product of two polynomials a[0-da] and b[0-db] in an appropriate way
void prod_polynomial(int da, int db, int a[], int b[], int c[])
{
    const int THR = 250000;
    if (THR / (da + 1) >= db + 1) prod_poly_naive(da, db, a, b, c);
    else prod_poly_NTT(da, db, a, b, c);
}
long long pow_mod(int n, long long k)
{
    long long N, ans = 1;
    for (N = n; k > 0; k >>= 1, N = N * N % Mod) if (k & 1) ans = ans * N % Mod;
    return ans;
}
int solve_sqrt(int N, int M)
{
    const int THR = 10000;
    int i, j, d[N_MAX + 1] = {}, a[524288], b[524288], c[524288] = {};
    long long dp[N_MAX + 1], tmp, sum = 0;
    for (i = 2; i <= M; i++) for (j = i; j <= N; j += i) d[j]++;
    for (j = 0; j < THR; j++) b[j] = d[j];
    for (i = 1, dp[0] = 1; i <= N; i++) {
        if (i % THR == 0) {
            for (j = (i - 1) / THR * THR; j < i; j++) {
                a[j] = dp[j];
                b[j+THR] = d[j+THR];
            }
            prod_poly_NTT(i - 1, i - 1 + THR, a, b, c);
        }
        for (j = i / THR * THR, tmp = c[i]; j < i - 1; j++) tmp += dp[j] * d[i-j];
        tmp %= Mod;
        dp[i] = pow_mod(M - 1, i) - (sum + tmp) % Mod;
        if (dp[i] < 0) dp[i] += Mod;
        sum = (sum * (M - 1) + tmp * (M - 2)) % Mod;
    }
    return (pow_mod(M, N) - dp[N] % Mod + Mod) % Mod;
}
long long recursion(int N, int M, int d[], long long dp[], long long tmp[], long long sum, int l, int r)
{
    if (l == r) {
        tmp[l] %= Mod;
        dp[l] = pow_mod(M - 1, l) - (sum + tmp[l]) % Mod;
        if (dp[l] < 0) dp[l] += Mod;
        sum = (sum * (M - 1) + tmp[l] * (M - 2)) % Mod;
        return sum;
    }
    
    int i, m = (l + r) / 2;
    static int a[524288], b[524288], c[524288];
    sum = recursion(N, M, d, dp, tmp, sum, l, m);
    for (i = l; i <= m; i++) a[i-l] = dp[i];
    for (i = l; i <= r; i++) b[i-l] = d[i-l];
    prod_polynomial(m - l, r - l, a, b, c);
    for (i = m + 1; i <= r; i++) tmp[i] += c[i-l];
    return recursion(N, M, d, dp, tmp, sum, m + 1, r);
}
int solve_log2(int N, int M)
{
    int i, j, d[N_MAX + 1] = {};
    long long dp[N_MAX + 1] = {1}, tmp[N_MAX + 1] = {};
    for (i = 2; i <= M; i++) for (j = i; j <= N; j += i) d[j]++;
    for (i = 1; i <= N; i++) tmp[i] = d[i];
    recursion(N, M, d, dp, tmp, 0, 1, N);
    return (pow_mod(M, N) - dp[N] % Mod + Mod) % Mod;
}
int main()
{
    int N, M;
    scanf("%d %d", &N, &M);
    // printf("%d\n", solve_sqrt(N, M));
    printf("%d\n", solve_log2(N, M));
    fflush(stdout);
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0