C++ の動作確認をしてみた（９２１）

C++の練習を兼ねて, AtCoder Beginner Contest 137 の問題F (Polynomial Construction) を解いてみた.

■感想.
1. 問題F は, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. TLEをギリギリ回避している実装(1793[ms])なので, 高速化について, 将来的な課題として残っている.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト AtCoder Beginner Contest 137 解説の各リンクをご覧下さい.

■C++版プログラム(問題F／AC版).

// 解き直し.
// https://img.atcoder.jp/abc137/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
const int LIMIT = 3030;
LL FAC[LIMIT], INV[LIMIT], a[LIMIT], b[LIMIT], t[LIMIT];

// Fermat's little theorem から, 大きな冪乗の計算を行う.
// -> 引数 MOD は, 素数と限らないので, 逆元の計算に使用する場合は, 注意する.
// @param a: べき乗したい正整数.
// @param b: 指数.
// @return:  べき乗した計算結果(mod版).
LL mPow(LL a, LL b, LL MOD){
    LL t = 1;
    while(b){
        if(b & 1) t = (t * a) % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return t;
}

// 組み合わせ(nCk)計算用(mod版).
// ※配列FAC, INV は, 事前に計算済のものを使う.
// @param n: 対象となる要素の個数.
// @param k: 選択する要素の個数.
// @return: 組み合わせ(nCk)の計算結果(mod版).
LL combination(LL n, LL k, LL MOD){
    if(n < 0 || k < 0 || k > n) return 0;
    LL ret = FAC[n] * INV[k] % MOD * INV[n - k] % MOD;
    return ret;
}

int main(){
    
    // 1. 入力情報.
    int p;
    scanf("%d", &p);
    rep(i, p) scanf("%lld", &a[i]);
    
    // 2. 事前準備.
    FAC[0] = INV[0] = 1;
    repx(i, 1, LIMIT){
        FAC[i] = (LL)i * FAC[i - 1] % p;
        INV[i] = mPow(FAC[i], p - 2, p);
    }
    
    // 3. 集計.
    rep(j, p){
        // Skip.
        if(!a[j]) continue;
        
        // 初期化.
        rep(i, LIMIT) t[i] = 0;
        
        // 1 - {(x - j) の (p - 1)乗} を 展開.
        bool sign = false;
        repr(i, p - 1, 0){
            t[i] = sign ? combination(p - 1, i, p) : (p - combination(p - 1, i, p));
            t[i] = t[i] * mPow(j, p - 1 - i, p) % p;
            sign = !sign;
        }
        
        // 定数項補正.
        t[0] = (t[0] + 1) % p;
        
        // 加算.
        rep(i, p) b[i] = (b[i] + t[i]) % p;
    }
    
    // 4. 出力.
    rep(i, p) printf("%lld%s", b[i], (i < p - 1) ? " " : "\n");
    return 0;
    
}

// 解き直し.

// https://img.atcoder.jp/abc137/editorial.pdf

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

#define repex(i, a, b, c) for(int i = a; i < b; i += c)

#define repx(i, a, b) repex(i, a, b, 1)

#define rep(i, n) repx(i, 0, n)

#define repr(i, a, b) for(int i = a; i >= b; i--)

const int LIMIT = 3030;

LL FAC[LIMIT], INV[LIMIT], a[LIMIT], b[LIMIT], t[LIMIT];

// Fermat's little theorem から, 大きな冪乗の計算を行う.

// -> 引数 MOD は, 素数と限らないので, 逆元の計算に使用する場合は, 注意する.

// @param a: べき乗したい正整数.

// @param b: 指数.

// @return: べき乗した計算結果(mod版).

LL mPow(LL a, LL b, LL MOD){

LL t = 1;

while(b){

if(b & 1) t = (t * a) % MOD;

a = a * a % MOD;

b >>= 1;

}

return t;

}

// 組み合わせ(nCk)計算用(mod版).

// ※配列FAC, INV は, 事前に計算済のものを使う.

// @param n: 対象となる要素の個数.

// @param k: 選択する要素の個数.

// @return: 組み合わせ(nCk)の計算結果(mod版).

LL combination(LL n, LL k, LL MOD){

if(n < 0 || k < 0 || k > n) return 0;

LL ret = FAC[n] * INV[k] % MOD * INV[n - k] % MOD;

return ret;

}

int main(){

// 1. 入力情報.

int p;

scanf("%d", &p);

rep(i, p) scanf("%lld", &a[i]);

// 2. 事前準備.

FAC[0] = INV[0] = 1;

repx(i, 1, LIMIT){

FAC[i] = (LL)i * FAC[i - 1] % p;

INV[i] = mPow(FAC[i], p - 2, p);

}

// 3. 集計.

rep(j, p){

// Skip.

if(!a[j]) continue;

// 初期化.

rep(i, LIMIT) t[i] = 0;

// 1 - {(x - j) の (p - 1)乗} を展開.

bool sign = false;

repr(i, p - 1, 0){

t[i] = sign ? combination(p - 1, i, p) : (p - combination(p - 1, i, p));

t[i] = t[i] * mPow(j, p - 1 - i, p) % p;

sign = !sign;

}

// 定数項補正.

t[0] = (t[0] + 1) % p;

// 加算.

rep(i, p) b[i] = (b[i] + t[i]) % p;

}

// 4. 出力.

rep(i, p) printf("%lld%s", b[i], (i < p - 1) ? " " : "\n");

return 0;

}

[入力例]
2
1 0

[出力例]
1 1
※AtCoderテストケースより

[入力例]
3
0 0 0

[出力例]
0 0 0
※AtCoderテストケースより

[入力例]
5
0 1 0 1 0

[出力例]
0 2 0 1 3
※AtCoderテストケースより

[入力例]
7
0 1 0 1 0 1 0

[出力例]
0 5 0 1 0 5 4

[入力例]
11
0 0 1 0 0 0 1 0 1 0 0

[出力例]
0 7 10 5 5 3 4 1 6 6 8

[入力例]
17
0 0 1 0 0 0 1 0 1 0 0 1 1 1 0 0 1

[出力例]
0 14 1 1 4 15 12 7 16 0 16 12 13 10 5 0 10 

[入力例]
331
0 0 1 0 1 1 1 0 1 1 0 0 0 1 0 0 0 0 0 1 1 0 1 0 1 0 1 0 1 1 0 1 1 0 1 0 1 1 0 1 1 1 0 1 1 1 1 1 0 1 0 1 0 0 0 0 0 1 0 0 1 1 1 0 0 1 1 0 1 1 0 0 1 1 1 0 0 0 0 1 1 1 1 1 0 1 0 1 1 0 1 1 1 0 1 0 1 1 1 1 0 1 0 1 0 0 1 0 1 1 1 0 1 1 1 1 0 0 0 1 0 0 0 0 0 0 1 1 0 0 1 0 1 1 1 1 1 1 1 1 0 0 0 1 0 1 0 1 0 0 0 1 1 1 0 0 0 0 0 0 1 0 0 1 0 0 1 1 1 1 1 0 0 1 0 1 0 0 1 1 0 1 1 1 0 1 0 0 0 1 0 0 0 0 1 0 1 1 1 0 1 0 0 0 1 0 1 1 1 1 1 1 1 1 0 1 0 1 1 1 0 1 0 0 1 1 0 1 1 1 0 0 1 0 1 0 0 1 1 1 1 0 0 0 0 1 1 0 0 0 1 1 0 1 1 0 1 0 1 0 1 1 1 0 1 0 0 0 1 0 1 0 1 0 1 1 1 1 0 1 0 1 0 1 1 1 1 0 0 0 0 0 0 1 0 1 1 0 1 1 1 0 0 0 0 0 1 1 0 0 0 0 1 1 0 1 1 1 1 1 1 0 1 1 1 0 0 0 0 1 0

[出力例]
0 270 29 28 211 326 92 161 309 74 132 135 28 242 187 243 185 253 58 165 253 31 0 297 289 236 323 67 2 207 156 248 113 174 12 12 176 254 118 107 176 253 6 283 218 8 261 79 115 48 156 165 23 185 294 122 45 217 32 237 135 110 224 299 104 246 99 243 153 53 202 322 54 201 123 282 125 68 308 248 73 263 16 274 261 102 67 57 21 1 5 104 46 117 74 11 324 59 95 248 100 110 203 304 170 276 252 317 184 213 312 213 163 138 21 289 167 316 119 145 275 191 206 63 12 200 204 204 294 242 224 23 308 208 30 195 42 192 232 293 162 96 8 15 173 291 232 36 125 110 239 115 126 230 18 1 177 23 185 23 219 71 207 98 254 3 184 306 324 45 290 137 81 174 8 135 183 237 179 81 32 202 115 204 304 271 252 188 135 158 239 303 123 100 69 326 63 75 188 43 109 132 233 77 43 66 86 153 121 63 85 77 66 143 180 197 145 51 261 308 44 236 202 87 173 292 254 43 168 21 165 320 196 122 91 258 212 104 6 280 210 23 150 176 127 6 31 137 189 140 113 97 325 57 100 212 271 308 80 7 107 318 164 25 42 200 2 210 19 170 213 258 270 10 58 200 88 268 205 83 164 261 50 55 262 29 61 68 16 316 276 260 237 48 13 208 158 248 18 187 304 265 307 234 109 207 259 46 322 91 64 119 185 128 159 142 273 171 255 270 105 92 285 221 206 101 232 52 156 62 156

[入力例]
2027
0 1 1 1 0 1 0 0 1 0 1 1 0 0 1 0 0 1 0 0 1 1 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 0 1 0 1 1 1 1 1 1 1 1 0 1 0 1 1 1 1 0 1 1 1 1 1 0 0 0 1 0 0 1 0 0 1 0 1 1 0 0 1 0 1 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 1 0 1 0 0 1 0 1 0 0 0 1 0 1 1 1 0 0 0 0 1 1 0 1 1 1 0 1 1 0 0 1 0 1 1 0 0 1 1 1 0 1 0 1 1 1 1 1 0 1 0 0 0 1 1 1 1 0 0 1 0 1 1 1 0 0 0 1 0 0 1 1 0 0 0 0 0 1 1 1 0 1 0 1 0 1 0 1 0 0 1 0 0 0 0 0 0 1 1 0 1 0 1 1 1 1 0 1 1 1 1 0 0 0 1 0 0 0 0 1 1 1 1 1 0 0 1 1 0 0 0 1 1 0 0 1 1 0 1 0 0 1 1 1 1 0 0 0 1 1 0 0 1 1 0 1 1 1 0 1 0 1 0 0 1 1 0 1 1 0 1 0 0 0 0 0 0 1 0 0 1 0 1 0 1 1 1 1 0 1 1 0 1 1 0 1 0 1 1 0 1 1 0 1 0 1 1 0 1 0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 1 0 1 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 0 1 0 0 0 1 1 1 0 0 0 1 1 0 1 1 0 0 0 1 1 0 0 0 0 0 0 1 0 1 0 1 0 1 1 0 1 1 0 1 1 0 1 1 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 1 1 1 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 1 1 1 0 1 0 1 1 0 0 1 0 1 1 1 1 0 1 1 1 1 1 0 1 0 0 1 1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 0 1 0 1 0 0 1 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 1 0 1 1 0 0 1 1 1 1 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 1 0 1 0 1 1 0 1 1 1 1 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 1 1 1 0 0 1 1 0 1 1 1 1 0 0 1 0 1 1 1 1 0 1 0 1 0 1 1 0 0 1 0 1 0 0 1 0 0 0 1 0 1 1 0 0 0 0 1 0 1 0 1 0 1 0 1 1 0 1 1 0 0 1 1 0 0 1 1 1 1 1 1 1 0 1 1 0 0 1 0 1 1 1 0 1 0 1 1 1 0 0 1 1 1 0 1 1 1 0 0 0 1 1 0 1 1 1 0 1 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 1 1 0 1 0 1 1 0 0 0 0 0 1 0 1 0 0 0 0 1 1 1 1 1 0 1 0 1 1 1 0 1 1 1 1 1 1 1 0 0 1 1 0 1 1 0 0 1 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 0 1 1 0 1 0 0 1 0 0 0 0 0 1 1 1 1 0 0 1 0 0 0 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 0 0 1 0 1 0 0 0 1 1 0 0 0 1 0 0 0 0 0 1 1 1 0 0 1 0 0 0 1 0 0 0 0 1 0 1 0 1 1 1 1 0 1 1 1 0 1 0 0 0 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 0 1 1 1 0 1 1 0 0 0 1 1 1 0 1 0 0 0 0 1 0 1 0 1 1 0 0 0 1 1 0 0 1 1 1 0 0 0 1 0 0 0 0 0 1 1 0 1 1 0 1 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 1 0 0 1 1 0 0 1 1 0 0 0 1 1 0 0 1 0 0 0 1 0 0 1 1 1 1 1 0 0 0 1 1 0 1 0 1 0 1 0 1 1 1 0 1 1 1 0 1 1 1 1 1 0 0 1 1 0 1 0 0 1 0 0 1 1 0 0 0 1 0 0 1 1 0 0 1 1 1 1 0 1 1 0 1 0 1 0 1 0 1 0 0 1 0 1 0 0 0 1 0 1 0 0 1 1 0 0 0 0 0 1 0 0 0 1 1 1 0 1 0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 1 0 1 1 1 0 0 1 1 1 0 1 1 0 1 0 1 0 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 0 1 1 1 0 1 1 0 1 0 1 0 1 1 0 0 1 0 0 1 1 0 1 1 0 1 0 1 0 0 1 1 1 0 0 0 0 0 0 1 0 0 1 0 0 1 0 1 1 1 0 0 0 1 1 0 1 1 0 1 0 0 0 0 1 1 1 0 0 1 1 0 1 0 1 0 0 0 1 0 1 0 1 1 1 0 0 0 1 1 1 0 1 0 1 1 1 0 1 1 0 0 0 1 0 0 1 0 0 1 1 0 1 1 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 1 0 1 0 0 1 0 0 1 1 1 0 1 0 0 1 0 1 1 0 1 1 1 1 0 0 0 1 1 0 0 0 1 1 0 1 0 0 0 1 1 1 0 0 1 1 1 0 1 0 1 0 1 1 0 0 0 0 1 1 0 1 1 0 1 1 1 1 0 1 1 0 0 0 1 0 0 1 1 1 0 1 1 0 0 0 0 1 1 1 0 1 0 0 0 1 1 0 0 0 0 0 1 0 1 1 1 0 1 0 1 1 0 1 1 1 1 0 1 0 1 0 0 1 1 0 1 0 0 0 1 1 0 0 1 1 1 1 1 1 0 1 1 0 1 0 1 0 1 0 1 1 1 0 0 0 1 1 0 1 1 1 0 1 1 0 0 0 0 0 1 0 1 1 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 0 0 1 0 0 0 0 1 0 0 1 0 1 0 1 1 0 1 1 1 1 1 0 0 0 0 0 1 0 1 1 1 0 0 1 1 1 1 1 0 1 0 1 1 1 1 0 0 1 0 0 1 0 1 0 1 1 0 0 1 1 0 0 1 1 1 1 0 1 1 1 1 0 0 1 0 0 0 1 1 0 0 1 0 1 1 0 1 1 1 0 1 1 1 0 0 1 1 1 0 0 0 0 0 0 1 1 0 0 0 0 1 1 1 0 0 0 1 1 0 1 1 0 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 0 1 1 1 1 0 0 1 0 1 0 0 0 1 1 0 1 1 0 0 0 0 1 0 1 1 1 1 0 0 1 1 0 0 1 0 0 1 0 1 0 0 1 0 0 1 0 0 1 0 1 1 1 0 0 1 1 0 1 1 0 1 0 0 1 1 0 0 0 1 1 0 1 1 0 0 1 1 0 0 0 1 0 1 1 1 0 1 0 1 1 1 1 1 0 0 0 1 0 1 1 1 1 0 0 1 0 0 1 1 0 0 1 0 0 0 0 1 1 1 0 1 0 1 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 1 0 1 1 1 1 1 0 0 1 1 1 0 0 1 1 0 0 1 1 0 0 1 0 0 0 1 1 0 1 0 0 1 1 1 1 1 1 0 0 1 1 0 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 0 1 1 0 1 0 0 1 0 0 0 0 0 1 1 1 0 0 1 0 1 1 0 0 1 0 1 1 0 0 1 1 0 0 0 0 0 0 1 0 0 1 0 0 1 0 1 1 0 1 0 0 1 1 1 1 1 1 1 0 0 1 0 0 1 1 0 0 0 0 0 1 1 0 1 1 1 1 0 1 1 0 1 1 1 0 1 1 0 1 0 1 1 0 1 0 1 1 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 0 0 1 0 0 0 1 1 0 1 1 0 1 1 1 0 1 1 1 0 1 0 0 0 1 1 1 0 0 1 0 0 0 1 0 1 1 0 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 0 0 1 0 0 1 0 1 0 1 0 1 0 1 1 1 1 0 0 1 0 0 0 0 0 1 0 1 0 0 1 0 1 1 0 0 0 0

[出力例]
0 601 1616 1772 2023 1856 752 1059 1602 1265 1361 1383 1006 1934 149 1935 1792 1675 1540 611 1508 47 587 787 1528 1616 1145 908 1096 1641 1056 109 1764 236 517 1129 1334 144 178 1566 131 1763 1702 1394 564 451 496 1873 1630 892 64 811 989 1986 402 202 1514 545 830 1373 1132 1817 260 693 971 1255 1516 860 655 1351 1193 1652 1912 307 1671 1957 651 424 512 497 215 1197 341 1942 420 372 1167 337 1385 656 483 1795 1069 1104 1242 579 990 434 824 1176 1153 1115 258 607 1482 792 47 1812 1800 1575 1713 609 203 1389 1698 1016 1502 1224 1101 68 59 255 1984 307 72 390 631 1926 605 1273 882 1282 294 1885 1653 605 179 21 1839 1820 845 458 1332 583 575 537 37 601 28 56 1179 640 1483 1937 1994 1818 343 1513 1497 247 320 1953 707 1832 1822 874 390 1676 861 1469 853 730 422 756 180 0 382 1615 173 76 236 1868 281 988 1818 1180 583 471 1536 1283 1641 1668 715 1874 647 1119 1054 1781 1649 1150 1401 1991 168 1784 403 1110 1919 1312 1216 554 1513 1537 362 961 216 773 1828 1505 1604 1869 2005 1955 1381 1188 1465 1328 944 1760 1435 1558 1730 1778 320 1821 1869 275 984 1899 987 605 1533 677 1208 667 224 1420 1453 1519 441 814 968 996 925 1301 2001 1169 682 460 1039 1798 1358 1572 231 114 440 652 454 138 393 220 1140 1009 1435 1980 1723 775 1408 1954 233 416 1919 1001 1802 176 1144 1151 290 534 1523 1717 315 338 916 410 835 1095 120 922 460 1141 437 1951 274 1639 873 1772 179 1320 1916 703 356 1761 1465 339 1795 1464 1263 252 766 1853 841 536 2002 1099 1924 95 1966 1742 424 1404 476 144 1861 1340 667 2018 1554 1998 983 557 1160 828 200 1697 1833 291 876 1743 994 1406 230 1151 1351 1360 473 799 324 1473 190 1772 921 1345 499 7 174 246 301 1164 1594 575 1167 1998 1302 1561 814 202 1082 1895 21 1827 216 258 122 437 1914 1334 1534 236 137 1594 1814 306 414 628 846 1603 608 191 921 687 700 1002 858 1547 1174 1476 1936 1807 1139 1416 738 618 941 653 1751 1573 1033 541 1774 341 1658 1137 1312 476 1164 612 1262 49 1347 1825 1864 1002 804 1167 1067 639 660 701 1408 1011 1137 1451 1766 1704 926 725 1987 97 143 405 408 977 1431 1526 1668 1506 1732 1549 39 1621 1586 1694 1177 1485 1806 519 721 1086 644 1726 1529 1666 1029 1952 138 124 438 1397 755 1942 1805 1642 369 905 1487 1786 1635 71 1523 1160 1125 1690 768 1774 1711 1549 1079 761 777 2020 1944 1873 158 661 1907 787 291 687 1644 817 1188 329 607 1998 377 849 890 109 661 614 1914 1052 1806 1300 1361 1198 641 359 653 516 57 1819 1017 330 80 1420 709 466 28 1140 1327 621 955 1924 152 79 859 703 1222 1611 905 654 1686 408 541 1163 1638 1749 676 980 994 686 1615 551 1036 1761 1048 292 778 638 492 772 1127 376 1727 585 847 413 1854 1682 252 1106 763 738 646 291 1700 2024 159 1330 671 1055 1472 241 1877 1127 809 1407 945 1628 1882 1022 802 738 1597 735 1620 1287 867 462 1367 1909 732 704 406 711 530 407 172 605 405 1641 1175 366 1722 1272 905 1094 1218 1452 1275 1333 1323 1932 1926 1294 1166 823 1942 408 1186 1328 1134 842 465 939 1420 957 1356 1417 313 712 720 1954 994 81 53 132 659 507 1440 1735 1666 1396 84 886 1512 441 314 1954 1734 1812 1660 1580 782 722 671 1810 1311 392 269 428 1587 263 1162 788 861 252 1121 618 1082 827 923 1783 97 319 1167 292 1861 1993 1344 386 1812 1430 608 223 1883 1767 768 1612 297 1439 1852 426 1231 1056 994 1227 140 1874 921 1953 361 1004 597 649 523 472 188 906 1516 1581 282 1727 1998 276 1204 943 810 1845 894 981 1223 63 1524 1222 827 1321 366 1137 425 1268 1484 307 1004 1123 693 837 564 740 891 1773 1350 685 825 368 1811 1338 1866 1013 217 303 1357 1421 851 626 372 517 189 49 1153 279 1532 1431 1652 1910 1574 1224 1739 1815 68 1845 1722 226 1248 1571 53 801 1484 348 1155 905 667 157 884 563 1438 1819 1672 1011 261 136 27 1300 1974 1807 317 380 1271 1328 2026 1680 1545 1448 462 1431 542 1794 1465 1293 573 1080 41 1298 1236 365 2011 1910 525 509 1604 818 28 1417 1756 1714 1858 22 1946 1096 573 58 1957 607 670 74 1749 1207 232 1171 483 1685 128 1302 36 1614 1639 685 263 1845 1651 1904 523 855 452 694 365 654 1475 1893 945 1710 1108 1225 21 1411 1703 827 1540 317 1203 318 1690 1631 473 494 1237 850 565 186 831 122 1968 1220 706 1757 1136 656 301 1510 2022 1534 610 1439 399 1137 974 825 1001 941 1337 494 509 230 1868 1345 663 164 392 501 676 1077 1144 1034 1383 442 69 382 868 42 1789 1656 1825 649 824 1096 244 1371 838 1 972 770 777 84 398 1375 1267 834 273 618 40 1538 1411 1214 398 1148 1489 1777 945 587 447 82 1201 60 1538 210 374 1480 124 376 1194 281 1523 1995 322 142 485 1819 994 334 1198 200 1534 267 333 569 1348 162 472 812 454 478 722 627 1355 186 1143 518 23 1371 497 1403 1136 2025 1550 917 1736 1489 131 803 690 422 404 1043 848 770 168 369 1814 1606 1509 130 782 1776 1808 467 1316 1141 1081 1574 1245 905 1573 1504 178 866 1547 869 1084 1900 1975 111 575 1418 313 1359 43 1792 233 8 1325 1055 1942 1327 2004 431 952 1989 1793 361 935 647 1016 1718 1348 1791 867 1291 1747 1362 271 1957 439 174 1318 1202 1169 779 2025 156 921 201 722 825 416 395 484 138 708 471 315 1606 896 1309 184 1794 426 293 221 1087 643 1558 819 1577 1170 555 567 1997 1137 870 959 1050 931 1149 1699 1425 1999 399 244 1896 340 1793 1689 466 96 316 961 257 894 1879 1566 1727 595 356 1887 1702 1180 984 1939 1770 1244 825 1059 1189 1350 618 1901 1522 510 407 320 776 1226 1 1608 1542 826 1651 512 464 1628 49 759 703 815 1261 697 42 748 1654 1266 1869 776 655 182 696 1756 1187 1726 813 6 1995 1892 908 1496 18 315 1712 1322 1893 243 185 415 364 76 916 105 1862 390 1416 854 1553 1748 319 1696 1760 1960 1380 1365 1078 841 1300 1816 1142 448 1216 1779 305 183 295 946 224 1226 1011 1852 1326 371 814 1529 1256 1380 186 482 1877 1622 1560 815 1280 1708 1375 1805 1273 1675 153 1736 408 333 611 1083 733 96 865 1164 912 604 1002 1282 514 1939 1239 723 1067 1553 159 1147 2006 1650 1382 1312 1617 710 1029 1367 1877 1462 1067 583 495 605 925 435 1730 1263 1005 982 1862 1422 1861 732 1593 1514 1520 1496 808 192 973 681 335 610 1206 631 1770 243 1255 1434 966 1257 845 1042 892 781 1521 1347 1324 1369 758 1435 556 842 1804 715 358 445 1543 909 219 88 1125 66 1518 737 1623 1038 1036 891 716 1916 813 22 894 754 1504 989 759 58 1579 1778 1844 923 53 1097 1833 1892 1282 1342 1503 1105 1807 1019 689 1118 870 560 1170 1811 1548 1282 1007 1282 845 1734 2004 1072 1954 982 1650 788 1224 594 210 1971 1400 1487 119 1685 734 282 1948 404 456 299 382 1888 687 147 1616 1398 346 1444 1206 1968 637 960 717 1522 1655 1456 1817 982 1325 1325 362 526 1985 1384 1218 446 538 1767 406 1730 667 911 286 1472 319 240 957 709 767 1838 38 242 1516 323 1198 701 1484 799 1249 87 1431 1523 1439 1435 1556 1830 335 1222 130 1084 35 443 1737 479 1678 481 1545 194 318 1034 463 1458 1132 1562 867 1111 1793 1271 207 199 1466 657 529 180 239 825 818 668 1242 1264 1597 1306 1776 1319 969 125 23 483 1426 1628 1592 1777 881 807 434 44 619 1364 1810 312 662 271 1507 418 247 1023 1862 314 289 1668 1278 634 1012 247 98 2007 669 1037 1418 540 767 444 1170 874 1503 1291 749 1460 1016 1995 1128 21 1304 1445 692 1528 2013 710 1423 13 1287 1857 116 566 349 1029 861 130 170 656 1724 1666 1461 1326 488 354 1210 1876 326 976 1514 1116 1593 841 456 974 1864 1414 497 737 1234 52 1788 994 1301 1955 687 310 1695 1879 1127 1570 520 1915 768 641 1959 1908 260 1971 500 792 1250 1784 1192 1172 662 296 654 836 1356 206 20 18 1411 1225 954 827 810 1931 963 443 989 939 920 631 1664 958 1524 316 1477 97 45 468 1770 431 272 659 170 171 1061 1196 1188 1098 84 1582 1387 471 1962 73 1111 697 763 1644 1109 322 240 1079 970 1639 1423 1961 1487 1440 498 1897 580 1711 1308 1081 779 1762 456 864 748 268 1767 387 1269 152 1608 958 1697 890 1228 1108 1070 1192 347 1557 579 1044 1563 1517 852 1523 1345 423 1624 1748 1418 1822 170 1194 1995 921 1522 957 1660 635 1084 116 1914 809 1499 1387 1237 1500 1270 248 1770 1815 352 1108 904 1031 1242 947 471 761 666 1660 513 1311 419 258 1457 1969 1287 1098 1017 419 99 1078 1782 1424 1999 629 284 1832 182 735 413 1412 1166 599 44 1328 997 1025 1411 593 290 28 25 1247 801 1050 1661 1387 1549 1720 1857 1858 178 1829 1040 1981 909 762 798 1062 27 879 445 676 20 831 1950 801 234 450 870 623 1747 309 619 118 1485 1744 1417 1525 1309 649 1171 1992 413 178 1120 831 1792 193 184 1548 1151 1786 1315 469 1615 1530 514 1243 794 624 876 1357 654 559 1160 834 497 1033 1880 1771 687 1907 1088 1211 1992 1801 1290 1382 1787 1703 199 832 120 999 330 982 1910 765 741 1495 1393 856 954 1472 472 437 1266 849 1062 267 13 402 1264 1041 969 1346 1050 1141 186 1221 371 1774 1925 1244 1214 1478 572 1473 790 1518 1840 489 388 1163 409 1441 1858 952 459 1830 1897 1972 636 793 1919 1092 266 1216 360 69 1700 227 350 1342 343 1823 301 1562 1329 650 1778 436 430 1905 401 1688 1186 924 1171 650 973 1258 872 41 1330 1872 1275 1569 1703 1985 357 132 18 1612 1933 1150 1196 459 501 109 1575 1283 1319 1044 433 275 1487 632 100 253 2011 1321 1696 720 1407 324 46 848 1794 1274 715 1807 851 745 711 1196 744 381 1124 1462 239 385 1617 1082 660 703 982 82 1383 1097 1537 587 699 1682 1374 1624 878 1548 378 1981 1325 740 426 692 314 894 1932 1108 1501 2006 913 1384 1298 13 1695 1186 393 1343 907 1106 1895 5 1321 920 210 1125 1956 966 1991 411 1685 1017

[入力例]

1 0

[出力例]

1 1

※AtCoderテストケースより

[入力例]

0 0 0

[出力例]

0 0 0

※AtCoderテストケースより

[入力例]

0 1 0 1 0

[出力例]

0 2 0 1 3

※AtCoderテストケースより

[入力例]

0 1 0 1 0 1 0

[出力例]

0 5 0 1 0 5 4

[入力例]

0 0 1 0 0 0 1 0 1 0 0

[出力例]

0 7 10 5 5 3 4 1 6 6 8

[入力例]

0 0 1 0 0 0 1 0 1 0 0 1 1 1 0 0 1

[出力例]

0 14 1 1 4 15 12 7 16 0 16 12 13 10 5 0 10

[入力例]

331

0 0 1 0 1 1 1 0 1 1 0 0 0 1 0 0 0 0 0 1 1 0 1 0 1 0 1 0 1 1 0 1 1 0 1 0 1 1 0 1 1 1 0 1 1 1 1 1 0 1 0 1 0 0 0 0 0 1 0 0 1 1 1 0 0 1 1 0 1 1 0 0 1 1 1 0 0 0 0 1 1 1 1 1 0 1 0 1 1 0 1 1 1 0 1 0 1 1 1 1 0 1 0 1 0 0 1 0 1 1 1 0 1 1 1 1 0 0 0 1 0 0 0 0 0 0 1 1 0 0 1 0 1 1 1 1 1 1 1 1 0 0 0 1 0 1 0 1 0 0 0 1 1 1 0 0 0 0 0 0 1 0 0 1 0 0 1 1 1 1 1 0 0 1 0 1 0 0 1 1 0 1 1 1 0 1 0 0 0 1 0 0 0 0 1 0 1 1 1 0 1 0 0 0 1 0 1 1 1 1 1 1 1 1 0 1 0 1 1 1 0 1 0 0 1 1 0 1 1 1 0 0 1 0 1 0 0 1 1 1 1 0 0 0 0 1 1 0 0 0 1 1 0 1 1 0 1 0 1 0 1 1 1 0 1 0 0 0 1 0 1 0 1 0 1 1 1 1 0 1 0 1 0 1 1 1 1 0 0 0 0 0 0 1 0 1 1 0 1 1 1 0 0 0 0 0 1 1 0 0 0 0 1 1 0 1 1 1 1 1 1 0 1 1 1 0 0 0 0 1 0

[出力例]

0 270 29 28 211 326 92 161 309 74 132 135 28 242 187 243 185 253 58 165 253 31 0 297 289 236 323 67 2 207 156 248 113 174 12 12 176 254 118 107 176 253 6 283 218 8 261 79 115 48 156 165 23 185 294 122 45 217 32 237 135 110 224 299 104 246 99 243 153 53 202 322 54 201 123 282 125 68 308 248 73 263 16 274 261 102 67 57 21 1 5 104 46 117 74 11 324 59 95 248 100 110 203 304 170 276 252 317 184 213 312 213 163 138 21 289 167 316 119 145 275 191 206 63 12 200 204 204 294 242 224 23 308 208 30 195 42 192 232 293 162 96 8 15 173 291 232 36 125 110 239 115 126 230 18 1 177 23 185 23 219 71 207 98 254 3 184 306 324 45 290 137 81 174 8 135 183 237 179 81 32 202 115 204 304 271 252 188 135 158 239 303 123 100 69 326 63 75 188 43 109 132 233 77 43 66 86 153 121 63 85 77 66 143 180 197 145 51 261 308 44 236 202 87 173 292 254 43 168 21 165 320 196 122 91 258 212 104 6 280 210 23 150 176 127 6 31 137 189 140 113 97 325 57 100 212 271 308 80 7 107 318 164 25 42 200 2 210 19 170 213 258 270 10 58 200 88 268 205 83 164 261 50 55 262 29 61 68 16 316 276 260 237 48 13 208 158 248 18 187 304 265 307 234 109 207 259 46 322 91 64 119 185 128 159 142 273 171 255 270 105 92 285 221 206 101 232 52 156 62 156

[入力例]

2027

0 1 1 1 0 1 0 0 1 0 1 1 0 0 1 0 0 1 0 0 1 1 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 0 1 0 1 1 1 1 1 1 1 1 0 1 0 1 1 1 1 0 1 1 1 1 1 0 0 0 1 0 0 1 0 0 1 0 1 1 0 0 1 0 1 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 1 0 1 0 0 1 0 1 0 0 0 1 0 1 1 1 0 0 0 0 1 1 0 1 1 1 0 1 1 0 0 1 0 1 1 0 0 1 1 1 0 1 0 1 1 1 1 1 0 1 0 0 0 1 1 1 1 0 0 1 0 1 1 1 0 0 0 1 0 0 1 1 0 0 0 0 0 1 1 1 0 1 0 1 0 1 0 1 0 0 1 0 0 0 0 0 0 1 1 0 1 0 1 1 1 1 0 1 1 1 1 0 0 0 1 0 0 0 0 1 1 1 1 1 0 0 1 1 0 0 0 1 1 0 0 1 1 0 1 0 0 1 1 1 1 0 0 0 1 1 0 0 1 1 0 1 1 1 0 1 0 1 0 0 1 1 0 1 1 0 1 0 0 0 0 0 0 1 0 0 1 0 1 0 1 1 1 1 0 1 1 0 1 1 0 1 0 1 1 0 1 1 0 1 0 1 1 0 1 0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 1 0 1 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 0 1 0 0 0 1 1 1 0 0 0 1 1 0 1 1 0 0 0 1 1 0 0 0 0 0 0 1 0 1 0 1 0 1 1 0 1 1 0 1 1 0 1 1 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 1 1 1 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 1 1 1 0 1 0 1 1 0 0 1 0 1 1 1 1 0 1 1 1 1 1 0 1 0 0 1 1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 0 1 0 1 0 0 1 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 1 0 1 1 0 0 1 1 1 1 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 1 0 1 0 1 1 0 1 1 1 1 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 1 1 1 0 0 1 1 0 1 1 1 1 0 0 1 0 1 1 1 1 0 1 0 1 0 1 1 0 0 1 0 1 0 0 1 0 0 0 1 0 1 1 0 0 0 0 1 0 1 0 1 0 1 0 1 1 0 1 1 0 0 1 1 0 0 1 1 1 1 1 1 1 0 1 1 0 0 1 0 1 1 1 0 1 0 1 1 1 0 0 1 1 1 0 1 1 1 0 0 0 1 1 0 1 1 1 0 1 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 1 1 0 1 0 1 1 0 0 0 0 0 1 0 1 0 0 0 0 1 1 1 1 1 0 1 0 1 1 1 0 1 1 1 1 1 1 1 0 0 1 1 0 1 1 0 0 1 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 0 1 1 0 1 0 0 1 0 0 0 0 0 1 1 1 1 0 0 1 0 0 0 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 0 0 1 0 1 0 0 0 1 1 0 0 0 1 0 0 0 0 0 1 1 1 0 0 1 0 0 0 1 0 0 0 0 1 0 1 0 1 1 1 1 0 1 1 1 0 1 0 0 0 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 0 1 1 1 0 1 1 0 0 0 1 1 1 0 1 0 0 0 0 1 0 1 0 1 1 0 0 0 1 1 0 0 1 1 1 0 0 0 1 0 0 0 0 0 1 1 0 1 1 0 1 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 1 0 0 1 1 0 0 1 1 0 0 0 1 1 0 0 1 0 0 0 1 0 0 1 1 1 1 1 0 0 0 1 1 0 1 0 1 0 1 0 1 1 1 0 1 1 1 0 1 1 1 1 1 0 0 1 1 0 1 0 0 1 0 0 1 1 0 0 0 1 0 0 1 1 0 0 1 1 1 1 0 1 1 0 1 0 1 0 1 0 1 0 0 1 0 1 0 0 0 1 0 1 0 0 1 1 0 0 0 0 0 1 0 0 0 1 1 1 0 1 0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 1 0 1 1 1 0 0 1 1 1 0 1 1 0 1 0 1 0 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 0 1 1 1 0 1 1 0 1 0 1 0 1 1 0 0 1 0 0 1 1 0 1 1 0 1 0 1 0 0 1 1 1 0 0 0 0 0 0 1 0 0 1 0 0 1 0 1 1 1 0 0 0 1 1 0 1 1 0 1 0 0 0 0 1 1 1 0 0 1 1 0 1 0 1 0 0 0 1 0 1 0 1 1 1 0 0 0 1 1 1 0 1 0 1 1 1 0 1 1 0 0 0 1 0 0 1 0 0 1 1 0 1 1 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 1 0 1 0 0 1 0 0 1 1 1 0 1 0 0 1 0 1 1 0 1 1 1 1 0 0 0 1 1 0 0 0 1 1 0 1 0 0 0 1 1 1 0 0 1 1 1 0 1 0 1 0 1 1 0 0 0 0 1 1 0 1 1 0 1 1 1 1 0 1 1 0 0 0 1 0 0 1 1 1 0 1 1 0 0 0 0 1 1 1 0 1 0 0 0 1 1 0 0 0 0 0 1 0 1 1 1 0 1 0 1 1 0 1 1 1 1 0 1 0 1 0 0 1 1 0 1 0 0 0 1 1 0 0 1 1 1 1 1 1 0 1 1 0 1 0 1 0 1 0 1 1 1 0 0 0 1 1 0 1 1 1 0 1 1 0 0 0 0 0 1 0 1 1 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 0 0 1 0 0 0 0 1 0 0 1 0 1 0 1 1 0 1 1 1 1 1 0 0 0 0 0 1 0 1 1 1 0 0 1 1 1 1 1 0 1 0 1 1 1 1 0 0 1 0 0 1 0 1 0 1 1 0 0 1 1 0 0 1 1 1 1 0 1 1 1 1 0 0 1 0 0 0 1 1 0 0 1 0 1 1 0 1 1 1 0 1 1 1 0 0 1 1 1 0 0 0 0 0 0 1 1 0 0 0 0 1 1 1 0 0 0 1 1 0 1 1 0 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 0 1 1 1 1 0 0 1 0 1 0 0 0 1 1 0 1 1 0 0 0 0 1 0 1 1 1 1 0 0 1 1 0 0 1 0 0 1 0 1 0 0 1 0 0 1 0 0 1 0 1 1 1 0 0 1 1 0 1 1 0 1 0 0 1 1 0 0 0 1 1 0 1 1 0 0 1 1 0 0 0 1 0 1 1 1 0 1 0 1 1 1 1 1 0 0 0 1 0 1 1 1 1 0 0 1 0 0 1 1 0 0 1 0 0 0 0 1 1 1 0 1 0 1 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 1 0 1 1 1 1 1 0 0 1 1 1 0 0 1 1 0 0 1 1 0 0 1 0 0 0 1 1 0 1 0 0 1 1 1 1 1 1 0 0 1 1 0 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 0 1 1 0 1 0 0 1 0 0 0 0 0 1 1 1 0 0 1 0 1 1 0 0 1 0 1 1 0 0 1 1 0 0 0 0 0 0 1 0 0 1 0 0 1 0 1 1 0 1 0 0 1 1 1 1 1 1 1 0 0 1 0 0 1 1 0 0 0 0 0 1 1 0 1 1 1 1 0 1 1 0 1 1 1 0 1 1 0 1 0 1 1 0 1 0 1 1 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 0 0 1 0 0 0 1 1 0 1 1 0 1 1 1 0 1 1 1 0 1 0 0 0 1 1 1 0 0 1 0 0 0 1 0 1 1 0 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 0 0 1 0 0 1 0 1 0 1 0 1 0 1 1 1 1 0 0 1 0 0 0 0 0 1 0 1 0 0 1 0 1 1 0 0 0 0

[出力例]

0 601 1616 1772 2023 1856 752 1059 1602 1265 1361 1383 1006 1934 149 1935 1792 1675 1540 611 1508 47 587 787 1528 1616 1145 908 1096 1641 1056 109 1764 236 517 1129 1334 144 178 1566 131 1763 1702 1394 564 451 496 1873 1630 892 64 811 989 1986 402 202 1514 545 830 1373 1132 1817 260 693 971 1255 1516 860 655 1351 1193 1652 1912 307 1671 1957 651 424 512 497 215 1197 341 1942 420 372 1167 337 1385 656 483 1795 1069 1104 1242 579 990 434 824 1176 1153 1115 258 607 1482 792 47 1812 1800 1575 1713 609 203 1389 1698 1016 1502 1224 1101 68 59 255 1984 307 72 390 631 1926 605 1273 882 1282 294 1885 1653 605 179 21 1839 1820 845 458 1332 583 575 537 37 601 28 56 1179 640 1483 1937 1994 1818 343 1513 1497 247 320 1953 707 1832 1822 874 390 1676 861 1469 853 730 422 756 180 0 382 1615 173 76 236 1868 281 988 1818 1180 583 471 1536 1283 1641 1668 715 1874 647 1119 1054 1781 1649 1150 1401 1991 168 1784 403 1110 1919 1312 1216 554 1513 1537 362 961 216 773 1828 1505 1604 1869 2005 1955 1381 1188 1465 1328 944 1760 1435 1558 1730 1778 320 1821 1869 275 984 1899 987 605 1533 677 1208 667 224 1420 1453 1519 441 814 968 996 925 1301 2001 1169 682 460 1039 1798 1358 1572 231 114 440 652 454 138 393 220 1140 1009 1435 1980 1723 775 1408 1954 233 416 1919 1001 1802 176 1144 1151 290 534 1523 1717 315 338 916 410 835 1095 120 922 460 1141 437 1951 274 1639 873 1772 179 1320 1916 703 356 1761 1465 339 1795 1464 1263 252 766 1853 841 536 2002 1099 1924 95 1966 1742 424 1404 476 144 1861 1340 667 2018 1554 1998 983 557 1160 828 200 1697 1833 291 876 1743 994 1406 230 1151 1351 1360 473 799 324 1473 190 1772 921 1345 499 7 174 246 301 1164 1594 575 1167 1998 1302 1561 814 202 1082 1895 21 1827 216 258 122 437 1914 1334 1534 236 137 1594 1814 306 414 628 846 1603 608 191 921 687 700 1002 858 1547 1174 1476 1936 1807 1139 1416 738 618 941 653 1751 1573 1033 541 1774 341 1658 1137 1312 476 1164 612 1262 49 1347 1825 1864 1002 804 1167 1067 639 660 701 1408 1011 1137 1451 1766 1704 926 725 1987 97 143 405 408 977 1431 1526 1668 1506 1732 1549 39 1621 1586 1694 1177 1485 1806 519 721 1086 644 1726 1529 1666 1029 1952 138 124 438 1397 755 1942 1805 1642 369 905 1487 1786 1635 71 1523 1160 1125 1690 768 1774 1711 1549 1079 761 777 2020 1944 1873 158 661 1907 787 291 687 1644 817 1188 329 607 1998 377 849 890 109 661 614 1914 1052 1806 1300 1361 1198 641 359 653 516 57 1819 1017 330 80 1420 709 466 28 1140 1327 621 955 1924 152 79 859 703 1222 1611 905 654 1686 408 541 1163 1638 1749 676 980 994 686 1615 551 1036 1761 1048 292 778 638 492 772 1127 376 1727 585 847 413 1854 1682 252 1106 763 738 646 291 1700 2024 159 1330 671 1055 1472 241 1877 1127 809 1407 945 1628 1882 1022 802 738 1597 735 1620 1287 867 462 1367 1909 732 704 406 711 530 407 172 605 405 1641 1175 366 1722 1272 905 1094 1218 1452 1275 1333 1323 1932 1926 1294 1166 823 1942 408 1186 1328 1134 842 465 939 1420 957 1356 1417 313 712 720 1954 994 81 53 132 659 507 1440 1735 1666 1396 84 886 1512 441 314 1954 1734 1812 1660 1580 782 722 671 1810 1311 392 269 428 1587 263 1162 788 861 252 1121 618 1082 827 923 1783 97 319 1167 292 1861 1993 1344 386 1812 1430 608 223 1883 1767 768 1612 297 1439 1852 426 1231 1056 994 1227 140 1874 921 1953 361 1004 597 649 523 472 188 906 1516 1581 282 1727 1998 276 1204 943 810 1845 894 981 1223 63 1524 1222 827 1321 366 1137 425 1268 1484 307 1004 1123 693 837 564 740 891 1773 1350 685 825 368 1811 1338 1866 1013 217 303 1357 1421 851 626 372 517 189 49 1153 279 1532 1431 1652 1910 1574 1224 1739 1815 68 1845 1722 226 1248 1571 53 801 1484 348 1155 905 667 157 884 563 1438 1819 1672 1011 261 136 27 1300 1974 1807 317 380 1271 1328 2026 1680 1545 1448 462 1431 542 1794 1465 1293 573 1080 41 1298 1236 365 2011 1910 525 509 1604 818 28 1417 1756 1714 1858 22 1946 1096 573 58 1957 607 670 74 1749 1207 232 1171 483 1685 128 1302 36 1614 1639 685 263 1845 1651 1904 523 855 452 694 365 654 1475 1893 945 1710 1108 1225 21 1411 1703 827 1540 317 1203 318 1690 1631 473 494 1237 850 565 186 831 122 1968 1220 706 1757 1136 656 301 1510 2022 1534 610 1439 399 1137 974 825 1001 941 1337 494 509 230 1868 1345 663 164 392 501 676 1077 1144 1034 1383 442 69 382 868 42 1789 1656 1825 649 824 1096 244 1371 838 1 972 770 777 84 398 1375 1267 834 273 618 40 1538 1411 1214 398 1148 1489 1777 945 587 447 82 1201 60 1538 210 374 1480 124 376 1194 281 1523 1995 322 142 485 1819 994 334 1198 200 1534 267 333 569 1348 162 472 812 454 478 722 627 1355 186 1143 518 23 1371 497 1403 1136 2025 1550 917 1736 1489 131 803 690 422 404 1043 848 770 168 369 1814 1606 1509 130 782 1776 1808 467 1316 1141 1081 1574 1245 905 1573 1504 178 866 1547 869 1084 1900 1975 111 575 1418 313 1359 43 1792 233 8 1325 1055 1942 1327 2004 431 952 1989 1793 361 935 647 1016 1718 1348 1791 867 1291 1747 1362 271 1957 439 174 1318 1202 1169 779 2025 156 921 201 722 825 416 395 484 138 708 471 315 1606 896 1309 184 1794 426 293 221 1087 643 1558 819 1577 1170 555 567 1997 1137 870 959 1050 931 1149 1699 1425 1999 399 244 1896 340 1793 1689 466 96 316 961 257 894 1879 1566 1727 595 356 1887 1702 1180 984 1939 1770 1244 825 1059 1189 1350 618 1901 1522 510 407 320 776 1226 1 1608 1542 826 1651 512 464 1628 49 759 703 815 1261 697 42 748 1654 1266 1869 776 655 182 696 1756 1187 1726 813 6 1995 1892 908 1496 18 315 1712 1322 1893 243 185 415 364 76 916 105 1862 390 1416 854 1553 1748 319 1696 1760 1960 1380 1365 1078 841 1300 1816 1142 448 1216 1779 305 183 295 946 224 1226 1011 1852 1326 371 814 1529 1256 1380 186 482 1877 1622 1560 815 1280 1708 1375 1805 1273 1675 153 1736 408 333 611 1083 733 96 865 1164 912 604 1002 1282 514 1939 1239 723 1067 1553 159 1147 2006 1650 1382 1312 1617 710 1029 1367 1877 1462 1067 583 495 605 925 435 1730 1263 1005 982 1862 1422 1861 732 1593 1514 1520 1496 808 192 973 681 335 610 1206 631 1770 243 1255 1434 966 1257 845 1042 892 781 1521 1347 1324 1369 758 1435 556 842 1804 715 358 445 1543 909 219 88 1125 66 1518 737 1623 1038 1036 891 716 1916 813 22 894 754 1504 989 759 58 1579 1778 1844 923 53 1097 1833 1892 1282 1342 1503 1105 1807 1019 689 1118 870 560 1170 1811 1548 1282 1007 1282 845 1734 2004 1072 1954 982 1650 788 1224 594 210 1971 1400 1487 119 1685 734 282 1948 404 456 299 382 1888 687 147 1616 1398 346 1444 1206 1968 637 960 717 1522 1655 1456 1817 982 1325 1325 362 526 1985 1384 1218 446 538 1767 406 1730 667 911 286 1472 319 240 957 709 767 1838 38 242 1516 323 1198 701 1484 799 1249 87 1431 1523 1439 1435 1556 1830 335 1222 130 1084 35 443 1737 479 1678 481 1545 194 318 1034 463 1458 1132 1562 867 1111 1793 1271 207 199 1466 657 529 180 239 825 818 668 1242 1264 1597 1306 1776 1319 969 125 23 483 1426 1628 1592 1777 881 807 434 44 619 1364 1810 312 662 271 1507 418 247 1023 1862 314 289 1668 1278 634 1012 247 98 2007 669 1037 1418 540 767 444 1170 874 1503 1291 749 1460 1016 1995 1128 21 1304 1445 692 1528 2013 710 1423 13 1287 1857 116 566 349 1029 861 130 170 656 1724 1666 1461 1326 488 354 1210 1876 326 976 1514 1116 1593 841 456 974 1864 1414 497 737 1234 52 1788 994 1301 1955 687 310 1695 1879 1127 1570 520 1915 768 641 1959 1908 260 1971 500 792 1250 1784 1192 1172 662 296 654 836 1356 206 20 18 1411 1225 954 827 810 1931 963 443 989 939 920 631 1664 958 1524 316 1477 97 45 468 1770 431 272 659 170 171 1061 1196 1188 1098 84 1582 1387 471 1962 73 1111 697 763 1644 1109 322 240 1079 970 1639 1423 1961 1487 1440 498 1897 580 1711 1308 1081 779 1762 456 864 748 268 1767 387 1269 152 1608 958 1697 890 1228 1108 1070 1192 347 1557 579 1044 1563 1517 852 1523 1345 423 1624 1748 1418 1822 170 1194 1995 921 1522 957 1660 635 1084 116 1914 809 1499 1387 1237 1500 1270 248 1770 1815 352 1108 904 1031 1242 947 471 761 666 1660 513 1311 419 258 1457 1969 1287 1098 1017 419 99 1078 1782 1424 1999 629 284 1832 182 735 413 1412 1166 599 44 1328 997 1025 1411 593 290 28 25 1247 801 1050 1661 1387 1549 1720 1857 1858 178 1829 1040 1981 909 762 798 1062 27 879 445 676 20 831 1950 801 234 450 870 623 1747 309 619 118 1485 1744 1417 1525 1309 649 1171 1992 413 178 1120 831 1792 193 184 1548 1151 1786 1315 469 1615 1530 514 1243 794 624 876 1357 654 559 1160 834 497 1033 1880 1771 687 1907 1088 1211 1992 1801 1290 1382 1787 1703 199 832 120 999 330 982 1910 765 741 1495 1393 856 954 1472 472 437 1266 849 1062 267 13 402 1264 1041 969 1346 1050 1141 186 1221 371 1774 1925 1244 1214 1478 572 1473 790 1518 1840 489 388 1163 409 1441 1858 952 459 1830 1897 1972 636 793 1919 1092 266 1216 360 69 1700 227 350 1342 343 1823 301 1562 1329 650 1778 436 430 1905 401 1688 1186 924 1171 650 973 1258 872 41 1330 1872 1275 1569 1703 1985 357 132 18 1612 1933 1150 1196 459 501 109 1575 1283 1319 1044 433 275 1487 632 100 253 2011 1321 1696 720 1407 324 46 848 1794 1274 715 1807 851 745 711 1196 744 381 1124 1462 239 385 1617 1082 660 703 982 82 1383 1097 1537 587 699 1682 1374 1624 878 1548 378 1981 1325 740 426 692 314 894 1932 1108 1501 2006 913 1384 1298 13 1695 1186 393 1343 907 1106 1895 5 1321 920 210 1125 1956 966 1991 411 1685 1017

■参照サイト
AtCoder Beginner Contest 137

C++の練習を兼ねて, AtCoder Beginner Contest 137 の 問題F (Polynomial Construction) を解いてみた.

コメントを残す コメントをキャンセル

C++の練習を兼ねて, AtCoder Beginner Contest 137 の問題F (Polynomial Construction) を解いてみた.

コメントを残すコメントをキャンセル