Educational Codeforces Round #107 E - Colorings and Dominoes

コンテスト中全然わからなかった． かなり多くの人が通していてショックを受けたので記事にしました．

冷静になって翌日に考察しなおしたら解けたけど，このぐらいはサラっと考察したいところ．

問題概要

$ N $ 行 $ M $ 列のボードが与えられる．ボードの各マスは黒か白で塗られている． 白いマスを赤か青に塗ることを考える． ここで，以下のようにドミノ（ $ 1 \times 2 $ のパーツ）を置くことを考える．

• 横に連続した $ 2 $ マスが両方とも赤なら，その $ 2 $ マスにまたがってドミノを置ける．
• 縦に連続した $ 2 $ マスが両方とも青なら，その $ 2 $ マスにまたがってドミノを置ける．
• $ 1 $ つのマスに $ 2 $ つ以上のドミノを重ねて置くことはできない．

塗った後の盤面の価値を，その盤面に置けるドミノの数の最大値とする． 全ての塗り方に対して，盤面の価値の総和を求めよ．

ただし答えが大きくなる可能性があるので， $ 998244353 $ で割った余りを答えよ．

制約

• $ 1 \leq N,M \leq 3 \times 10^{5} $
• $ NM \leq 3 \times 10^{5} $

考察

当然ながら白のマスの塗り方を全て試すのは最悪 $ O(2^{NM}) $ の時間計算量がかかるので無理である．

こういう問題は塗り分けた盤面単位で値を足していくという方針は難しく，筋が悪い． ドミノ $ 1 $ つの価値の総和に対する寄与を考える．

まず重複など何も考えずにドミノの寄与を考える． ドミノを置く隣接 $ 2 $ マスを全探索する．両方とも白いマスでなくてはならない． 下の図の左のように隣接 $ 2 $ マスに着目してやると，その $ 2 $ マスは所定の色で塗られることが確定する． その他の白いマスはそれぞれ $ 2 $ 通りの塗り方が存在するため，図の例なら $ 2^{5} $ 通りの塗り分けの時にその位置にドミノを置けることがわかる．

これを足し上げることで求められるのはすべての白マスの塗り分け方に対してすべてのドミノの置き方を考えたときに置いたドミノの総和である． この値はほぼほぼ求める価値の総和と一致しない．というのも，$ 1 $ つの塗り分けに対して $ 2 $ 通り以上のドミノの置き方がある時に重複して数えてしまうためである．

左の 2 つのドミノの寄与を単純に考えると，右の盤面に対して 2 通り数えることになる

重複，すなわち $ 1 $ つの塗り分けに対して複数のドミノの置き方がある場合について考える． ある塗り分けられた盤面に対して，横向きにドミノを置いていたとする． 同じ領域を使って縦向きのドミノに置き換えるということは当然不可能である． これは，赤に塗られた領域には縦向きのドミノを置くことができないためである． したがって，横向きのドミノの置き方を考える時はそのドミノが置かれている行のみについて考えれば良い． さらに言えば間に黒マスが挟まっても，その前後は配置について影響を及ぼさないため連続する白マスの列について考えれば良い． これは縦のドミノと列についても同じことが言える．

以上のことから $ 1 $ 次元の問題について考えれば良いことがわかる． 重複なく数え上げるテクニックの $ 1 $ つとして条件を付けて数え上げることで重複を防ぐというものがある． これはどうやら競技プログラミングの数え上げ典型らしく，しばしば問われる． よくあるのは（というか殆どこれな気がするが），最左のもののみを数え上げるというものだ．

今回の問題では，左から（上から）貪欲にドミノを配置する置き方をするときのドミノの寄与のみを考えることにする． 例えば，下の図の例では赤く塗ったマスが $ 5 $ つ並んでいるためドミノの配置は複数存在するが，太線のようなドミノの置き方しかしないものと考える．

横向きのドミノ 2 個の置き方は 3 通りあるが左から貪欲に詰めたときのドミノの寄与だけを考える

連続する白いマスの列について左から $ 1, 2, \cdots $ のように番号を振って考える． $ i-1 $ と $ i $ 番目のマスにまたがって置かれるドミノに着目したときに，そのドミノの寄与について考える． 貪欲に左から詰めたときの寄与のみを考えるため，ドミノのすぐ左側には偶数個（$ 0 $ 個も可能）連続している赤いマスがなくてはならない．それ以外はどちらの色で塗っても構わない． このような塗り方を愚直に計算すると，各ドミノに対して左側の赤の個数を全探索するため，全体で $ O(M^{2}) $ （縦の場合は $ O(N^{2}) $ ）かかってしまい今回の制約では間に合わない．

着目するドミノと数え上げるパターン

しかしよく考えると，すぐ左の赤の個数が $ 2 $ 個以上の場合については，$ i-3 $ と $ i-2 $ にまたがるドミノの寄与を計算する際に求めている． 具体的には，左の赤の個数が $ k $ 個の場合は $ i-3 $ と $ i-2 $ にまたがるドミノにおける左の赤の個数が $ k-2 $ 個の時に対応する．

よって遷移が $ O(1) $ の DP で求めることができ，すべての寄与を最悪 $ O(N) $ や $ O(M) $ で計算することができる． 注意点としては，他の行や列の白マスも自由に塗っていいことを考慮しながら $ 1 $ つ $ 1 $ つのドミノの寄与を足し上げていくことにより，プログラム全体で $ O(NM) $ で価値の総和を計算することができた．

個人的ポイント

• この手の盤面を決めて盤面のスコアを足し上げる問題はそのままでは筋が悪い．
  • スコアに寄与する単位（今回はドミノ）について，その寄与を考えると良い．
• 問題文を冷静に読むと同じ行/列，さらに連続する白マスの列についてのみ考えれば良い．
• 重複を防ぐテクニックとして，条件付きのものを数え上げるというものがある．
  • 最左の要素，最左のマッチング…などなどを考えることが多い．
  • ABC171 F - Strivore とか ARC114 C - Sequence Scores などよく出題されている．
• $ 2 $ 個ずつ伸びていくような数え上げは，DP で次元が落ちる．
  • 別に偶数個ずつではなく一般の自然数 $ N $ にしても同じ（だと思う）．

ソースコード

提出URL

