解説

数列辞典にかけたい気持ちをぐっとこらえて考察する。

玉の分配を考えてみると、N個のうち4つはもう分配が決まっている。
次数3の玉が1つ。そこから3路あるが、それぞれ1つずつ玉を置く。
残りのN-4を3路に分配する。
N-4を3つに分けるが、同じ数で構成される組み合わせは排除したい。
これをうまくやる方法であるが、以下を満たすように組み合わせを求める。

a + b + c = N - 4
a ≦ b ≦ c

難しくないか？？
何かを全探索で計算することはできなさそう。
こういう数学系は場合分けか？式変形か？

a=b=cの場合は一通りでN-4が3で割り切れるか見ればいいけど、下の2つかぶっているときで見れるので特にいらない。
a,b,cのうち2つがかぶっているときは、あと一つはN-4-2*(被った数)で一意に定まるので、被った数を数えればいい。
これは、(N-4)/2+1通りありそう（+1は0の分）。

全部違うときが問題で、わからん。
解説を見ると、式変形してる。
うんうん。

最小値aを決めると、b,cにもa+1をあらかじめ割り当てておく。
すると、残りはN-(3a+6)となるので、これを2つに分ける。
例えば、残りが4ならば(0,4),(1,3)の2通り、残りが5ならば(0,5),(1,4),(2,3)の3通りとなる。
つまり、切り上げが組み合わせになる。
aの範囲は0～(N-4-3)/3である。-3はa,a+1,a+2が最小構成であるため。
ma = (N-4-3)/3としておこう。

sum{a=0..ma} ceil*1 / 2)
が答え。
これは、ceilが扱いにくいので、aの偶奇で計算を分ける。
aが偶数なら、a=2Aとすると
sum{A=0..floor(ma/2)} ceil*2 / 2)
= sum{A=0..floor(ma/2)} ( ceil*3 / 2)
= sum{A=0..floor((ma-1)/2)} ( ceil((N - 9) / 2) - 3A )
= ceil((N-9) / 2) * (floor((ma-1)/2) + 1) - 3 * sum{A=0..floor((ma-1)/2)} A

ceilについてはNの偶奇で分けてやればいい。
sumについては等差数列の総和公式を使おう。
全然式が合わんくてきつかった

ll N;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;

    mint ans = 0;
    ans += (N - 4) / 2 + 1;

    ll ma = (N - 4 - 3) / 3;
    if (0 <= ma) {
        ll even_ma = ma / 2;

        ans += mint(N / 2 - 3) * mint(even_ma + 1);
        if (N % 2) ans += mint(even_ma + 1);

        ans -= mint(3) * (even_ma + 1) / 2 * even_ma;
    }

    if (1 <= ma) {
        ll odd_ma = (ma-1) / 2;

        ans += mint((N - 9) / 2) * mint(odd_ma + 1);
        if ((N - 9) % 2) ans += mint(odd_ma + 1);

        ans -= mint(3) * (odd_ma + 1) / 2 * odd_ma;
    }

    cout << ans << endl;
}

*1:N-(3a+6

*2:N-(6A+6

*3:N / 2 - 3) - 3A )
= ceil(N / 2 - 3) * (floor(ma/2) + 1) - 3 * sum{A=0..floor(ma/2)} A

aが奇数なら、a=2A+1とすると
sum{A=0..floor((ma-1)/2)} ceil((N-(3(2A+1)+6

はまやんはまやんはまやん

hamayanhamayan's blog

Y字グラフ [yukicoder 906]

解説