AtCoder Beginner Contest 321 復習 (Rust) - 獅子座じゃない人のブログ

Rustで競プロするのに慣れたりライブラリを整備したりするのも兼ねて、ABC321を解き直します。

A問題

atcoder.jp
10進での桁についての問題なので、proconio::marker::Charsを使うのが手っ取り早いでしょう。
atcoder.jp

use proconio::marker::Chars;

fn main() {
    macro_rules! input {
        ($($tt:tt)*) => {
            proconio::input!($($tt)*);
        };
    }

    input!(s:Chars);
    let n=s.len();
    let mut ans=true;
    for i in 0..n-1 {
        if s[i]<=s[i+1] {
            ans=false;
        }
    }
    ans.outputln();
}

trait Outputif {
    fn outputif<T1,T2>(self, ok: T1, bad: T2) where T1: std::fmt::Display, T2: std::fmt::Display;
    fn outputln(self);
}

impl Outputif for bool {
    fn outputif<T1,T2>(self, ok: T1, bad: T2) where T1: std::fmt::Display, T2: std::fmt::Display {
        if self {
            println!("{}",ok);
        } else {
            println!("{}",bad);
        }
    }
    fn outputln(self) {
        self.outputif("Yes", "No");
    }
}

B問題

atcoder.jp
B問題なので、場合分けよりも全探索がよいでしょう。
iter().sum()を覚えました。これくらいだと関数化しないでそのまま使ったほうが楽そうです。
atcoder.jp

fn main() {
    macro_rules! input {
        ($($tt:tt)*) => {
            proconio::input!($($tt)*);
        };
    }

    #[allow(unused_macros)]
    macro_rules! outputln {
        ($var:expr) => {
            println!("{}",$var);
        };
        ($var:expr,$($vars:expr),+) => {
            print!("{} ",$var);
            outputln!($($vars),+);
        };
    }

    input!(n:usize,x:usize,a:[usize;n-1]);
    for i in 0..=100 {
        let mut a=a.clone();
        a.push(i);
        a.sort();
        if a[1..n-1].iter().sum::<usize>()>=x {
            outputln!(i);
            return;
        }
    }
    outputln!(-1);
}

C問題

atcoder.jp
本番では条件を満たす数が1022個しかないことを利用して埋め込みましたが、よく考えたらそれをわかっていればbit全探索で余裕ですね。
atcoder.jp

fn main() {
    macro_rules! input {
        ($($tt:tt)*) => {
            proconio::input!($($tt)*);
        };
    }

    #[allow(unused_macros)]
    macro_rules! outputln {
        ($var:expr) => {
            println!("{}",$var);
        };
        ($var:expr,$($vars:expr),+) => {
            print!("{} ",$var);
            outputln!($($vars),+);
        };
    }

    input!(k:usize);
    let mut anss=Vec::<usize>::new();
    for n in 2..1024 {
        let mut ans=0;
        for i in (0..10).rev() {
            if (n>>i)%2>0 {
                ans*=10;
                ans+=i;
            }
        }
        anss.push(ans);
    }
    anss.sort();
    outputln!(anss[k-1]);
}

D問題

atcoder.jp
親の顔より見た二分探索。Rustでめぐる式をすると-1の扱いが面倒かも。
atcoder.jp

fn main() {
    macro_rules! input {
        ($($tt:tt)*) => {
            proconio::input!($($tt)*);
        };
    }

    #[allow(unused_macros)]
    macro_rules! outputln {
        ($var:expr) => {
            println!("{}",$var);
        };
        ($var:expr,$($vars:expr),+) => {
            print!("{} ",$var);
            outputln!($($vars),+);
        };
    }

    input!(n:usize,m:usize,p:usize,a:[usize;n],mut b:[usize;m]);
    b.sort();
    let bpsum=PrefixSum::construct_prefix_sum(&b);
    let mut ans=0;
    for a in a {
        let bound=binary_search(m.isize(), -1, |mid| {
            let mid=mid.usize();
            return a+b[mid]>p;
        }) as usize;
        ans+=a*bound+bpsum.calculate_partial_sum(0, bound)+p*(m-bound);
    }
    outputln!(ans);
}

