4252021-11-03 09:01:45hentesoposszumToronyépítés (1,1,3,3)cpp11Accepted 50/5012ms9444 KiB
#include <iostream>
#include <vector>

using namespace std;

int main() {
    vector<int> l = {0,2,4,10,24,56,132,312,736,1736,4096,9664,22800,53792,126912,299424,706432,1666688,3932224,9277312,1677892,11220232,574872,4505528,11241412,3422460,15855976,13774560,14183932,19659600,6237996,423640,19956372,11968520,4574212,8640952,798728,10745880,18563556,18514460,18100464,12697716,1794028,19578876,3922860,11433776,1394980,10635680,3718696,10227352,1305848,10049088,132664,2877024,5642116,11549560,8643060,8360244,19609500,16084904,8470080,15738944,3017372,2764796,16797372,19419380,3948136,1070800,560144,9016560,20174720,1049512,20132144,19983404,1645616,3135304,5817200,14925632,15911764,3037712,15716580,2626364,11328152,13669248,12381116,6998320,914920,6381964,6550460,14930760,2205232,17511384,4253964,12918392,229228,8966384,3349336,7157128,12036916,10562396,15228940,14111496,8927568,7892800,3588376,4821780,5219052,17614856,4453056,19344216,13287820,15271644,8601396,3358216,17049612,10881800,8269924,10218856,1781096,20102040,11468,3585128,6954120,13931176,14822500,3133024,13918292,17061368,20178676,7563612,8829744,17596624,9900256,17249892,9062708,17715820,9301100,16517508,7836332,14064756,534204,16741072,981332,3031072,19334180,210808,6483760,11215664,2642836,18253192,18517496,1900448,20097172,16599012,16788812,13141644,19061096,11069492,8002056,13706088,9130944,14055892,15103744,8049160,3789888,17577156,10832416,9034500,12803096,6850808,11560508,8306992,10105492,2911784,2227444,4455764,14735096,13714972,16131364,1102596,9425028,10692568,3380220,5400388,11975804,10501940,11594548,6720488,14234748,11238376,15707620,19464520,775468,12756068,3810852,9172640,3437200,14496104,6917272,498836,9779772,13183980,7155524,13660484,13268712,428256,7967372,2051952,4960416,5645468,15394840,290296,11871528,14112520,8595524,513888,9042708,15066356,10950380,19776068,9054524,19799700,18521212,14731256,8431588,13485384,16013064,8469088,3488728,18793476,14104912,14977172,6910972,1611552,12967340,19546516,1895920,9516412,17705640,18993012,16598632,7978220,13522248,19821544,15179312,16982904,12978572,15895552,5126588,16000212,3161204,16575584,4521268,15364944,3250732,15544000,1187564,8876592,8420968,19217064,15767096,7955912,13925736,18965448,13422504,14276264,5853100,18341100,4604404,704900,17881892,4552376,10514552,16372672,1429880,3678756,19892748,2225040,11807592,2770356,9990792,3176552,11893816,3349000,13051104,9469624,5427140,16746380,12011792,14667756,2197948,8209372,5334040,15063976,6126480,2710932,15339708,2512160,10446184,11151568,7117348,14916956,11716832,17458252,4120092,11463740,17423768,2667504,8052380,10532080,6189060,8272772,17399596,6757096,9849628,14078232,1250440,1990028,11926412,6143596,16267248,15967104,3801184,19926756,11157396,9707052,18847400,19589376,18172640,13409756,5367940,6660944,19931292,10178248,13468276,6168812,12484012,11484360,15096236,14740280,12029064,13830384,16721112,17080136,1190716,15613548,4757044,11895520,14597920,18499820,160356,9306444,15192312,10495228,19393236,8540772,17861892,13879932,4421192,4145952,15841660,105488,8502880,8268864,16748704,10082952,16493524,5854132,11664060,15894952,3077952,9273916,9917520,5780836,9899396,19423724,9988904,19566492,17350108,14257808,7018276,8316552,4728504,3283452,2989900,15436808,17230412,20408,10704324,15449256,10729220,2446872,15582148,12202520,9088676,8921432,1827688,1622620,877996,5411368,14067976,9681836,9976300,7668336,14490236,8512856,12152276,12864808,2335112,8764668,2838736,10347696,18014620,1286496,3058276,1725576,6024144,18164840,19570724,10769520,17448504,13408132,7935088,10346968,7089984,9840036,20163900,14087552,7434960,14777504,17309896,9069496,7273784,8747144,15423172,4973696,7231572,4889272,19725936,13494800,16558036,11937620,10444624,13585104,10625232,1719496,10399092,1628432,6695856,13979788,11006332,15194268,17927896,17448240,4654692,4744960,3966184,17241752,3553208,15038784,3930748,14967912,19593176,6627632,2770872,4307880,1660916,8863576,6132804,15587440,8481816,9019132,8792928,14339380,6296808,9969364,8197272,8778052,17284724,10543776,18433548,10806220,2279776,1006432,3415196,11389944,4582644,15995680,14351032,17657244,6675524,1632896,18370172,9671176,2398036,1116200,1364644,7525360,17283120,17085420,8801344,11748712,17248048,11678568,6434344,6944568,17036164,6520800,6720628,7093368,7018228,7267604,8511836,10850020,16025140,8653736,18797404,9014764,15126892,7218268,12255956,14345480,2707280,9716364,7703472,611396,445412,16297768,13608220,7897156,7969632,2735488,1055180,18049624,1150008,4410376,4499784,11299584,11209812,11209084,4597120,11403756,4805464,18805168,19997632,9185976,15562072,10489084,19140012,8773844,18315748,14281196,5689864,7591008,3324192,18028112,10818024,8074324,11784656,4785144,5508828,14376860,18113900,6825240,1983984,19985660,13201584,10161028,19873160,5519164,11150276,1416548,13871424,9623184,1869356,11271452,1369056,6476824,15286444,13100892,18945324,7833212,1447992,366416,16399256,15484388,11491500,15361296,1061044,4894980,92336,2306760,14403480,8781524,1966460,12529772,2202376,8337672,1314672,7034096,10533428,3486092,830268,2517284,12006752,5463932,15962432,15518152,1543952,14802660,11300,3110504,15616220,11044932,8100764,7013752,15907260,7595832,9009060,9412424,13806404,5210712,9036164,5264920,741156,19554640,9218904,19920120,18319196,14655984,8521884,13261944,15415640,7454832,1013336,12647844,19995244,1596944,8279468,16129208,15242196,6623112,5084424,233024,13712272,17383284,15022508,17049344,8234932,6094664,5867800,7995356,7969932,7465356,10711316,17152388,8815272,18843068,11360588,20141612,17339036,16979032,13610964,1269676,16287308,19376328,871792,14108092,6338516,14420616,16637200,5531216,19693556,12031188,14914700,8586188,814536,11248364,19458996,126848,2540316,3578408,7410512,19901656,6539912,7690740,14764576,2188760,19759000,8416828,1001068,1099920,19033496,19859020,1497664,642104,582032,4159392,9602992,159940,8638664,16273204,12656180,2169472,16675244,18242632,403992,13948364,3751668,8311320,4099152,15701640,7605704,3199604,17592380,9975952,6141004,7046552,13834900,19741700,13156288,13562160,5977396,18057260,2608516,17171824,9827844,4662612,3248656,5942892,1000900,8499112,8673900,19349600,15277208,7482000,13242984,16620168,7784120,1633992,16298212,7744448,18756880,9479860,14238508,5360452,9470516,6997832,4506460,7743844,9273244,7349300,9976180,18288740,10855864,1243872,18855116,19001744,71016,17642156,12657476,5246876,5357848,15820540,1714616,14144928,19510720,2030456,12140660,2672436,9405784,2672672,10690216,19981892,4888912,10948148,1229756,12237336,5950752,14361016,12776488,17244372,2580452,10503772,15076072,15102940,10793208,11318344,12422352,6010904,14448388,13321264,18454228,5174908,16782236,9842604,9824916,12794088,4853168,9146060,3460080,16626496,11124896,8959844,10752464,3334504,4378588,10051996,6562892,1672852,3239588,19604960,2135408,10749992,79580,4429976,10149828,248708,9357368,18804284,17895876,14086272,5150788,5673112,19308660,8498680,8133476,14464056,5505256,7067356,2642608,16295728,6305952,17897120,7755372,7912540,11199104,17698844,10802552,3583096,2143664,5682324,18530840,928792,13222232,2875820,7609224,1242696,8237032,11482404,5240092,6744140,16242980,2545928,18580136,9015908,2913564,2567184,2956076,11739280,8402820,2507684,8283820,13163172,11131604,18620740,2937500,7928100,12677464,11019820,17685732,96068,2021668,19204692,18391412,405944,19011164,14174828,8951436,15504984,18939408,15361472,1102588,19873884,9840388,1675844,2679240,4829148,13009984,11168340,11784868,9169488,255440,3870508,5869884,12250648,12032204,15594068,15269216,14182624,19133168,8174444,4293920,6433960,9006700,6391132,5440076,8683444,9939044,10548132,18253044,15963960,12603968,1083700,13885212,12558144,7073580,1497368,7900916,9738884,2262396,116516,19710800,3526176,7285384,13572152,13986548,2123648,11181492,9915864,3868916,9890708,19403036,6123688,11818684,1813116,15873608,14964368,13344860,18016720,5331852,17143316,9689748,9833092,13532600,6024480,11505036,9655056,11148964,4887784,8875572,19838964,9033280,15607596,10262796,18382044,7348956,15013396,6160556,6808916,3224408,18769928,10737472,7713652,12546944,6148616,7514428,19912636,11702288,18223324,15641596,14267552,4351428,19775940,7456660,3406068,5943800,6590812,19993760,11454904,15881324,11119844,4729280,800992,3631564,16721688,14835252,16723524,6260100,1770488,16777916,5655816,14852608,2630724,16573080,2221052,9703552,12133048,8498092,16193180,16232240};

    int n;
    cin >> n;

    if (n < l.size()) {
        cout << l[n];
    } else {
        int s = l.size();
        l.resize(n + 1);

        for (int i = s; i <= n; i++) {
            l[i] = (2 * l[i - 1] + 2 * l[i - 3]) % 20210108;
        }

        cout << l[n];
    }
}
SubtaskSumTestVerdictTimeMemory
base50/50
1Accepted0/02ms1748 KiB
2Accepted0/01ms1796 KiB
3Accepted3/31ms1828 KiB
4Accepted3/31ms1832 KiB
5Accepted4/41ms1832 KiB
6Accepted4/41ms1832 KiB
7Accepted4/412ms9440 KiB
8Accepted4/42ms2556 KiB
9Accepted4/41ms1824 KiB
10Accepted4/41ms1824 KiB
11Accepted4/44ms3200 KiB
12Accepted4/412ms9444 KiB
13Accepted4/49ms8404 KiB
14Accepted4/44ms4244 KiB
15Accepted2/21ms1824 KiB
16Accepted2/21ms1828 KiB