問題はこちら
問題概要
を満たす整数の組全てについて
の総和を求めよ.
解説
形式的冪級数で解きます.とすると
よって
としてが答え.
を偶奇で分けると
したがって
Bostan–Moriのアルゴリズムを用いたり,線形漸化式に直して行列累乗したりすると
ライブラリとか除くと実装はこれだけ
int main() { int t;cin >> t; while(t--) { ll n;cin >> n; FormalPowerSeries<MOD,true> f({1}); for (int i = 0; i < 16; i++) f *= {1,-1}; for (int i = 0; i < 5; i++) f *= {1,1}; cout << Bostan_Mori({1},f,n-5) << endl; } return 0; }