trait Usize {
    fn usize(self) -> usize;
}

impl Usize for isize {
    fn usize(self) -> usize {
        self as usize
    }
}

trait Isize {
    fn isize(self) -> isize;
}

impl Isize for usize {
    fn isize(self) -> isize {
        self as isize
    }
}

#[allow(dead_code)]
fn binary_search<F>(ok: isize, bad: isize, determine: F) -> isize where F: Fn(isize) -> bool {
    let right=ok>bad;
    let mut ok=ok;
    let mut bad=bad;
    while if right {
        ok-bad>1
    } else {
        bad-ok>1
    } {
        let mid=(ok+bad)/2;
        if determine(mid) {
            ok=mid;
        } else {
            bad=mid;
        }
    }
    return ok;
}

trait PrefixSum {
    fn construct_prefix_sum(array: &Self) -> Self;
    fn calculate_partial_sum(&self, l: usize, r: usize) -> Self::Output where Self: std::ops::Index<usize>;
}

impl<T> PrefixSum for Vec<T> where T: Copy + std::ops::Add<Output=T> + std::ops::Sub<Output=T> {
    fn construct_prefix_sum(array: &Self) -> Self {
        let mut prefix_sum=vec![array[0]-array[0];array.len()+1];
        for i in 0..array.len() {
            prefix_sum[i+1]=prefix_sum[i]+array[i];
        }
        return prefix_sum;
    }
    fn calculate_partial_sum(&self, l: usize, r: usize) -> <Self as std::ops::Index<usize>>::Output {
        assert!(l < self.len() && r <= self.len());
        return self[r]-self[l];
    }
}

E問題

atcoder.jp
本番中はLCAで場合分けして求めることまではわかっていましたが、頂点番号の計算で混乱したのとF問題を中途半端に解きにいってしまったので解けず…
頂点 $v$ の子は頂点 $2v,\ 2v+1$ であり、親ないし子を見る操作がビットシフトに対応します。また、頂点 $v$ の兄弟は頂点 $v\oplus 1$ です。
これを踏まえて、 $\left|[2^dv,2^d(v+1))\cap[1,N]\cap\mathbb{N}\right|=\min\{N+1,2^d(v+1)\}-\min\{N+1,2^dv\}$ であることを使えば個数を求めることができます。
オーバーフローに気を付ける必要があります。距離 $K$ の頂点が存在しないときにそもそも計算しないようにしたり、saturating_mul関数を使ったりすればよいでしょう。
atcoder.jp

fn main() {
    macro_rules! input {
        ($($tt:tt)*) => {
            proconio::input!($($tt)*);
        };
    }

    #[allow(unused_macros)]
    macro_rules! outputln {
        ($var:expr) => {
            println!("{}",$var);
        };
        ($var:expr,$($vars:expr),+) => {
            print!("{} ",$var);
            outputln!($($vars),+);
        };
    }

    input!(t:usize);
    for _ in 0..t {
        input!(n:usize,x:usize,k:usize);
        let mut ans=0;
        for d in 0..x.blen() {
            if x.blen()-d==k {
                ans+=1;
            } else if x.blen()-d<k {
                let dist=k-(x.blen()-d+1);
                let branchdist=x.blen()-(d+1);
                if dist<=n.blen() {
                    ans+=min(n+1,(((x>>branchdist)^1)+1).saturating_mul(1<<dist))-min(n+1,((x>>branchdist)^1).saturating_mul(1<<dist));
                }
            }
        }
        if k<=n.blen() {
            ans+=min(n+1,(x+1).saturating_mul(1<<k))-min(n+1,x.saturating_mul(1<<k));
        }
        outputln!(ans);
    }
}

#[allow(dead_code)]
fn min<T>(left: T, right: T) -> T where T: std::cmp::PartialOrd {
    return if left<right {
        left
    } else {
        right
    };
}

trait Blen {
    fn blen(self) -> usize;
}

impl Blen for usize {
    fn blen(self) -> usize {
        return self.ilog2() as usize;
    }
}

F問題