▶ソースコードを展開

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,n,m) for(int i=(int)(n); i<=(int)(m); i++)
#define RFOR(i,n,m) for(int i=(int)(n); i>=(int)(m); i--)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define RITR(x,c) for(__typeof(c.rbegin()) x=c.rbegin();x!=c.rend();x++)
#define setp(n) fixed << setprecision(n)

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll,ll>
#define pi pair<int,int>

#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define ins insert

#define debug(a) cerr<<(a)<<endl
#define dbrep(a,n) rep(_i,n) cerr<<(a[_i])<<" "; cerr<<endl
#define dbrep2(a,n,m) rep(_i,n){rep(_j,m) cerr<<(a[_i][_j])<<" "; cerr<<endl;}

using namespace std;

template<class A, class B>
ostream &operator<<(ostream &os, const pair<A,B> &p){return os<<"("<<p.fi<<","<<p.se<<")";}
template<class A, class B>
istream &operator>>(istream &is, pair<A,B> &p){return is>>p.fi>>p.se;}

template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}
template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

//-------------------------------------------------
//--ModInt
//-------------------------------------------------
const uint_fast64_t MOD = 998244353;

class mint
{
private:
    using Value = uint_fast64_t;
    Value n;
public:
    mint():n(0){}
    mint(int_fast64_t _n):n(_n<0 ? MOD-(-_n)%MOD : _n%MOD){}
    mint(const mint &m):n(m.n){}

    friend ostream& operator<<(ostream &os, const mint &a){
        return os << a.n;
    }
    friend istream& operator>>(istream &is, mint &a){
        Value temp; is>>temp;
        a = mint(temp);
        return is;
    }

    mint& operator+=(const mint &m){n+=m.n; n=(n<MOD)?n:n-MOD; return *this;}
    mint& operator-=(const mint &m){n+=MOD-m.n; n=(n<MOD)?n:n-MOD; return *this;}
    mint& operator*=(const mint &m){n=n*m.n%MOD; return *this;}
    mint& operator/=(const mint &m){return *this*=m.inv();}
    mint& operator++(){return *this+=1;}
    mint& operator--(){return *this-=1;}

    mint operator+(const mint &m) const {return mint(*this)+=m;}
    mint operator-(const mint &m) const {return mint(*this)-=m;}
    mint operator*(const mint &m) const {return mint(*this)*=m;}
    mint operator/(const mint &m) const {return mint(*this)/=m;}
    mint operator++(int){mint t(*this); *this+=1; return t;}
    mint operator--(int){mint t(*this); *this-=1; return t;}

    bool operator==(const mint &m) const {return n==m.n;}
    bool operator!=(const mint &m) const {return n!=m.n;}
    mint operator-() const {return mint(MOD-n);}

    mint pow(Value b) const {
        mint ret(1), m(*this);
        while(b){
            if (b & 1) ret*=m;
            m*=m;
            b>>=1;
        }
        return ret;
    }

    mint inv() const {return pow(MOD-2);}
};

//-------------------------------------------------

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N,M; cin>>N>>M;
    vector<string> f(N);
    rep(i,N) cin>>f[i];

    int w=0;
    rep(i,N)rep(j,M){
        if (f[i][j]=='o') w++;
    }

    vector<mint> d2(N*M+1);
    d2[0]=1;
    rep(i,N*M) d2[i+1]=d2[i]*2;
    
    vector<mint> dp(max(N,M)+1);
    FOR(i,2,max(N,M)){
        dp[i] = dp[i-2]+d2[max(i-3,0)];
    }
    
    mint ans=0;
    rep(i,N){
        const auto &row = f[i];
        int cnt=0;
        rep(j,M){
            if (row[j]=='o') cnt++;
            else cnt=0;
            ans+=dp[cnt]*d2[w-cnt];
        }
    }
    rep(j,M){
        int cnt=0;
        rep(i,N){
            if (f[i][j]=='o') cnt++;
            else cnt=0;
            ans+=dp[cnt]*d2[w-cnt];
        }
    }
    cout<<ans<<"\n";
    return 0;
}

Educational Codeforces Round #107 (Div.2) D - Min Cost String

この問題かなり難しく感じました． よく観察すると典型に落とし込めるということで，記事にしました．

問題概要

文字列 $ S = S_1S_2 \cdots S_{|S|} $ のコストを次のように定義する．

• $ 1 \leq i < j \leq |S| $ のようなペア $ (i,j) $ であって， $ S_i = S_j $ かつ $ S _ {i+1}=S _ {j+1} $ であるようなものの数

英小文字の最初の $ K $ 文字のみで構成される長さ $ N $ の文字列でコストが最小のものを $ 1 $ つ出力せよ．

制約

• $ 1 \leq N \leq 2 \times 10^{5} $
• $ 1 \leq K \leq 26 $

考察

まず，長さ $ N $ 文字列には $ 2 $ 文字の連続する部分文字列が（重複を含めて） $ N-1 $ 個ある． 文字列のコストはこの $ N-1 $ 個の部分列の等しいものの組み合わせの総和と等しい． よってコストを $ cost $ ，連続する部分文字列 $ ij $ の数を $ cnt_{i,j} $ として，次の式が成り立つ．

\begin{align} cost &= \sum _ {i=\rm{'a'}} ^ {\rm{'z'}} \sum _ {j=\rm{'a'}} ^ {\rm{'z'}} \frac {(cnt _ {i,j})(cnt _ {i,j}-1)}{2} \\ &= \frac{1}{2} \left\{ \sum _ {i=\rm{'a'}} ^ {\rm{'z'}} \sum _ {j=\rm{'a'}} ^ {\rm{'z'}} (cnt _ {i,j})^{2} - \sum _ {i=\rm{'a'}} ^ {\rm{'z'}} \sum _ {j=\rm{'a'}} ^ {\rm{'z'}} cnt _ {i,j} \right\} \\ &= \frac{1}{2} \left\{ \sum _ {i=\rm{'a'}} ^ {\rm{'z'}} \sum _ {j=\rm{'a'}} ^ {\rm{'z'}} (cnt _ {i,j})^{2} - (N-1) \right\} \hspace{15pt} \left(\because \sum _ {i=\rm{'a'}} ^ {\rm{'z'}} \sum _ {j=\rm{'a'}} ^ {\rm{'z'}} cnt _ {i,j} = N-1\right) \end{align}

