結果
問題 | No.1561 connect x connect |
ユーザー |
👑 ![]() |
提出日時 | 2024-05-28 03:35:13 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 301 ms / 2,000 ms |
コード長 | 11,041 bytes |
コンパイル時間 | 5,173 ms |
コンパイル使用メモリ | 183,596 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-12-20 20:38:42 |
合計ジャッジ時間 | 9,237 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
#include <iostream>#include <string>#include <vector>#include <algorithm>#include <utility>#include <atcoder/modint>// (edited) Nyaan's librarynamespace nachia{// output : denominator of rational gftemplate <typename Modint>std::vector<Modint> BerlekampMassey(const std::vector<Modint> &s){const int N = (int)s.size();std::vector<Modint> b, c;b.reserve(N+1);c.reserve(N+1);const Modint Zero = Modint(0);const Modint One = Modint(1);b.push_back(One);c.push_back(One);Modint y = One;for(int ed=1; ed<=N; ed++){int l = int(c.size());int m = int(b.size());Modint x = Zero;for(int i=0; i<l; i++) x += c[i] * s[ed-l+i];b.push_back(Zero);m++;if(x.val() == 0) continue;Modint freq = x / y;if(l < m){auto tmp = c;c.insert(c.begin(), m-l, Zero);for(int i=0; i<m; i++) c[i] -= freq * b[i];std::swap(b, tmp); y = x;} else {for(int i=0; i<m; i++) c[l-m+i] -= freq * b[i];}}std::reverse(c.begin(), c.end());return c;}} // namespace nachia#include <atcoder/convolution>#include <cassert>namespace nachia{// ax + by = gcd(a,b)// return ( x, - )std::pair<long long, long long> ExtGcd(long long a, long long b){long long x = 1, y = 0;while(b){long long u = a / b;std::swap(a-=b*u, b);std::swap(x-=y*u, y);}return std::make_pair(x, a);}} // namespace nachianamespace nachia{class DynamicModSupplier{using u64 = unsigned long long;using Int = unsigned int;private:u64 imod;Int mod;// atcoder libraryu64 reduce2(u64 z) const noexcept {// atcoder library#ifdef _MSC_VERu64 x; _umul128(z, im, &x);#elseusing u128 = unsigned __int128;u64 x = (u64)(((u128)(z)*imod) >> 64);#endifreturn z - x * mod;}Int reduce(u64 z) const noexcept {Int v = reduce2(z);if(mod <= v) v += mod;return v;}public:DynamicModSupplier(unsigned int MOD = 998244353) : mod(MOD) {assert(2 <= MOD);assert(MOD < (1u << 31));imod = (u64)(-1) / mod + 1;}Int add(Int a, Int b) const { a += b; if(a >= mod){ a -= mod; } return a; }Int sub(Int a, Int b) const { a -= b; if(a >= mod){ a += mod; } return a; }Int mul(Int a, Int b) const { return reduce((u64)a * b); }Int muladd(Int a, Int b, Int c) const { return reduce((u64)a * b + c); }Int inv(Int a) const {Int v = ExtGcd(a, mod).first;return (v < mod) ? v : (v + mod);}Int pow(Int a, u64 i) const {Int r = a, ans = 1;while(i){if(i & 1) ans = mul(ans, r);i /= 2;r = mul(r, r);}return ans;}Int getMod() const { return mod; }};} // namespace nachianamespace nachia{template<class FinishType>struct GarnerMod{using Int = unsigned int;using IntLong = unsigned long long;std::vector<Int> mods;std::vector<DynamicModSupplier> dynmods;std::vector<std::vector<Int>> table_coeff;std::vector<Int> table_coeffinv;void precalc(std::vector<Int> new_mods){mods = std::move(new_mods);dynmods.resize(mods.size());for(size_t i=0; i<mods.size(); i++) dynmods[i] = DynamicModSupplier(mods[i]);int nmods = mods.size();table_coeff.assign(nmods+1, std::vector<Int>(nmods, 1));for(int j=0; j<nmods; j++){for(int k=0; k<nmods; k++) table_coeff[j+1][k] = table_coeff[j][k];for(int k=j+1; k<nmods; k++) table_coeff[j+1][k] = dynmods[k].mul(table_coeff[j+1][k], mods[j] % mods[k]);}table_coeffinv.resize(nmods);for(int i=0; i<nmods; i++) table_coeffinv[i] = dynmods[i].inv(table_coeff[i][i]);}FinishType calc(const std::vector<Int>& x){int nmods = mods.size();std::vector<Int> table_const(nmods);FinishType res = 0;FinishType res_coeff = 1;for(int j=0; j<nmods; j++){Int t = dynmods[j].mul(dynmods[j].sub(x[j], table_const[j]), table_coeffinv[j]);for(int k=j+1; k<nmods; k++){table_const[k] = dynmods[k].muladd(t, table_coeff[j][k], table_const[k]);}res += res_coeff * FinishType(t);res_coeff *= mods[j];}return res;}std::vector<FinishType> calc(std::vector<std::vector<Int>> x){int n = x[0].size(), m = x.size();std::vector<FinishType> res(n);std::vector<Int> buf(m);for(int i=0; i<n; i++){for(int j=0; j<m; j++) buf[j] = x[j][i];res[i] = calc(buf);}return res;}};} // namespace nachianamespace nachia{template<class Modint, unsigned int nttmod> std::vector<unsigned int>PartConvolution(std::vector<Modint> A, std::vector<Modint> B){std::vector<atcoder::static_modint<nttmod>> AA(A.size());for(std::size_t i=0; i<A.size(); i++) AA[i] = A[i].val();std::vector<atcoder::static_modint<nttmod>> BB(B.size());for(std::size_t i=0; i<B.size(); i++) BB[i] = B[i].val();auto AB = atcoder::convolution(AA, BB);std::vector<unsigned int> res(AB.size());for(std::size_t i=0; i<AB.size(); i++) res[i] = AB[i].val();return res;}template<class Modint>std::vector<Modint> Convolution(std::vector<Modint> A, std::vector<Modint> B){auto Q1 = PartConvolution<Modint, 998244353>(A, B);auto Q2 = PartConvolution<Modint, 897581057>(A, B);auto Q3 = PartConvolution<Modint, 880803841>(A, B);GarnerMod<Modint> garner;garner.precalc({ 998244353, 897581057, 880803841 });return garner.calc({ Q1, Q2, Q3 });}} // namespace nachianamespace nachia{template<class Modint>Modint KthTermOfRationalGF(std::vector<Modint> denom,std::vector<Modint> numer,unsigned long long K){assert(denom.size() != 0);assert(denom.size() == numer.size());assert(denom[0].val() != 0);int n = (int)denom.size();while(K != 0){auto Qn = denom;Qn.push_back(Modint(0));for(int i=1; i<n; i+=2) Qn[i] = -Qn[i];int f = K % 2;denom = Convolution(denom, Qn);for(int i=0; i<n; i++) denom[i] = denom[i*2];denom.resize(n);numer = Convolution(numer, Qn);for(int i=0; i<n; i++) numer[i] = numer[i*2+f];numer.resize(n);K /= 2;}return numer[0] / denom[0];}// divisor of fractional representation// and first termstemplate<class Modint>Modint KthTermOfLinearRecurrence(std::vector<Modint> denom,std::vector<Modint> firstTerms,unsigned long long K){assert(denom.size() <= firstTerms.size());firstTerms.resize(denom.size());auto numer = Convolution(firstTerms, denom);numer.resize(denom.size());return KthTermOfRationalGF(std::move(denom), std::move(numer), K);}} // namespace nachiausing Modint = atcoder::modint1000000007;using i64 = long long;#define rep(i,n) for(int i=0; i<int(n); i++)const i64 INF = 1001001001001001001;using namespace std;vector<vector<int>> enumBaseState(int N){vector<int> st;vector<int> arr(N, -1);vector<vector<int>> res;auto dfs = [&](auto& rec, int p, int nx){if(p == N){res.push_back(arr);return;}arr[p] = -1;rec(rec, p+1, nx);if(p != 0 && arr[p-1] != -1){arr[p] = arr[p-1];rec(rec, p+1, nx);}else {vector<int> stbuf = st;arr[p] = nx;st.push_back(nx);rec(rec, p+1, nx+1);st.pop_back();for(int x=0; x<int(stbuf.size()); x++){st = vector(stbuf.begin(), stbuf.begin() + (x+1));arr[p] = st.back();rec(rec, p+1, nx);}st = stbuf;}};dfs(dfs, 0, 0);return res;}void refine(vector<int>& Q){vector<int> occ;for(int& q : Q) if(q != -1){int res = -1;rep(i,occ.size()) if(occ[i] == q) res = i;if(res == -1){ res = int(occ.size()); occ.push_back(q); }q = res;}}vector<vector<int>> enumNextState(vector<int> cur, int at){int n = int(cur.size());int q = cur[at];auto t0 = cur; t0[at] = -1;auto t1 = cur;vector<vector<int>> res;if(q == -1){t1[at] = 1001001001;if(at != 0 && t1[at-1] != -1) t1[at] = t1[at-1];} else {int qocc = 0;rep(i,n) if(cur[i] == q) qocc++;if(qocc == 1) t0 = vector<int>(0);int p = -1;if(at != 0 && cur[at-1] != -1) p = cur[at-1];if(p != -1) rep(i,n) if(t1[i] == p) t1[i] = q;}if(!t0.empty()){refine(t0);res.push_back(move(t0));}if(!t1.empty()){refine(t1);res.push_back(move(t1));}return res;}int main(){ios::sync_with_stdio(false); cin.tie(nullptr);int N; cin >> N;i64 L; cin >> L;auto baseState = enumBaseState(N);sort(baseState.begin(), baseState.end());vector<vector<vector<int>>> stateList(N+1);vector<vector<pair<int,int>>> transList(N);auto lbi = [&](const vector<vector<int>>& l, const vector<int>& tg) -> int {return int(lower_bound(l.begin(), l.end(), tg) - l.begin());};stateList[0] = baseState;rep(i,N){auto& dest = stateList[i+1];for(auto q : stateList[i]) for(auto r : enumNextState(q, i)){dest.push_back(r);}sort(dest.begin(), dest.end());dest.erase(unique(dest.begin(), dest.end()), dest.end());rep(j,stateList[i].size()){for(auto r : enumNextState(stateList[i][j], i)){int k = lbi(dest, r);transList[i].push_back({ j, k });}}}vector<int> sz(N+1);rep(i,N+1) sz[i] = int(stateList[i].size());rep(i,N){vector<int> F(N, -1);F[i] = 0;int j = lbi(stateList[i], F);transList[i].push_back({ j, sz[i+1] });transList[i].push_back({ sz[i], sz[i+1] });}rep(i,N+1) sz[i]++;vector<Modint> firstTerms;vector<Modint> dp(sz[0]);dp.back() = 1;dp[0] = 1;firstTerms.push_back(1);//int Z = sz[0] * 2 + 5;int Z = 1143 * 2 + 5; // according to the editorial https://yukicoder.me/problems/no/1561/editorialrep(l,Z){rep(y,N){vector<Modint> nx(sz[y+1]);for(auto [u,v] : transList[y]) nx[v] += dp[u];swap(dp, nx);}firstTerms.push_back(dp.back());}auto bm = nachia::BerlekampMassey(firstTerms);firstTerms.resize(bm.size());Modint ans = nachia::KthTermOfLinearRecurrence(bm, firstTerms, L+1) - 1;cout << ans.val() << endl;return 0;}