atcoder.jp
解説を見て、解けなかったのを本当に悔しがった問題。戻すDPという概念を知らなかったのが理由の1つではあります。
+クエリのみの場合はただの部分和問題になります。
$\operatorname{DP}[i]$ を $K=i$ の場合の答えとすると、漸化式は $\operatorname{{DP}_{next}}[i]=\begin{cases}\operatorname{{DP}_{prev}}[i]+\operatorname{{DP}_{prev}}[i-x]\ (i\geq x)\\\operatorname{{DP}_{prev}}[i]\ (i\lt x)\end{cases}$ となります。
-クエリについて考えます。クエリの直前の $\operatorname{DP}[i]$ の値は、直前までのクエリの順番に依りません。（これは母関数（形式的冪級数）で立式すれば感覚的にもわかりやすいです。）
よって、 $x$ を直前の+クエリで追加されたものと考えて、+クエリの更新を元に戻せばよいです。
+クエリの漸化式は $\operatorname{{DP}_{next}}[i]=\begin{cases}\operatorname{{DP}_{prev}}[i]+\operatorname{{DP}_{prev}}[i-x]\ (i\geq x)\\\operatorname{{DP}_{prev}}[i]\ (i\lt x)\end{cases}$ です。これを $\operatorname{{DP}_{prev}}[i]$ について解くと、 $\operatorname{{DP}_{prev}}[i]=\begin{cases}\operatorname{{DP}_{next}}[i]-\operatorname{{DP}_{prev}}[i-x]\ (i\geq x)\\\operatorname{{DP}_{next}}[i]\ (i\lt x)\end{cases}$ となります。
$\operatorname{next}$ と $\operatorname{prev}$ を逆にすると、 $\operatorname{{DP}_{next}}[i]=\begin{cases}\operatorname{{DP}_{prev}}[i]-\operatorname{{DP}_{next}}[i-x]\ (i\geq x)\\\operatorname{{DP}_{prev}}[i]\ (i\lt x)\end{cases}$ となります。
両方のクエリについて、 $\operatorname{DP}[i]$ の更新は適切な更新順のもとで元の配列に上書きすることができます。そして、今回の問題の制約では愚直に空間計算量 $\Theta(QK)$ の配列で実装してしまうとREないしMLEになる危険性があります。
RustのVecについての可変参照と不変参照の仕様から、+=だとコンパイルエラーになり+だと実行できるのが初見殺しですが、これくらいは受け入れるのが手っ取り早いでしょう。
atcoder.jp

use ac_library::ModInt998244353;

fn main() {
    macro_rules! input {
        ($($tt:tt)*) => {
            proconio::input!($($tt)*);
        };
    }

    #[allow(unused_macros)]
    macro_rules! outputln {
        ($var:expr) => {
            println!("{}",$var);
        };
        ($var:expr,$($vars:expr),+) => {
            print!("{} ",$var);
            outputln!($($vars),+);
        };
    }

    input!(q:usize,k:usize);
    let mut dp=vec![ModInt998244353::raw(0);k+1];
    dp[0]=ModInt998244353::raw(1);
    for _ in 0..q {
        input!(o:char,a:usize);
        if o=='+' {
            for i in (a..=k).rev() {
                dp[i]=dp[i]+dp[i-a];
            }
        } else if o=='-' {
            for i in a..=k {
                dp[i]=dp[i]-dp[i-a];
            }
        }
        outputln!(dp[k]);
    }
}

G問題