上の式で変数は $ cnt_{i,j} $ のみであるから，$ cost $ を最小化するには $ \sum _ {i=\rm{'a'}} ^ {\rm{'z'}} \sum _ {j=\rm{'a'}} ^ {\rm{'z'}} (cnt _ {i,j})^{2} $ を最小化すればよいことがわかる．

$ \sum _ {i=\rm{'a'}} ^ {\rm{'z'}} \sum _ {j=\rm{'a'}} ^ {\rm{'z'}} cnt _ {i,j} = N-1 $ であるから，和が一定の数列の二乗和を最小化すればよいことが分かり，これは（できるだけ）等しくなるように分配すれば良い（証明略）．

※実数の場合はコーシー・シュワルツの不等式で簡単に証明できる．

したがって，なるべく $ 2 $ 文字の連続部分文字列が被らないように文字列を構築していくことを考えればよい．この連続部分文字列は $ K^{2} $ 種類存在する．そして実は $ K^{2} $ 種類の $ 2 $ 文字連続部分文字列を全て含む 長さ $ K^{2}+1 $ の文字列を構成することが可能である．

ここでアルファベットを頂点に対応させたグラフを考える． すると $ 2 $ 文字の連続部分文字列は辺に対応し，文字列はこのグラフ上の歩道に対応する．

K=4 の時のグラフ

任意の辺を 1 回ずつ通る歩道をグルグル回れば，連続部分文字列の分布を最もフラットにできる． このような歩道は，オイラー路（Eulerian trail）の定義そのものである．

オイラー路を持つためには，すべての頂点の入次数と出次数が等しくなければならない． このグラフは，すべての頂点間に 1 本ずつ有効辺が伸びているため明らかに条件を満たしている． オイラー路の構築はグラフのサイズを $ M $ として， DFS で $ O(M) $ で構築が可能である（隣接行列のためのメモリの確保は別に考えています）．

オイラー路に対応する文字列を構築したら，長さ $ N $ に達するまで連結することで答えが得られる． 全体で $ O(N+K^{2}) $ で答えを得ることができる．

別解（コンテスト中の解法）

コンテスト中には全然オイラー路が見えなかったが長さ $ 2 $ の連続部分文字列 $ K^{2} $ 種類が被らない文字列を規則的に構築するための観察をしていた．

• $ K=1 $ の時は自明に "aa"
• $ K \geq 2 $ の時は $ K - 1 $ の時の文字列に $ K $ 番目のアルファベットを含む $ 2 $ 文字の文字列を含むようにすれば良い．
  • $ K=2 $ の時 "bb"+"aa"+"b"
  • $ K=3 $ の時 "cc"+"bbaab"+"cac"

上記のように再帰的に構築可能である．

個人的ポイント

• 要素を頂点，ペアを辺に対応させてグラフの問題に落とすことは多々ある．
• オイラー路は $ O(M) $ で構成可能．
  • 厳密には隣接行列を連想配列でするなどにより log が付いたりしそう．
• $ 1 $ パラメータの構築は，$ 1 $ つ前のものから簡単な手続きで作れることが多い．
  • 再帰的な構築を考える．

参考資料

競プロにおけるオイラー路とその応用について - Learning Algorithms

• これを見てオイラー路を構成を勉強しました．

ソースコード

オイラー路解

再帰構築解

▶ソースコードを展開

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,n,m) for(int i=(int)(n); i<=(int)(m); i++)
#define RFOR(i,n,m) for(int i=(int)(n); i>=(int)(m); i--)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define RITR(x,c) for(__typeof(c.rbegin()) x=c.rbegin();x!=c.rend();x++)
#define setp(n) fixed << setprecision(n)

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll,ll>
#define pi pair<int,int>

#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define ins insert

#define debug(a) cerr<<(a)<<endl
#define dbrep(a,n) rep(_i,n) cerr<<(a[_i])<<" "; cerr<<endl
#define dbrep2(a,n,m) rep(_i,n){rep(_j,m) cerr<<(a[_i][_j])<<" "; cerr<<endl;}

using namespace std;

template<class A, class B>
ostream &operator<<(ostream &os, const pair<A,B> &p){return os<<"("<<p.fi<<","<<p.se<<")";}
template<class A, class B>
istream &operator>>(istream &is, pair<A,B> &p){return is>>p.fi>>p.se;}

template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}
template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

/* Some Libraries */

//-------------------------------------------------

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N,K; cin>>N>>K;
    string S="aa";
    rep(i,K-1){
        char ch=(char)(i+'a'+1);
        string pref=""; pref+=ch; pref+=ch;
        string suff="";
        rep(j,i*2+1){
            if (j&1){
                suff+=(char)('a'+j/2);
            }else{
                suff+=ch;
            }
        }
        S=pref+S+suff;
    }
    while(S.size()<N) S+=S.substr(1);
    cout<<S.substr(0,N)<<"\n";
    return 0;
}

AtCoder Regular Contest B - 高橋ノルム君

見た目や diff 以上に手間取ってしまったので記録．

問題概要

$ N $ 個の点の座標 $ (x_i, y_i) $ と $ N $ 個の正整数定数 $ c_i $ が与えられる． $ i $ 番目の点が座標 $ (X,Y) $ に移動するには $ c_i * \max({|x_i-X|, |y_i-Y|}) $ 秒を要する．

全ての点が同時に動き始めて $ 1 $ つの点に集まるのにかかる最小の時間を求めよ．

制約

• $ 2 \leq N \leq 1000 $
• $ -10^{5} \leq x_i, y_i \leq 10^{5} $
• $ 1 \leq c_i \leq 1000 $

考察

集まる先の点を最適化して最小の時間を求めることは難しい．

というのも，$ c_i $ という係数があり単純な最適化は難しく単峰性もないため三分探索もできない．

というわけで，こういう時の伝家の宝刀であるところの答え決め打ち二分探索をする． そもそも問題自体が max-min 問題なので二分探索を疑った，という方針の人も多そう．

$ t $ 秒で全ての点が $ 1 $ つの点に集まれるかどうかを判定する問題を考えることになる． $ i $ 番目の点が動ける $ x $ 座標の区間を考えると， $ [x_i-t/c, x_i+t/c] $ となる． $ y $ 座標に関しても同様である． すなわち，各点の $ t $ 秒の可動域は正方形の領域になっている．

