結果

問題 No.1561 connect x connect
ユーザー 👑 NachiaNachia
提出日時 2024-05-28 03:29:49
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 421 ms / 2,000 ms
コード長 10,935 bytes
コンパイル時間 5,068 ms
コンパイル使用メモリ 183,596 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-12-20 20:38:17
合計ジャッジ時間 10,231 ms
ジャッジサーバーID
(参考情報)
judge3 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

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

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <atcoder/modint>
// (edited) Nyaan's library
namespace nachia{
// output : denominator of rational gf
template <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 nachia
namespace nachia{
class DynamicModSupplier{
using u64 = unsigned long long;
using Int = unsigned int;
private:
u64 imod;
Int mod;
// atcoder library
u64 reduce2(u64 z) const noexcept {
// atcoder library
#ifdef _MSC_VER
u64 x; _umul128(z, im, &x);
#else
using u128 = unsigned __int128;
u64 x = (u64)(((u128)(z)*imod) >> 64);
#endif
return 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 nachia
namespace 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 nachia
namespace 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 nachia
namespace 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 terms
template<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 nachia
using 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;
rep(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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0