atcoder.jp
まず、主客転倒で問題を言い換えます。主客転倒が苦手なのでここの理解に1日潰しました。
ケーブルの繋ぎ方の集合を $C$ とします。また、 $c\in C$ について、繋ぎ方 $c$ の場合の連結成分数 $s$ を $\sigma(c)$ とします。
すると、答えは $\displaystyle\frac{1}{M!}\sum_{s\in \sigma(C)} s\bigl\lvert\{c\ |\ \sigma(c)=s\}\bigr\rvert$ となります。
これは見るからに主客転倒で変形できる形です。変形すると $\displaystyle\frac{1}{M!}\sum_{c\in C} \sigma(c)$ となります。
ここで、 $c\in C$ を1つ固定し、 $S\subseteq \{1,2,\ldots,N\}$ をとります。そして、繋ぎ方 $c$ の場合に $S$ に属するある部品と $\{1,2,\ldots,N\}\setminus S$ に属するある部品を繋ぐケーブルがなく、かつ $S$ が1つの連結成分となるかどうかを考えます。
$S$ がある連結成分そのものであるとき、条件を満たします。 $S$ が複数の連結成分の頂点を要素として含むとき、条件を満たしません。 $S$ がある連結成分の真部分集合であるとき、必ず $S$ に属するある部品と $\{1,2,\ldots,N\}\setminus S$ に属するある部品を繋ぐケーブルがあるので条件を満たしません。
よって、写像 $p(c,S)\ (c\in C,\ S\subseteq \{1,2,\ldots,N\})$ を「繋ぎ方 $c$ の場合に $S$ に属するある部品と $\{1,2,\ldots,N\}\setminus S$ に属するある部品を繋ぐケーブルがなく、かつ $S$ が1つの連結成分となるならば $1$ 、でなければ $0$ 」と定義すると、答えは $\displaystyle\frac{1}{M!}\sum_{c\in C}\sum_{S\subseteq \{1,2,\ldots,N\}} p(c,S)$ となります。
これを $\displaystyle\sum_{S\subseteq \{1,2,\ldots,N\}}\left(\frac{1}{\lvert C\rvert} \sum_{c\in C}p(c,S)\right)$ と見ると、求めるのは $S$ が1つの連結成分となる確率の総和であると言い換えられました。
$S$ に属する部品についている赤い端点の総数を $R(S)$ 、青い端点の総数を $B(S)$ とします。
また、 $f(S)$ および $g(S)$ を、 $R(S)\neq B(S)$ ならば $f(S)=g(S)=0$ 、 $R(S)=B(S)$ ならば $f(S)$ を「 $S$ に属する部品についている端点のみを考えたときのケーブルの繋ぎ方の総数」すなわち $R(S)!$ として、 $g(S)$ を「 $S$ に属する部品についている端点のみを考えたときに $S$ が1つの連結成分となる繋ぎ方の総数」として定義します。これは、 $p(c,S)=1$ となる繋ぎ方 $c$ のうち、 $\{1,2,\ldots,N\}\setminus S$ に属する部品どうしを繋ぐケーブルのみ異なる繋ぎ方を同一視したものであるため、 $\displaystyle\frac{1}{\lvert C\rvert}\sum_{c\in C}p(c,S)=\frac{(M-R(S))!}{M!}g(S)$ が成り立ちます。
ここで、 $f(S)$ を用いて $g(S)$ を求める方法を考えます。
$S$ に $R(S)$ 本のケーブルを繋いだときにどのような連結成分に分割されるかを考えることで、 $\mathscr{P}$ を $S$ の分割全体の集合として、 $\displaystyle f(S)=\sum_{P\in\mathscr{P}}\prod_{T\in P}g(T)$ がいえます。これは $f(S)=0$ の場合も成り立ちます。
また、 $P=\{S\}$ の場合を除いて $\lvert P\rvert>1$ であり、 $P=\{S\}$ の場合は $\displaystyle\prod_{T\in P}g(T)=g(S)$ です。したがって、 $\displaystyle g(S)=f(S)-\sum_{\substack{P\in\mathscr{P}\\\lvert P\rvert>1}}\prod_{T\in P}g(T)$ と変形できます。
さらに、 $v\in S$ を1つ固定することで $\displaystyle g(S)=f(S)-\sum_{\substack{T\varsubsetneq S\\v\in T}}g(T)f(S\setminus T)$ と変形できます。
この式は部分集合を列挙するbit DPによって求めることができます。
（要素を1つとり順序を固定する部分集合列挙bit DPはABC310 D - Peaceful Teamsを思い出しますね…（トラウマ））

use ac_library::ModInt998244353;
use proconio::marker::Usize1;