したがって，判定問題は「 $ N $ 個の正方形領域の全てに含まれる点が存在するか」と言い換えられる． これは， $ x $ 座標と $ y $ 座標を独立に考えて動ける区間の共通部分を取っていけば良い． この実装は区間 $ [l,r] $ を「$ l $ 以上 かつ $ r $ 以下」という制約に置き換えると簡単な最大最小の更新でできる．

以上により判定問題を $ O(N) $ で解くことができた． 二分探索とあわせて $ O(N log \, t_{max}) $ でこの問題を解けた．

余談

制約が $ 2 \leq N \leq 1000 $ なので，判定が $ O(N^{2}) $ の解法が存在するのではないかと考えた． よく考えると，正方形領域 $ A $ と $ B $ ， $ B $ と $ C $ ， $ C $ と $ A $ が共通部分があるときに $ A, B, C $ の共通部分は必ず存在する． このことは正方形領域が $ x,y $ 座標軸に平行な辺しか持たないことからわかる．

したがって，全ての正方形領域の組に対して共通部分が存在するかチェックすれば良い． これで $ O(N^{2}) $ で判定問題を解くことができた．

個人的ポイント

• 係数が付いていたりすると距離っぽい max-min 問題を解くのは難しい．
  • 答えを決めうって二分探索をすることで大体うまくいく．
  • Yakiniku Optimization Problem もこれだった気がする．
• 区間の共通部分を求める実装は，最大最小の更新で行える．
  • 存在しない場合 最大 < 最小 になるので判定も楽．

ソースコード

提出URL

▶ソースコードを展開

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
using lf = long double;
using P = pair<lf,lf>;

int main()
{
    int N; scanf("%d",&N);
    vector<int> x(N),y(N),c(N);
    for(int i=0; i<N; i++)
        scanf("%d%d%d",&x[i],&y[i],&c[i]);
    
    lf lo=0, hi=1e9;
    for(int q=0; q<70; q++){
        lf mid = (lo+hi)/2;

        P xlim(-1e5,1e5);
        P ylim(-1e5,1e5);

        auto merge = [](P p, P q){
            lf r1 = max(p.first,q.first);
            lf r2 = min(p.second,q.second);
            return P(r1,r2);
        };

        for(int i=0; i<N; i++){
            P xr(x[i]-mid/c[i], x[i]+mid/c[i]);
            P yr(y[i]-mid/c[i], y[i]+mid/c[i]);
            xlim = merge(xlim,xr);
            ylim = merge(ylim,yr);
        }
        bool ok=true;
        if (xlim.first>xlim.second) ok=false;
        if (ylim.first>ylim.second) ok=false;
        (ok)?(hi=mid):(lo=mid);
    }
    printf("%.15Lf\n", hi);
    return 0;
}

AtCoder Beginner Contest 026 D - 高橋君ボール1号

簡単ですが，なぜか詰まった覚えがあるので記事にしておくことに．

問題概要

正の整数 $ A,\, B,\, C $ と，以下の関数 $ f(t) $ が与えられる．

• $ f(t) = At + B \sin{C \pi t} $

$ t \geq 0 $ かつ $ f(t) = 100 $ であるような $ t $ を $ 1 $ つ見つけよ．

制約

• $ 1 \leq A, B, C \leq 100 $

考察

この問題文は，求める $ t $ はあるものとして書かれているが念のため確認をする． 制約から $$ -100 \leq B \sin{C \pi t} \leq 100 $$ は明らかである．一方で $ At $ は $ t $ が大きくなれば無限に大きくなる． $ f(0) = 0 $ であり $ f(t) $ は明らかに連続関数であるから，中間値の定理より必ず $ 1 $ つは解が存在する．

