問題概要

以下の3つの条件を満たす有向木を数え上げてください。

最も長い（有向）パスの長さが $n$
すべての頂点の次数（=入次数+出次数）が $3$ 以下
ある頂点対が friends であることを、2頂点を結ぶパスが存在することとして定義したとき、すべての friends でない頂点対 $(u,v)$ について、ある頂点 $w$ が存在し、 $(u,w)$ と $(v,w)$ がそれぞれ friends となる

解法

準備

説明のため、長さ $n$ のパスを1つ固定し、先頭（パスがスタートする頂点）から順に $0,1,2,\dots,n$ と番号を振っておきます。このもとで条件を整理してみます。

まず1つ目の条件は、この長さ $n$ のパスがそれ以上伸ばせないということに相当します。つまり、番号 $0$ の頂点は入次数0で、番号 $n$ の頂点は出次数0です。

2つ目の条件からは、固定したパスから辺を生やすとき、番号 $1,2,\dots,n-1$ の頂点からは1本ずつしか生やせないことが言えます。

3つ目の条件について、パスに合流する辺とパスから分岐する辺を考えてみます。例えば、番号 $2$ の頂点に合流する辺と番号 $1$ の頂点から分岐する辺があったとき、それぞれの先の頂点は当然 friends ではありませんし、さらに3つ目の条件を満たすような頂点 $w$ も存在しません。より一般に、ある値 $L$ が存在して、 $L$ 未満の番号の頂点にはパスに合流する辺のみが、 $L$ 以上の番号の頂点にはパスから分岐する辺のみが生えることになります。

下の図のようなイメージです。

f:id:kotatsugame:20210525080030p:plain

さて、パスに合流する辺とパスから分岐する辺は、向きこそ異なるものの、パターンとしては同一のものになります。よって、とりあえずパスに合流する辺として考えてみることにします。具体的には、番号 $i$ までのパスに合流する辺をくっつける場合の数 $v_i$ を求めます。 $v_0=1$ です。

番号 $i$ の頂点から辺が生えていない場合は $v_{i-1}$ 通りあります。生えている場合は、その先にあるパスの長さによって、現在固定しているパスとの区別がつくかどうかを考える必要があります。パスの長さが $i-2$ 以下のときは、区別がつくため、固定しているパスへの辺の生やし方と掛け合わせて $v_{i-1}\sum_{j=0}^{i-2}v_j$ 通りあります。区別がつかない場合は重複組み合わせになり、 ${}_{v_{i-1}}\mathrm{H}_2$ 通りです。合わせると以下のような式が成り立ちます。

$\displaystyle v_i=v_{i-1}+{}_{v_{i-1}}\mathrm{H}_2+v_{i-1}\sum_{j=0}^{i-2}v_j$

特に、番号 $i$ の頂点から辺が生えている場合の数は $v_i-v_{i-1}$ となります。

パターン1

パスに合流するような辺とパスから分岐する辺の両方が存在するようなグラフを数え上げます。この際、番号 $0$ の頂点と番号 $n$ の頂点は次数が1となることに注意しておきます。

パスに合流するような辺がつながっている頂点のうち、最も番号が大きいものの番号を $l\ge 1$ とします。対応して、パスから分岐するような辺がつながっている頂点のうち、最も番号が小さいものの番号を $l\lt r\le n-1$ とします。そのようなグラフの場合の数は $(v_l-v_{l-1})(v_{n-r}-v_{n-r-1})$ となります。

このままでも累積和を取ることによって計算できますが、もう少し進めてみます。 $l$ を固定したとき、 $l\lt r\le n-1$ について $v_{n-r}-v_{n-r-1}$ の和を求めます。

$\displaystyle \sum_{r=l+1}^{n-1}(v_{n-r}-v_{n-r-1})=(v_{n-l-1}-v_{n-l-2})+(v_{n-l-2}-v_{n-l-3})+\dots+(v_1-v_0)=v_{n-l-1}-1$

意味としては、 $n-l-1$ 番目までの頂点に辺を生やす場合の数から、1本も辺を生やさない場合を引いたことになります。

パターン2

パスに合流する辺しか存在しない場合を考えます。パスから分岐する辺しか存在しない場合もパターンとしては等しいため、全く同じ値になることがわかります。番号 $n$ の頂点の次数（=入次数）は1から3の3通りありますが、このうち1または2の場合は、合わせて以前に計算した $v_n$ となります。よって次数が3の場合のみを新たに考えればよいです。

3本の辺それぞれが区別できるかどうかを考えます。これは、その先にあるパスの長さによって決まるのでした。パスを1つ固定しているので、少なくとも1本には長さ $n-1$ のパス（辺の生やし方 $v_{n-1}$ 通り）がつながっています。その他の2本について、その先のパスの長さがどうなっているかで場合分けします。

すべて $n-1$ の場合

どれも区別できない可能性があります。重複組み合わせを用いて ${}_{v_{n-1}} \mathrm{H}_3$ 通りと書けます。

1本が $n-1$ の場合

もう1本についての場合の数は $\sum_{i=0}^{n-2}v_i$ なので、 ${}_{v_{n-1}} \mathrm{H}_2 \sum_{i=0}^{n-2}v_i$ 通りと書けます。

どれも $n-1$ 未満の場合

長いほうの長さが $i$ であるとき、短いほうの長さが $i$ かそれ未満かで式が異なり、 ${}_{v_i} \mathrm{H}_2+v_i\sum_{j=0}^{i-1}v_j=v_{i+1}-v_i$ 通りと書けます。あとは $0\le i\lt n-1$ についてこれの和をとればよく、最後に長さ $n-1$ のパスの場合の数を掛けて $v_{n-1}\sum_{i=0}^{n-2}(v_{i+1}-v_i)=v_{n-1}(v_{n-1}-v_0)=v_{n-1}(v_{n-1}-1)$ 通りになります。

最後に、パスから分岐する辺しかない場合のために値を2倍するのですが、この際パスに一切辺が生えていない状態を2回カウントしてしまっているため、1引く必要があります。

実装

ACLのmodintを使用しています。

https://codeforces.com/contest/1528/submission/117271924

#include<iostream>
#include<atcoder/modint>
using namespace std;
using mint=atcoder::modint998244353;
mint H(mint a,int k)
{
    mint ret=1;
    for(int i=1;i<=k;i++)ret=ret*(a+i-1)/i;
    return ret;
}
int n;
mint v[1<<20];
int main()
{
    cin>>n;
    v[0]=1;
    mint sv=0;
    for(int i=1;i<=n;i++)
    {
        v[i]=v[i-1]+H(v[i-1],2)+v[i-1]*sv;
        sv+=v[i-1];
    }
    mint ans1=0,ans2=0;
    for(int l=1;l<n-1;l++)
    {
        ans1+=(v[l]-v[l-1])*(v[n-l-1]-1);
    }
    ans2+=v[n];
    ans2+=H(v[n-1],3);
    ans2+=H(v[n-1],2)*(sv-v[n-1]);
    ans2+=v[n-1]*(v[n-1]-1);
    cout<<(ans1+ans2*2-1).val()<<endl;
}

kotatsugameの日記

Codeforces Round #722 Div.1 E Mashtali and Hagh Trees

問題概要

解法

準備

パターン1

パターン2

実装