fn main() {
    macro_rules! input {
        ($($tt:tt)*) => {
            proconio::input!($($tt)*);
        };
    }

    #[allow(unused_macros)]
    macro_rules! outputln {
        ($var:expr) => {
            println!("{}",$var);
        };
        ($var:expr,$($vars:expr),+) => {
            print!("{} ",$var);
            outputln!($($vars),+);
        };
    }

    input!(n:usize,m:usize,r:[Usize1;m],b:[Usize1;m]);
    let mut rcnts=vec![0;n];
    let mut bcnts=vec![0;n];
    for &r in &r {
        rcnts[r]+=1;
    }
    for &b in &b {
        bcnts[b]+=1;
    }
    let invs=ModInt998244353::construct_modint_inverses(m);
    let facts=ModInt998244353::construct_modint_facts(m);
    let factinvs=ModInt998244353::construct_modint_fact_inverses(m, &invs);
    let mut rbcnts=vec![0;1<<n];
    let mut f=vec![ModInt998244353::raw(0);1<<n];
    for s in 1..1<<n {
        let mut rcnt=0;
        let mut bcnt=0;
        for i in 0..n {
            if (s>>i)%2>0 {
                rcnt+=rcnts[i];
                bcnt+=bcnts[i];
            }
        }
        if rcnt==bcnt {
            rbcnts[s]=rcnt;
            f[s]=facts[rcnt];
        }
    }
    let mut g=vec![ModInt998244353::raw(0);1<<n];
    let mut ans=ModInt998244353::raw(0);
    for s in 1..1<<n {
        if f[s]==ModInt998244353::raw(0) {
            continue;
        }
        g[s]=f[s];
        let mut t=(s-1)&s;
        while t>=s>>s.blen()<<s.blen() {
            g[s]=g[s]-g[t]*f[s-t];
            t=(t-1)&s;
        }
        ans+=g[s]*facts[m-rbcnts[s]]*factinvs[m];
    }
    outputln!(ans);
}

trait ModIntInv where Self: Sized {
    fn construct_modint_inverses(n: usize) -> Vec<Self>;
}

impl<M> ModIntInv for ac_library::StaticModInt<M> where M: ac_library::Modulus {
    fn construct_modint_inverses(n: usize) -> Vec<Self> {
        assert!(M::HINT_VALUE_IS_PRIME);
        let mut inv=vec![Self::raw(1);n+1];
        for i in 2..=n {
            inv[i]=-inv[Self::modulus() as usize%i]*(Self::modulus() as usize/i);
        }
        return inv;
    }
}

trait ModIntFact where Self: Sized {
    fn construct_modint_facts(n: usize) -> Vec<Self>;
    fn construct_modint_fact_inverses(n: usize, invs: &Vec<Self>) -> Vec<Self>;
}

impl<M> ModIntFact for ac_library::StaticModInt<M> where M: ac_library::Modulus {
    fn construct_modint_facts(n: usize) -> Vec<Self> {
        let mut facts=vec![Self::raw(1);n+1];
        for i in 2..=n {
            facts[i]=facts[i-1]*i;
        }
        return facts;
    }
    fn construct_modint_fact_inverses(n: usize, invs: &Vec<Self>) -> Vec<Self> {
        assert!(invs.len() > n);
        let mut factinvs=vec![Self::raw(1);n+1];
        for i in 2..=n {
            factinvs[i]=factinvs[i-1]*invs[i];
        }
        return factinvs;
    }
}

trait Blen {
    fn blen(self) -> usize;
}

impl Blen for usize {
    fn blen(self) -> usize {
        return self.ilog2() as usize;
    }
}