具体的には制約から $ f(200) \geq 100 $ であることが保証されるので，区間 $ [0,200] $ に解が存在することが分かる． 中間値の定理で存在が保証される解を $ 1 $ つ見つけるアルゴリズムとして，二分法が知られる． 二分探索と同様の手法で，解の存在範囲を狭めていくアルゴリズム (https://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%B3%95)．

$ f(t) $ の計算自体は高速に行うことが出来るので，十分収束する回数二分法を回すことで正解が得られる．

個人的ポイント

• 連続関数 $ f(x) $ に対して $ f(x) = const. $ みたいな方程式の解を $ 1 $ つ求めるときは二分法．
  • 最小のものとかになるとまた話は変わってくる．
• 今回は常に解が存在したが，しない場合があるような制約で出題されることもありそう．
  • しっかりと存在しない条件を確認する．

ソースコード

提出URL

▶ソースコードを展開

#include <iostream>
#include <cmath>

using namespace std;
using lf = long double;

constexpr lf PI = 3.14159265358979L;

int main()
{
    int A,B,C; scanf("%d%d%d",&A,&B,&C);
    auto f = [&](lf t){
        return A*t + B*sin(C*PI*t);
    };
    lf lo=0, hi=201;
    for(int i=0; i<80; i++){
        lf mid = (lo+hi)/2;
        (f(mid)<(lf)100)?(lo=mid):(hi=mid);
    }
    printf("%.15Lf\n", lo);
    return 0;
}

Educational Codeforces Round 104 (Div.2) - D. Pythagorean Triples

高校数学みたいな問題でした． 脳みそが働いていなかったこともあって，相当な時間詰まってしまいました…

脳みそが死んでいても手を動かすだけでこの手の問題を解けるように整理しておきます．

codeforces.com

問題概要

ピタゴラス数とは $$ a^{2}+b^{2}=c^{2} \tag{1} $$ を満たす正の整数 $ (a, b, c) $ の組である． 誤ったピタゴラス数の定義 $$ c=a^{2}-b \tag{2} $$ を考える．$ (3, 4, 5) $ はピタゴラス数正しい定義と誤った定義両方を満たす． このように，両方の定義を満たし $ 1 \leq a \leq b \leq c \leq n $ を満たすような $ (a, b, c) $ の組の数を求めよ． テストケースは $ t $ 個与えられる．

制約

• $ 1 \leq t \leq 10^{4} $
• $ 1 \leq N \leq 10^{9} $

考察

式 $ (1) $ と $ (2) $ を両方満たさなければならないため，連立させる． 共通する $ a^{2} $ を排除したいので辺々足し合わせて整理する．

\begin{align} a^{2}+b^{2}+c&=a^{2}+c^{2}-b \\ b^{2}+b&=c^{2}-c \\ b(b+1)&=c(c-1) \\ b&=c-1 \tag{3} \end{align}

上の式 $ (3) $ を $ (2) $ 代入して（別に $ (1) $ でも良い）

\begin{align} a^{2}-(c-1)=c \\ a^{2}=2c-1 \tag{4} \end{align}

$ a $ と $ c $ の関係式が得られた．組の数え上げの典型であるところの関係式が得られたら文字を固定するをやる． こういうのは次数が高い文字から決めうつのが好ましい．（ $ a $ と $ c $ の上限が同じなので次数が高い $ a $ の方が探索範囲が狭まる）

式 $ (4) $ と制約 $ c \leq n $ より $ a^{2} \leq 2n-1 $ を満たす $ a $ を考えればいいことが分かる． また 式 $ (4) $ から $ c $ が整数である条件は $ a $ が奇数であれば良いことがわかる． $ b=c-1 $ なので $ c $ が整数であれば $ b $ も整数なのでこちらも同時に条件を確認できる．

最後に $ 1 \leq a \leq b \leq c $ の条件を確認する．

• $ a $ を $ 1 $ からインクリメンタルに全探索するので $ 1 \leq a $ は満たされる．
• $ b = \frac{a^{2}-1}{2} $ と計算できるので $ a \leq b $ はそのまま条件確認すれば良い．
• $ b \leq c $ は常に満たされている．

$ a^{2} $ は $ a>0 $ で単調増加するので $ 1 $ つのテストケースを $ O( \sqrt{n} ) $ で計算ができる． $ O(T \sqrt{n} ) $ は正直厳しいケースがありそう． $ n $ の最大値を $ n _ {max} $ として $ a^{2} \leq 2 \cdot n _ {max} - 1 $ までについて前計算でテーブルをすれば，二分探索によって各テストケースに $ O( \log{n} ) $ で答えられる． こうすることで，時間計算量 $ O( \sqrt{n_{max}} + T \log{n}) $ で安心して Submit することができる．

別解

計算量はそう変わらないんですが，別の解法を一応示します． $ a^{2} $ が $ a>0 $ で単調増加で $ b=c-1 $ とおけば，$ a \leq b \leq c $ も $ a=3 $ 以上の時は満たされている（ $ f(a)=b-a=\frac{a^{2}-1}{2}-a $ のグラフを思い浮かべれば自明かと思います）．

つまり，$ 2n-1 $ 以下で $ 3 $ 以上の奇数の平方数を数え上げれば問題文の条件を全て満たす． これは $ a=2m+1 $ などと表現すれば二分探索で求めることができる． 前計算が要らずに $ O(T \log{n}) $ になり，うれしい（？）

謝辞

前計算をしない $ O(T \sqrt{n} )$ が普通に 358 ms で通りました．実行時間の見積もりが下手すぎて涙…。

個人的ポイント

• 連立方程式が出てきたらとりあえず文字を減らすよう頑張る．
  • 文字が $ 2 $ つ以下にできたら後は大体算数か二分探索．
• 次数が大きい方から決め打つと，十中八九嬉しい．
  • これはもう脳死でやれるだろ（自戒）
• 整数組数え上げ問題はちゃんと最初の条件をちゃんと確認する．
  • ちゃんと確認しないと頭悪い日だと混乱してしまう…
  • 整数条件と不等式
• なんか軽い $ 10^{8} $ ループぐらいならもう脳死で投げちまうか．
  • C++ は最強なので大体通る気がしてきたぞ．

ソースコード

提出URL1(前計算)

提出URL2(二分探索のみ)

提出URL2(前計算なし)

▶ソースコードを展開

#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
using ll=long long;
 
const ll N_MAX=1e9;
 
int main()
{
    vector<ll> v;
    for(ll a=1; a*a<=2*N_MAX+1; a++){
        if ((a*a&1) && (a*a-1)/2>=a){
            v.push_back(a*a);
        }
    }
    int t; scanf("%d",&t);
    while(t--){
        ll N; scanf("%lld",&N);
        ll ans=upper_bound(v.begin(),v.end(),2*N-1)-v.begin();
        printf("%lld\n",ans);
    }
    return 0;
}

AtCoder Regular Contest 107 D - Number of Multisets

もはやなんで苦手なのかわからないが，苦手だったのでまとめた．

特に特殊ではないと思うが，着眼点をミスるとハマってしまいそうなDPの問題でした．

atcoder.jp

問題概要

自然数 $ N, K $ が与えられて，$ \frac{1}{2^{i}} (i = 0, 1, 2, \cdots) $ のみを要素に使って作れる長さ $ N $，和 $ K $ の多重集合 (multiset) の種類数を答えよ． 答えは大きくなるので $ 998244353 $ で割った余りを出力せよ．

制約

• $ 1 \leq K \leq N \leq 3000 $
• 入力は整数

考察

問題を読み替える．$ K $ は整数なので $ \frac{1}{2^{N-1}} $ 未満の数字は使うことができない． （少し考えると $ \frac{1}{2} + \frac{1}{4} + \cdots + \frac{1}{2^{N-1}} $ が小さい数を使う限界であるとわかる）

$$ \sum _ {i=0}^{N-1} c_i \cdot \frac{1}{2^{i}}= K \tag{1} $$ $$ \sum _ {i=0}^{N-1} c_i = N \tag{2} $$ $$ c_i \geq 0 ~~ (0 \leq i \leq N-1) \tag{3} $$

をみたすような整数列$ c $ の数を求めよ，という問題に読み替えることができる．

特殊な制約を持った部分和DPのような見た目をしていて，制約もそんなに厳しくないのでDPの方向で考えていく．

何も考えないで部分和DPをやるととんでもない状態数になることは目に見えているのでこの問題特有の制約について考える．

ここで式 $ (1) $ に注目して両辺に $ 2 $ を掛ける．これは高校数学典型っぽい変形テクニックで $$ \sum _ {i=0}^{N-1} C_i \cdot r^{i} = S $$ のような形が出てきたら，両辺に $ r $ か $ r^{-1} $ を掛けることによって変形すると嬉しいことが多い．

\begin{align} \sum _ {i=0}^{N-1} c_i \cdot \frac{1}{2^{i-1}} &= 2K \\ 2c_0 + \sum _ {i=1}^{N-1} c_i \cdot \frac{1}{2^{i-1}} &= 2K \\ \sum _ {i=0}^{N-2} c_{i+1} \cdot \frac{1}{2^{i}} &= 2(K - c_0) \tag{4} \end{align}

また $$ \sum _ {i=0}^{N-2} c_{i+1} = N - c_0 \tag{5} $$

式 $ (4)~(5) $ は式 $ (1)~(2) $ に対応していることがわかる．ここで入力が $ N, K $ の時の答えを $ f(N,K) $ と置き $ c_0 $ は変数であることに注意すると次の式が成立する．

$$ f(N,K) = \sum _ {c_0=0}^{\min({N,K})} f(N - c_0, 2(K - c_0)) \tag{6} $$

$ \min({N,K}) $ の理由は $ N<0 $ または $ K<0 $ のとき $ f(N,K)=0 $ であるためそれぞれが非負の区間で $ c_0 $ を回したということ．

式 $ (6) $ のような遷移式が見つかったのでDPを考える． $ N<K $ のとき明らかに $ f(N,K)=0 $ のためこの状態を考える必要はなく，状態数は $ O(N^{2}) $ である．遷移が $ O(N) $ なので全体の計算量は $ O(N^{3}) $ になる．$ N \leq 3000 $ なのでこのままでは間に合わない．遷移をまとめることを考えていく．

分かり易さのために $ f(N,K) $ の値を表にして，例として $ f(4,2) $ の値を求めることを考える．

☆の値は赤い部分の値の和に等しい

式 $ (6) $ より，赤い部分の値の和が目的の $ f(4,2) $ の値と等しいことがわかる．この赤い部分の和を斜めのラインの累積和として求めながらDPをすれば遷移が $ O(1) $ になるだろう．どう累積和をとってもいいが，今回は図の"〇"のようなこれ以上左上に行けない部分を代表としてそこの添え字に値を加算していった．

注意点としては $ f(N,K) $ の値が $ f(N,2K) $ に依存しているため $ K $ の降順に計算していく．

これでも全体の計算量が $ O(N^{2}) $ になるのだが累積和を取るところが少し面倒．実はもっと良い方法がある．

★の値は緑の和なので☆=★+赤となる

先程と同様に考えると★の値は緑の部分の値の和になる．これは☆の値を求める赤の和と殆ど被っている．またそのような★の位置は☆の位置のちょうど左上である（冷静に式を処理すると確認できる）．以上のことから次の式が成立する．

$$ f(N, K) = f(N - 1, K - 1) + f(N, 2K) \tag{7} $$

式 $ (7) $ からメモ化再帰なりすれば答えが $ O(N^{2}) $ で得られる．ループを回すときはやはり $ K $ の降順に計算していくことに注意．

別解

AtCoderにおける想定解と同じ．

答えは $ c_0 = 0 $ の場合と $ c_0 > 0 $ の場合の和になることに注目する．

• $ c_0 = 0 $ の場合は式 $ (1) $ の両辺に $ 2 $ を掛けることで $ f(N, 2K) $ と等しいことが示せる．
• $ c_0 > 0 $ の場合は $ c_0 $ を $ 1 $ 減らす．すると $ f(N - 1, K - 1) $ と等しいことがわかる．

よって式 $ (7) $ が成立することが示せる．

この場合分けを一発でできる人天才すぎないか？僕には無理です．

個人的ポイント

• 日本語が多い問題文だったので式で問題文を読み替えることが大切
• 等比数列に何らかの係数がついた式の総和は公比を掛け/割りすると嬉しい
  • 最初の式と同じようなものが得られて一般的な式が得られがち
• 遷移がまとめられないかを考える時はDPテーブルを実際に書いてみると良いかも
• 本文には書かなかったがsnukeさんの解説では1の寄与を二分木1つに言い換えていた
  • 二分木は結構嬉しい形なのでこの言い換えは詰まったときに一考の余地があると思った
  • 二分木を数え上げる時は葉から構成するといいらしい（AtCoder解説動画情報）
    • 実際根から素直に構成すると $ O(N^{3}) $ になってしまう．

ソースコード

提出URL1(累積和)

提出URL2(メモ化再帰)

▶ソースコードを展開

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,n,m) for(int i=(int)(n); i<=(int)(m); i++)
#define RFOR(i,n,m) for(int i=(int)(n); i>=(int)(m); i--)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define RITR(x,c) for(__typeof(c.rbegin()) x=c.rbegin();x!=c.rend();x++)
#define setp(n) fixed << setprecision(n)

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll,ll>
#define pi pair<int,int>

