結果

問題 No.3392 Count 23578 Sequence
コンテスト
ユーザー tnakao0123
提出日時 2025-11-30 18:00:13
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 3,224 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 615 ms
コンパイル使用メモリ 61,324 KB
実行使用メモリ 26,852 KB
最終ジャッジ日時 2025-11-30 18:00:52
合計ジャッジ時間 39,131 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 45 WA * 3
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:105:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  105 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
main.cpp:106:36: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  106 |   for (int i = 0; i < n; i++) scanf("%d", as + i);
      |                               ~~~~~^~~~~~~~~~~~~~

ソースコード

diff #
raw source code 

/* -*- coding: utf-8 -*-
 *
 * 3392.cc:  No.3392 Count 23578 Sequence - yukicoder
 */

#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

/* constant */

const int MAX_N = 1000000;
const int P = 4073;
const int MOD = 1000000007;

/* typedef */

using ll = long long;

template<const int MOD>
struct MI {
  int v;
  MI(): v() {}
  MI(int _v): v(_v % MOD) { if (v < 0) v += MOD; }
  MI(long long _v): v(_v % MOD) { if (v < 0) v += MOD; }

  explicit operator int() const { return v; }
  
  MI operator+(const MI m) const { return MI(v + m.v); }
  MI operator-(const MI m) const { return MI(v + MOD - m.v); }
  MI operator-() const { return MI(MOD - v); }
  MI operator*(const MI m) const { return MI((long long)v * m.v); }

  MI &operator+=(const MI m) { return (*this = *this + m); }
  MI &operator-=(const MI m) { return (*this = *this - m); }
  MI &operator*=(const MI m) { return (*this = *this * m); }

  bool operator==(const MI m) const { return v == m.v; }
  bool operator!=(const MI m) const { return v != m.v; }

  MI pow(int n) const {  // a^n % MOD
    MI pm = 1, a = *this;
    while (n > 0) {
      if (n & 1) pm *= a;
      a *= a;
      n >>= 1;
    }
    return pm;
  }

  MI inv() const { return pow(MOD - 2); }
  MI operator/(const MI m) const { return *this * m.inv(); }
  MI &operator/=(const MI m) { return (*this = *this / m); }
};

using mi = MI<MOD>;
using vmi = vector<mi>;

/* global variables */

vmi pes, invpes;

/* subroutines */

inline void prep_rhash(int n) {
  pes.resize(n + 1), invpes.resize(n + 1);
  pes[0] = invpes[0] = 1;
  pes[1] = P;
  invpes[1] = pes[1].inv();
  for (int i = 2; i <= n; i++) {
    pes[i] = pes[i - 1] * P;
    invpes[i] = invpes[i - 1] * invpes[1];
  }
}

inline vmi v2rh(int n, int as[]) {
  vmi rh(n + 1, 0);
  for (int k = 0; k < n; k++)
    rh[k + 1] = rh[k] + pes[k] * as[k];
  return rh;
}

inline mi v2h(int n, int as[]) {
  mi h = 0;
  for (int k = 0; k < n; k++) h += pes[k] * as[k];
  return h;
}

inline mi rhash(vmi &rh, int i, int j) {
  return (rh[j] - rh[i]) * invpes[i];
}

/* global variables */

int as[MAX_N], ds[MAX_N];

/* subroutines */

/* main */

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) scanf("%d", as + i);

  for (int i = 0; i < n - 1; i++) ds[i] = as[i + 1] - as[i];

  prep_rhash(n);
  auto rh0 = v2rh(n - 1, ds);
  reverse(ds, ds + n - 1);
  auto rh1 = v2rh(n - 1, ds);

  ll sum = 0;
  for (int i = 0; i < n; i++) {
    int maxl = min(i, n - 1 - i);
    int l0 = 0, l1 = maxl + 1;
    while (l0 + 1 < l1) {
      int l = (l0 + l1) / 2;
      auto h0 = rhash(rh0, i - l, i);
      auto h1 = rhash(rh1, n - 1 - (i + l), n - 1 - i);
      if (h0 == h1) l0 = l;
      else l1 = l;
    }
    sum += l0 + 1;
    //printf(" %d-%d,%d-%d\n", i - l0, i, i, i + l0);

    if (i < n - 1) {
      int maxl = min(i, n - 2 - i);
      int l0 = 0, l1 = maxl + 1;
      while (l0 + 1 < l1) {
	int l = (l0 + l1) / 2;
	auto h0 = rhash(rh0, i - l, i);
	auto h1 = rhash(rh1, n - 1 - (i + 1 + l), n - 1 - (i + 1));
	if (h0 == h1) l0 = l;
	else l1 = l;
      }
      sum += l0 + 1;
      //printf(" %d-%d,%d-%d\n", i - l0, i, i + 1, i + 1 + l0);
    }
  }

  printf("%lld\n", sum);
  
  return 0;
}
0