また、和とスカラーを成分ごと、subset convolution $\displaystyle (F*G)_S=\sum_{S=T_1\sqcup T_2}F_{T_1}G_{T_2}$ を積、 $\displaystyle 1_S=\begin{cases}1\ (S=\emptyset)\\0\ (S\neq\emptyset)\end{cases}$ を乗法単位元とする集合冪級数環を考えます。
便宜上、 $f(\emptyset)=1,\ g(\emptyset)=0$ とします。
$f(S)$ の集合冪級数を $F_S$ 、 $g(S)$ の集合冪級数を $G_S$ として、 $\displaystyle f(S)=\sum_{P\in\mathscr{P}}\prod_{T\in P}g(T)$ という式は、 $\lvert P\rvert$ で場合分けして順序が異なるのを同一視することで、 $\displaystyle F_S=1+G_S+\frac{{G_S}^2}{2}+\frac{{G_S}^3}{3!}+\cdots=\exp G_S$ と表すことができます。逆に、 $G_S=\log F_S$ といえます。
ここで、 $\displaystyle\boldsymbol{F}_S=F_Sx^{\lvert S\rvert}$ および $\displaystyle\boldsymbol{G}_S=G_Sx^{\lvert S\rvert}$ を考え、それらをゼータ変換します。これをランクつきゼータ変換と呼ぶようです。
$\displaystyle\zeta\boldsymbol{F}_S=\sum_{T\subseteq S}F_Tx^{\lvert T\rvert}$ および $\displaystyle\zeta\boldsymbol{G}_S=\sum_{T\subseteq S}G_Tx^{\lvert T\rvert}$ となり、subset convolutionではなく成分ごとの意味で積をとると $\displaystyle\zeta\boldsymbol{F}_S\zeta\boldsymbol{G}_S=\sum_{T_1\subseteq S}F_{T_1}x^{\lvert T_1\rvert}\sum_{T_2\subseteq S}G_{T_2}x^{\lvert T_2\rvert}=\sum_{T_1\subseteq S}\sum_{T_2\subseteq S}F_{T_1}G_{T_2}x^{\lvert T_1\rvert+\lvert T_2\rvert}=\sum_{T\subseteq S}\sum_{T_1\cup T_2=T}F_{T_1}G_{T_2}x^{\lvert T_1\rvert+\lvert T_2\rvert}$ となります。
これをメビウス変換で戻すと、 $\displaystyle\sum_{T_1\cup T_2=S}F_{T_1}G_{T_2}x^{\lvert T_1\rvert+\lvert T_2\rvert}$ となります。ここで、 $\lvert T_1\rvert+\lvert T_2\rvert=\lvert S\rvert$ のとき、かつそのときに限り、 $T_1\sqcup T_2=S$ となります。よって、 $\lvert S\rvert$ 次の項の係数が $(F*G)_S$ となります。
メビウス変換や多項式の $\lvert S\rvert$ 次の項の係数に線形性があることを考えると、 $\displaystyle\log F_S$ は $\log\zeta\boldsymbol{F}_S$ をメビウス変換して $\lvert S\rvert$ 次の項の係数をとったものといえます。
$\zeta\boldsymbol{F}_S$ は $S$ を固定するとただの形式的冪級数になるため、 $\log\zeta\boldsymbol{F}_S$ も形式的冪級数のライブラリを整備していれば容易に求まります。
atcoder.jp

use ac_library::ModInt998244353;
use proconio::marker::Usize1;

fn main() {
    macro_rules! input {
        ($($tt:tt)*) => {
            proconio::input!($($tt)*);
        };
    }

    #[allow(unused_macros)]
    macro_rules! outputln {
        ($var:expr) => {
            println!("{}",$var);
        };
        ($var:expr,$($vars:expr),+) => {
            print!("{} ",$var);
            outputln!($($vars),+);
        };
    }

    input!(n:usize,m:usize,r:[Usize1;m],b:[Usize1;m]);
    let mut rcnts=vec![0;n];
    let mut bcnts=vec![0;n];
    for &r in &r {
        rcnts[r]+=1;
    }
    for &b in &b {
        bcnts[b]+=1;
    }
    let invs=ModInt998244353::construct_modint_inverses(m);
    let facts=ModInt998244353::construct_modint_facts(m);
    let factinvs=ModInt998244353::construct_modint_fact_inverses(m, &invs);
    let mut rbcnts=vec![0;1<<n];
    let mut f=vec![vec![ModInt998244353::raw(0);1<<n];n+1];
    for s in 0..1<<n {
        let mut rcnt=0;
        let mut bcnt=0;
        let mut bitcnt=0;
        for i in 0..n {
            if (s>>i)%2>0 {
                bitcnt+=1;
                rcnt+=rcnts[i];
                bcnt+=bcnts[i];
            }
        }
        if rcnt==bcnt {
            rbcnts[s]=rcnt;
            f[bitcnt][s]=facts[rcnt];
        }
    }
    for i in 0..=n {
        f[i].zeta_subset_transform();
    }
    let mut f=vec_range(0, 1<<n, |s| vec_range(0, n+1, |i| f[i][s]));
    for s in 0..1<<n {
        f[s].fps_log_assign();
    }
    let mut f=vec_range(0, n+1, |i| vec_range(0, 1<<n, |s| f[s][i]));
    for i in 0..=n {
        f[i].mobius_subset_transform();
    }
    let mut ans=ModInt998244353::raw(0);
    for s in 0..1<<n {
        let mut bitcnt=0;
        for i in 0..n {
            if (s>>i)%2>0 {
                bitcnt+=1;
            }
        }
        ans+=f[bitcnt][s]*facts[m-rbcnts[s]]*factinvs[m];
    }
    outputln!(ans);
}