#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define ins insert

#define debug(a) cerr<<(a)<<endl
#define dbrep(a,n) rep(_i,n) cerr<<(a[_i])<<" "; cerr<<endl
#define dbrep2(a,n,m) rep(_i,n){rep(_j,m) cerr<<(a[_i][_j])<<" "; cerr<<endl;}

using namespace std;

template<class A, class B>
ostream &operator<<(ostream &os, const pair<A,B> &p){return os<<"("<<p.fi<<","<<p.se<<")";}
template<class A, class B>
istream &operator>>(istream &is, pair<A,B> &p){return is>>p.fi>>p.se;}

const ll mod = 998244353;
const int N_MAX = 3010;
ll sum[N_MAX][N_MAX];
ll dp[N_MAX][N_MAX];

//-------------------------------------------------

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N,K; cin>>N>>K;
    
    dp[0][0]=sum[0][0]=1;
    FOR(i,1,N)RFOR(j,N,0){
        int k = min(i,j);
        if (2*(j-k)<=N)
            dp[i][j] = sum[i-k][2*(j-k)];
        int l = min(i,j/2);
        if (dp[i][j]>0)
            (sum[i-l][j-l*2]+=dp[i][j])%=mod;
    }
    cout<<dp[N][K]<<"\n";
    return 0;
}

AtCoder Regular Contest 106 D - Powers

数学系の問題が苦手すぎて困ったのでちゃんと記事にして忘れないようにしました． 総和のついた数式を変形させていくタイプの問題でした．

atcoder.jp

