結果

問題 No.3572 Number of special equations
コンテスト
ユーザー MGNTR
提出日時 2026-06-19 22:25:11
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 1 ms / 2,000 ms
コード長 1,327 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,813 ms
コンパイル使用メモリ 357,888 KB
実行使用メモリ 6,400 KB
最終ジャッジ日時 2026-06-19 22:25:17
合計ジャッジ時間 5,044 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

// 根は x=0 か |x|=1なるやつだけ
// 共役なやつは、同じじゃないとまずい
// -> a+b+... + 2(A+B+C+) = N  みたいな問題をいくつか解ければいい
//母関数パンチ！
//すみません、面倒すぎませんか...
//bostanmoriなのでパクる maspy さんありがとう...
#include <bits/stdc++.h>
#include <atcoder/modint>
#include <atcoder/convolution>

using namespace std;
using namespace atcoder;

using ll = long long;
template <typename T>
using vc = vector<T>;
#define FOR(i, a, b) for (int i = a; i < int(b); ++i)

using mint = modint998244353;
int len(vector<mint> a){
	return a.size();
}

mint Bostan_Mori(vc<mint> P, vc<mint> Q, ll K) {
  int d = len(Q) - 1;
  while (K > 0) {
    vc<mint> Q_minus(d + 1);
    FOR(i, 0, d + 1) Q_minus[i] = (i & 1 ? -Q[i] : Q[i]);
    vc<mint> U = convolution(P, Q_minus);
    vc<mint> V = convolution(Q, Q_minus);
    P.clear(), Q.clear();
    for (int i = K % 2; i < len(U); i += 2) P.push_back(U[i]);
    for (int i = 0; i < len(V); i += 2) Q.push_back(V[i]);
    K /= 2;
  }
  return P[0];
}

void solve() {
 ll n;cin>>n;
  vector<mint> P={0,-2,0,2,-2};
  vector<mint> Q={-1,2,1,-4,2};
  mint ANS = Bostan_Mori(P, Q, n);
  cout << ANS.val() << "\n";
}

signed main() {
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  solve();
}
0