#[allow(dead_code)]
fn vec_range<N,F,T>(begin: N, end: N, func: F) -> Vec<T> where std::ops::Range<N>: Iterator, F: Fn(<std::ops::Range<N> as Iterator>::Item) -> T {
    return (begin..end).map(|i| func(i)).collect::<Vec::<T>>();
}

trait ModIntInv where Self: Sized {
    fn construct_modint_inverses(n: usize) -> Vec<Self>;
}

impl<M> ModIntInv for ac_library::StaticModInt<M> where M: ac_library::Modulus {
    fn construct_modint_inverses(n: usize) -> Vec<Self> {
        assert!(M::HINT_VALUE_IS_PRIME);
        let mut inv=vec![Self::raw(1);n+1];
        for i in 2..=n {
            inv[i]=-inv[Self::modulus() as usize%i]*(Self::modulus() as usize/i);
        }
        return inv;
    }
}

trait ModIntFact where Self: Sized {
    fn construct_modint_facts(n: usize) -> Vec<Self>;
    fn construct_modint_fact_inverses(n: usize, invs: &Vec<Self>) -> Vec<Self>;
}

impl<M> ModIntFact for ac_library::StaticModInt<M> where M: ac_library::Modulus {
    fn construct_modint_facts(n: usize) -> Vec<Self> {
        let mut facts=vec![Self::raw(1);n+1];
        for i in 2..=n {
            facts[i]=facts[i-1]*i;
        }
        return facts;
    }
    fn construct_modint_fact_inverses(n: usize, invs: &Vec<Self>) -> Vec<Self> {
        assert!(invs.len() > n);
        let mut factinvs=vec![Self::raw(1);n+1];
        for i in 2..=n {
            factinvs[i]=factinvs[i-1]*invs[i];
        }
        return factinvs;
    }
}

trait FPS {
    fn fps_add_assign(&mut self, g: &Self);
    fn fps_add(f: &Self, g: &Self) -> Self;
    fn fps_sub_assign(&mut self, g: &Self);
    fn fps_sub(f: &Self, g: &Self) -> Self;
    fn fps_scalar_assign(&mut self, k: isize);
    fn fps_scalar(f: &Self, k: isize) -> Self;
    fn fps_mul_assign(&mut self, g: &Self);
    fn fps_mul(f: &Self, g: &Self) -> Self;
    fn fps_inv(&self) -> Self;
    fn fps_div_assign(&mut self, g: &Self);
    fn fps_div(f: &Self, g: &Self) -> Self;
    fn fps_diff_assign(&mut self);
    fn fps_diff(f: &Self) -> Self;
    fn fps_int_assign(&mut self);
    fn fps_int(f: &Self) -> Self;
    fn fps_log_assign(&mut self);
    fn fps_log(f: &Self) -> Self;
}