問題概要

長さ $ N $ の整数列 $ A $ と $ K $ が与えられる． $ 1 \leq X \leq K $ について，以下の値を求めよ． $$ \left( \sum _ {L=1}^{N-1} \sum _ {R=L+1}^{N} (A_L + A_R)^{K} \right) \bmod 998244353 $$

制約

• $ 2 \leq N \leq 2 \times 10^{5} $
• $ 1 \leq K \leq 300 $
• $ 1 \leq A_i \leq 10^{8} $

考察

本質ではないところから．問題文では 1-indexed になっていて嫌な気持ちになるので， $ i = L - 1, j = R - 1 $ として 0-indexed に直す． $$ \sum _ {i=0}^{N-2} \sum _ {j=i+1}^{N-1} (A_i + A_j)^{K} $$ また，求める値を $ ans_X (1 \leq X \leq N) $ と置くことにする．

$ (A_i + A_j)^{K} $ はこのままの形で扱うのは難しいので変形したいが，この形は二項定理で展開するのが良いと相場が決まっている．すると， $$ ans_X = \sum _ {i=0}^{N-2} \sum _ {j=i+1}^{N-1} \sum _ {k=0}^{X} \binom{X}{k} (A_i)^{k} (A_j)^{X-k} $$ のようになる．シグマがいっぱいで困っちゃう．

知識 (シグマを含む式の変形)

上の式のようにシグマが二重・三重になっているような式は次の3つの変形を使ってうまいこと書き換えるのが定石．

1. 項ごとに分割して考えることができる

2. 対象の式をカウンタ変数( $ i $ や $ j $ )の式として見たときに定数なら括り出せる

3. 2つの並んだシグマは，2つのカウンタ変数の初期値/終端値に依存関係がないなら入れ替えられる

1, 2は総和の線形性より明らかです． $$ \sum _ {i=0}^{N-1} (\alpha A_i + \beta B_i) = \alpha \sum _ {i=0}^{N-1} A_i + \beta \sum _ {i=0}^{N-1} B_i $$

3は自分の数学力では何といえばいいのかわかりませんが中高で習うはずです． $ j $ の初期値/終端値に $ i $ が含まれているなどの場合は $ i \rightarrow j $ の順番を守らなければいけません．

---

閑話休題，問題の考察に戻って実際に変形してみる．なにも考えず変形規則をできるだけ適用した．

\begin{align} ans_X &= \sum _ {i=0}^{N-2} \sum _ {j=i+1}^{N-1} \sum _ {k=0}^{X} \binom{X}{k} (A_i)^{k} (A_j)^{X-k} \\ &=\sum _ {k=0}^{X} \binom{X}{k} \sum _ {i=0}^{N-2} \left\{ (A_i)^{k} \cdot \sum _ {j=i+1}^{N-1} (A_j)^{X-k} \right\} \end{align}

この形だと $ \sum _ {j=i+1}^{N-1} (A_j)^{X-k} $ を前計算しておくことで $ O(NK^{2}) $ で答えが得られる( $ ans_X $ $ 1 $ つにつき $ O(NK) $)．

当然制約上このままでは間にあわない．式を見ると $ \sum _ {j=i+1}^{N-1} (A_j)^{X-k} $ が $ i $ の関数になっていることで $ i $ のシグマから括り出せていないことがわかる．この式が $ i $ の関数になってしまっている原因は明らかに $ j=i+1 $ であるからここを $ j=0 $ に変えてしまうことを考える．

最初の式に立ち返って $ j=0 $ にすると，どのぐらい答えに影響するのかを考える．これは意外と単純で $ ans_X $ は $ i < j $ の場合の和なので，$ j = i+1 $ を $ j=0 $ に変えた和から $ i = j $ と $ i > j $ の場合の和を引けば $ i < j $ の場合の和が算出されるだろう．また対称性から$ i < j $ の場合と $ i > j $ の場合の和は等しい．以上を式で言えば次の通りである．

\begin{align} ans_X &= \sum _ {i=0}^{N-1}\ \sum _ {j=0}^{N-1} (A_i + A_j)^{X} - \sum _ {i=0}^{N-1} (A_i + A_i)^{X} - \sum _ {j=0}^{N-1} \sum _ {i=j+1}^{N-1} (A_i + A_j)^{X} \\ &= \left( \sum _ {i=0}^{N-1} \sum _ {j=0}^{N-1} (A_i + A_j)^{X} - \sum _ {i=0}^{N-1} (A_i + A_i)^{X} \right) \times \frac{1}{2} \\ &= \left( \sum _ {i=0}^{N-1} \sum _ {j=0}^{N-1} (A_i + A_j)^{X} - 2^{X} \cdot \sum _ {i=0}^{N-1} (A_i)^{X} \right) \times \frac{1}{2} \tag{*} \end{align}

$ \sum _ {i=0}^{N-1} \sum _ {j=0}^{N-1} (A_i + A_j)^{X} $ を最初の変形と同様なにも考えず変形．

\begin{align} \sum _ {i=0}^{N-1} \sum _ {j=0}^{N-1} (A_i + A_j)^{X} &= \sum _ {i=0}^{N-1} \sum _ {j=0}^{N-1} \sum _ {k=0}^{X} \binom{X}{k} (A_i)^{k} (A_j)^{X-k} \\ &= \sum _ {k=0}^{X} \binom{X}{k} \left( \sum _ {i=0}^{N-1} (A_i)^{k} \right) \left( \sum _ {j=0}^{N-1} (A_j)^{X-k} \right) \end{align}

ここで $ f(k) = \sum _ {i=0}^{N-1} (A_i)^{k} $ と置くと，$ f(k) $ $ (0 \leq k \leq K) $ を $ O(NK) $ で前計算することにより答えが $ O(K^{2}) $ で求められる．

今一度全体の式 $ (*) $ を書き下すと $$ ans_X = \left( \sum _ {k=0}^{X} \binom{X}{k} f(k) f(X-k) - 2^{X} f(X) \right) \times \frac{1}{2} $$

二項係数，$ f(k) $，$ 2^{k} $ を前計算することで全体の計算量は $ O(NK + K^{2}) $ になり間に合う．

余談

整理した式 $ (*) $を見ると $$ \sum _ {k=0}^{X} \binom{X}{k} f(k) f(X-k) $$ といういかにも畳み込みっぽい形が見つかる．実際，

