結果

問題 No.2989 Fibonacci Prize
ユーザー 👑 ygussany
提出日時 2024-12-14 01:38:04
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 14 ms / 2,000 ms
コード長 3,422 bytes
コンパイル時間 302 ms
コンパイル使用メモリ 33,792 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-12-14 01:38:07
合計ジャッジ時間 2,518 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 77
権限があれば一括ダウンロードができます

ソースコード

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

#include <stdio.h>
int naive(int N, int M)
{
    int i;
    static __int128 F[1001];
    for (i = 3, F[1] = 1, F[2] = 1; i <= M; i++) F[i] = F[i-1] + F[i-2];
    
    int ans = 0, l, r;
    __int128 sum;
    for (l = 1; l <= M; l++) {
        for (r = l; r <= M; r++) {
            for (i = l, sum = 0; i <= r; i++) {
                sum += F[i];
                if (sum > F[M]) break;
            }
            if (i > r && sum % N == 0) ans++;
        }
    }
    return ans;
}
long long solve(int N, int M)
{
    if (M == 1) {
        if (N == 1) return 1;
        else return 0;
    } else if (M == 2) {
        if (N == 1) return 2;
        else return 0;
    } else if (M == 3) {
        if (N == 1) return 4;
        else if (N == 2) return 2;
        else return 0;
    } else if (N == 1) return (long long)(M - 2) * (M - 1) / 2 + 3;
    
    int i, cur, prev, F[2], sum = 2 % N, flag = 0;
    static int num[200001], tmp[200001];
    for (i = 0; i < N; i++) {
        num[i] = 0;
        tmp[i] = 0;
    }
    num[0]++;
    num[1]++;
    num[sum]++;
    for (i = 3, F[0] = 1, F[1] = 1, cur = 1, prev = 0; i <= M - 2; i++, cur ^= 1, prev ^= 1) {
        F[prev] += F[cur];
        if (F[prev] >= N) F[prev] -= N;
        if (sum == 0 && F[prev] == 0 && F[cur] == 1) {
            if (flag == 0) flag = i;
            else {
                flag = i - flag;
                break;
            }
        }
        sum += F[prev];
        if (sum >= N) sum -= N;
        num[sum]++;
        if (flag > 0) tmp[sum]++;
    }
    if (i <= M - 2) {
        int j, k = (M - 2 - i) / flag;
        for (j = 0; j < N; j++) num[j] += k * tmp[j];
        i += k * flag;
        for (num[sum]++, i++, cur ^= 1, prev ^= 1; i <= M - 2; i++, cur ^= 1, prev ^= 1) {
            F[prev] += F[cur];
            if (F[prev] >= N) F[prev] -= N;
            sum += F[prev];
            if (sum >= N) sum -= N;
            num[sum]++;
        }
    }
    
    long long ans = 0;
    for (i = 0; i < N; i++) ans += (long long)num[i] * (num[i] - 1) / 2;
    F[prev] += F[cur];
    if (F[prev] >= N) F[prev] -= N;
    if (F[prev] == 0) ans++;
    if ((F[prev] + F[cur]) % N == 0) ans += 2;
    return ans;
}
#define MT_N 624
#define MT_M 397
#define MT_MATRIX_A 0x9908b0dfUL
#define MT_UPPER_MASK 0x80000000UL
#define MT_LOWER_MASK 0x7fffffffUL
static unsigned int mt[MT_N];
static int mti = MT_N + 1;
void init_genrand(unsigned int s)
{
    mt[0] = s & 0xffffffffUL;
    for (mti = 1; mti < MT_N; mti++) {
        mt[mti] = (1812433253UL * (mt[mti-1] ^ (mt[mti-1] >> 30)) + mti); 
        mt[mti] &= 0xffffffffUL;
    }
}
unsigned int genrand()
{
    unsigned int y;
    static unsigned int mag01[2] = {0x0UL, MT_MATRIX_A};
    if (mti >= MT_N) {
        int kk;
        if (mti == MT_N + 1) init_genrand(5489UL);
        
        for (kk = 0; kk < MT_N - MT_M; kk++) {
            y = (mt[kk] & MT_UPPER_MASK) | (mt[kk+1] & MT_LOWER_MASK);
            mt[kk] = mt[kk+MT_M] ^ (y >> 1) ^ mag01[y&0x1UL];
        }
        for (; kk < MT_N - 1; kk++) {
            y = (mt[kk] & MT_UPPER_MASK) | (mt[kk+1] & MT_LOWER_MASK);
            mt[kk] = mt[kk+(MT_M-MT_N)] ^ (y >> 1) ^ mag01[y&0x1UL];
        }
        y = (mt[MT_N-1] & MT_UPPER_MASK) | (mt[0] & MT_LOWER_MASK);
        mt[MT_N-1] = mt[MT_M-1] ^ (y >> 1) ^ mag01[y&0x1UL];
        mti = 0;
    }
  
    y = mt[mti++];
    y ^= (y >> 11);
    y ^= (y << 7) & 0x9d2c5680UL;
    y ^= (y << 15) & 0xefc60000UL;
    y ^= (y >> 18);
    return y;
}
int main()
{
    int N, M;
    scanf("%d %d", &N, &M);
    if (N == 1 && M == 1) printf("2\n");
    else printf("%lld\n", solve(N, M));
    
    /*
    for (N = 1; N <= 10; N++) {
        for (M = 1; M <= 160; M++) {
            if (solve(N, M) != naive(N, M)) printf("%d %d %lld %d\n", N, M, solve(N, M), naive(N, M));
        }
    }
    */
    fflush(stdout);
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0