impl<M> FPS for Vec<ac_library::StaticModInt<M>> where M: ac_library::Modulus {
    fn fps_add_assign(&mut self, g: &Self) {
        assert!(self.len() == g.len());
        let n=self.len()-1;
        for i in 0..=n {
            self[i]+=g[i];
        }
    }
    fn fps_add(f: &Self, g: &Self) -> Self {
        assert!(f.len() == g.len());
        let mut h=f.clone();
        h.fps_add_assign(&g);
        return h;
    }
    fn fps_sub_assign(&mut self, g: &Self) {
        assert!(self.len() == g.len());
        let n=self.len()-1;
        for i in 0..=n {
            self[i]-=g[i];
        }
    }
    fn fps_sub(f: &Self, g: &Self) -> Self {
        assert!(f.len() == g.len());
        let mut h=f.clone();
        h.fps_sub_assign(&g);
        return h;
    }
    fn fps_scalar_assign(&mut self, k: isize) {
        let n=self.len()-1;
        for i in 0..=n {
            self[i]*=k;
        }
    }
    fn fps_scalar(f: &Self, k: isize) -> Self {
        let mut h=f.clone();
        h.fps_scalar_assign(k);
        return h;
    }
    fn fps_mul_assign(&mut self, g: &Self) {
        assert!(self.len() == g.len());
        let n=self.len()-1;
        let h=FPS::fps_mul(self, g);
        for i in 0..=n {
            self[i]=h[i];
        }
    }
    fn fps_mul(f: &Self, g: &Self) -> Self {
        assert!(f.len() == g.len());
        let n=f.len()-1;
        return ac_library::convolution::convolution(&f[0..=n], &g[0..=n])[0..=n].to_vec();
    }
    fn fps_inv(&self) -> Self {
        let n=self.len()-1;
        let mut inv=vec![self[0].inv();1];
        while inv.len()<=n {
            inv.resize(std::cmp::min(inv.len()*2,n+1), ac_library::StaticModInt::<M>::raw(0));
            let mut newinv=inv.clone();
            newinv.fps_scalar_assign(2);
            let mut selfclone=self.clone()[0..inv.len()].to_vec();
            selfclone.fps_mul_assign(&inv);
            selfclone.fps_mul_assign(&inv);
            newinv.fps_sub_assign(&selfclone);
            inv=newinv;
        }
        return inv;
    }
    fn fps_div_assign(&mut self, g: &Self) {
        assert!(self.len() == g.len());
        self.fps_mul_assign(&g.fps_inv());
    }
    fn fps_div(f: &Self, g: &Self) -> Self {
        assert!(f.len() == g.len());
        let mut h=f.clone();
        h.fps_div_assign(&g);
        return h;
    }
    fn fps_diff_assign(&mut self) {
        let n=self.len()-1;
        for i in 0..n {
            self[i]=self[i+1]*(i+1);
        }
    }
    fn fps_diff(f: &Self) -> Self {
        let mut h=f.clone();
        h.fps_diff_assign();
        return h;
    }
    fn fps_int_assign(&mut self) {
        let n=self.len()-1;
        for i in (1..=n).rev() {
            self[i]=self[i-1]/i;
        }
        self[0]=ac_library::StaticModInt::<M>::raw(0);
    }
    fn fps_int(f: &Self) -> Self {
        let mut h=f.clone();
        h.fps_int_assign();
        return h;
    }
    fn fps_log_assign(&mut self) {
        let n=self.len()-1;
        let h=FPS::fps_log(self);
        for i in 0..=n {
            self[i]=h[i];
        }
    }
    fn fps_log(f: &Self) -> Self {
        let mut h=f.clone();
        h.fps_diff_assign();
        h.fps_div_assign(f);
        h.fps_int_assign();
        return h;
    }
}

trait ZetaMobius {
    fn zeta_subset_transform(&mut self);
    fn mobius_subset_transform(&mut self);
}

impl<T> ZetaMobius for Vec<T> where T: Copy + std::ops::Add<Output=T> + std::ops::Sub<Output=T> {
    fn zeta_subset_transform(&mut self) {
        let n=self.len();
        let mut i=1;
        while i<n {
            for j in 0..n {
                if j&i==0 {
                    self[j|i]=self[j|i]+self[j];
                }
            }
            i<<=1;
        }
    }
    fn mobius_subset_transform(&mut self) {
        let n=self.len();
        let mut i=1;
        while i<n {
            for j in 0..n {
                if j&i==0 {
                    self[j|i]=self[j|i]-self[j];
                }
            }
            i<<=1;
        }
    }
}

自分の実装だとむしろ遅くなってしまいましたね…まあこの形式的冪級数の実装でTLEになるようなことがあればそのときに直しましょう…