\begin{align} \sum _ {k=0}^{X} \binom{X}{k} f(k) f(X-k) &= \sum _ {k=0}^{X} \frac{X!}{k!(X-k)!} f(k) f(X-k) \\ &= X! \sum _ {k=0}^{X} \frac{ f(k) }{ k! } \frac{ f(X-k) }{ (X-k)! } \\ &= X! \sum _ {k=0}^{X} g(k) g(X-k) \\ & \left( g(k) = \frac{ f(k) }{ k! } \right) \end{align}

となりFFTを用いて $ O(NK + K \log{K}) $ になる．ボトルネックそこじゃないけど．

本当に余談だが，$ j $ の初期化を $ j=i+1 $ のままにしても畳み込みの形にすることができてその時の計算量は $ O(NK \log{K}) $ になる．試したけど間に合わんかった．つらい．

個人的なポイント

• 2項の式の累乗の式を見たら，とりあえず展開すべき
• シグマが二重三重になっている問題は変形が肝要であることが多い
  • シグマ同士の入れ替えや線形性を利用した変形を手元でするべき
• シグマの変形の中でも $$ \sum _ {i=0}^{N-1} \sum _ {j=0}^{N-1} f(i) f(j) = \left( \sum _ {i=0}^{N-1} f(i) \right) \cdot \left( \sum _ {j=0}^{N-1} f(j) \right) $$ の変形は典型な気がする (やはり $ N $ が $ 1 $ つ落ちるのは大きい)

ソースコード

提出URL1

提出URL2(FFT)

▶ソースコードを展開

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,n,m) for(int i=(int)(n); i<=(int)(m); i++)
#define RFOR(i,n,m) for(int i=(int)(n); i>=(int)(m); i--)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define RITR(x,c) for(__typeof(c.rbegin()) x=c.rbegin();x!=c.rend();x++)
#define setp(n) fixed << setprecision(n)

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll,ll>
#define pi pair<int,int>

#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define ins insert

#define debug(a) cerr<<(a)<<endl
#define dbrep(a,n) rep(_i,n) cerr<<(a[_i])<<" "; cerr<<endl
#define dbrep2(a,n,m) rep(_i,n){rep(_j,m) cerr<<(a[_i][_j])<<" "; cerr<<endl;}

using namespace std;

template<class A, class B>
ostream &operator<<(ostream &os, const pair<A,B> &p){return os<<"("<<p.fi<<","<<p.se<<")";}
template<class A, class B>
istream &operator>>(istream &is, pair<A,B> &p){return is>>p.fi>>p.se;}

//-------------------------------------------------
//--ModInt
//-------------------------------------------------
const ::std::uint_fast64_t MOD = 998244353;

class mint
{
private:
    using value_type = ::std::uint_fast64_t;
    value_type n;
public:
    mint():n(0){}
    mint(::std::int_fast64_t _n):n(_n<0 ? MOD-(-_n)%MOD : _n%MOD){}
    mint(const mint &m):n(m.n){}

    friend ::std::ostream& operator<<(::std::ostream &os, const mint &a){
        return os << a.n;
    }
    friend ::std::istream& operator>>(::std::istream &is, mint &a){
        value_type temp; is>>temp;
        a = mint(temp);
        return is;
    }

    mint& operator+=(const mint &m){n+=m.n; n=(n<MOD)?n:n-MOD; return *this;}
    mint& operator-=(const mint &m){n+=MOD-m.n; n=(n<MOD)?n:n-MOD; return *this;}
    mint& operator*=(const mint &m){n=n*m.n%MOD; return *this;}
    mint& operator/=(const mint &m){return *this*=m.inv();}
    mint& operator++(){return *this+=1;}
    mint& operator--(){return *this-=1;}

    mint operator+(const mint &m) const {return mint(*this)+=m;}
    mint operator-(const mint &m) const {return mint(*this)-=m;}
    mint operator*(const mint &m) const {return mint(*this)*=m;}
    mint operator/(const mint &m) const {return mint(*this)/=m;}
    mint operator++(int){mint t(*this); *this+=1; return t;}
    mint operator--(int){mint t(*this); *this-=1; return t;}

    bool operator==(const mint &m) const {return n==m.n;}
    bool operator!=(const mint &m) const {return n!=m.n;}
    mint operator-() const {return mint(MOD-n);}

    mint pow(value_type b) const {
        mint ret(1), m(*this);
        while(b){
            if (b & 1) ret*=m;
            m*=m;
            b>>=1;
        }
        return ret;
    }

    mint inv() const {return pow(MOD-2);}
};

//-------------------------------------------------
//--Combination (depends on ModInt)
//-------------------------------------------------
class Combination
{
private:
    ::std::vector<mint> _fact;
    ::std::vector<mint> _finv;
public:
    Combination(int n):_fact(n+1), _finv(n+1){
        _fact[0] = _fact[1] = 1;
        _finv[0] = _finv[1] = 1;
        for(int i=2; i<=n; i++){
            _fact[i] = _fact[i-1]*i;
            _finv[i] = _fact[i].inv();
        }
    }
    mint fact(int x){return _fact[x];}
    mint finv(int x){return _finv[x];}
    mint comb(int x, int y){
        if (y>x || y<0) return 0;
        return _fact[x]*_finv[y]*_finv[x-y];
    }
    mint homo(int x, int y){return comb(x+y-1, y);}
};

const int N_MAX = 2e5;
const int K_MAX = 300;
mint asum[K_MAX+1];
mint pow2[K_MAX+1];

//-------------------------------------------------

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N,K; cin>>N>>K;
    vll a(N);
    rep(i,N) cin>>a[i];
    rep(i,N){
        mint m = 1;
        rep(j,K+1){
            asum[j]+=m;
            m*=a[i];
        }
    }
    pow2[0]=1;
    rep(i,K) pow2[i+1]=pow2[i]*2;
    Combination bn(K);
    mint inv2 = mint(2).inv();

    FOR(x,1,K){
        mint ans=0;
        FOR(i,0,x){
            ans+=bn.comb(x,i)*asum[x-i]*asum[i];
        }
        ans-=pow2[x]*asum[x];
        cout<<ans*inv2<<"\n";
    }
    return 0;
}