#598160 (C++17) No.1561 connect x connect

• 問題: No.1561 connect x connect
• ユーザー: noya2
• 提出日時: 2020-12-29 16:49:24
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: RE (最新)
  AC
  (最初)
• 実行時間: -
• コード長: 20,474 bytes
• コンパイル時間: 2,465 ms
• コンパイル使用メモリ: 213,600 KB
• 実行使用メモリ: 4,932 KB
• 最終ジャッジ日時: 2023-09-07 13:51:57
• 合計ジャッジ時間: 5,439 ms
• ジャッジサーバーID （参考情報）: judge15 / judge14

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 4,380 KB
testcase_01	AC	1 ms; 4,376 KB
testcase_02	AC	2 ms; 4,380 KB
testcase_03	AC	2 ms; 4,380 KB
testcase_04	AC	2 ms; 4,376 KB
testcase_05	AC	2 ms; 4,376 KB
testcase_06	AC	2 ms; 4,376 KB
testcase_07	AC	2 ms; 4,376 KB
testcase_08	AC	2 ms; 4,380 KB
testcase_09	AC	2 ms; 4,380 KB
testcase_10	AC	2 ms; 4,380 KB
testcase_11	AC	1 ms; 4,380 KB
testcase_12	AC	1 ms; 4,380 KB
testcase_13	AC	2 ms; 4,376 KB
testcase_14	AC	3 ms; 4,820 KB
testcase_15	AC	3 ms; 4,824 KB
testcase_16	AC	16 ms; 4,384 KB
testcase_17	AC	3 ms; 4,380 KB
testcase_18	AC	2 ms; 4,376 KB
testcase_19	AC	84 ms; 4,896 KB
testcase_20	AC	4 ms; 4,376 KB
testcase_21	AC	1 ms; 4,380 KB
testcase_22	AC	4 ms; 4,376 KB
testcase_23	AC	2 ms; 4,380 KB
testcase_24	AC	82 ms; 4,828 KB
testcase_25	AC	2 ms; 4,380 KB
testcase_26	RE	-
testcase_27	RE	-
testcase_28	RE	-
testcase_29	RE	-
testcase_30	RE	-
testcase_31	AC	2 ms; 4,376 KB
testcase_32	AC	2 ms; 4,380 KB
testcase_33	AC	3 ms; 4,872 KB
testcase_34	AC	93 ms; 4,932 KB
testcase_35	RE	-
testcase_36	RE	-
testcase_37	RE	-

ソースコード

#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define repp(i,n,m) for (int i = m; i < (n); ++i)
using namespace std;
using ll = long long;
const long long mod = 1000000007LL;
template <typename S>
void rev(vector<S> &ar){reverse(ar.begin(),ar.end());}

struct mint {
    ll x; // typedef long long ll;
    mint(ll x=0):x((x%mod+mod)%mod){}
    mint operator-() const { return mint(-x);}
    mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += mod-a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const mint a) {
        (x *= a.x) %= mod;
        return *this;
    }
    mint operator+(const mint a) const {
        mint res(*this);
        return res+=a;
    }
    mint operator-(const mint a) const {
        mint res(*this);
        return res-=a;
    }
    mint operator*(const mint a) const {
        mint res(*this);
        return res*=a;
    }
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }

    bool operator == (const mint& r) const {
        return this->x == r.x;
    }
    bool operator != (const mint& r) const {
        return this->x != r.x;
    }
    bool operator == (ll& r) const {
        return this->x == r;
    }
    bool operator != (ll& r) const {
        return this->x != r;
    }
    friend ostream& operator << (ostream &os, const mint& y) {
        return os << y.x;
    }
    // for prime mod
    mint inv() const {
        return pow(mod-2);
    }
    mint& operator/=(const mint a) {
        return (*this) *= a.inv();
    }
    mint operator/(const mint a) const {
        mint res(*this);
        return res/=a;
    }
};

struct poly{
    vector<mint> px;
    poly() {
        del0();
    }
    poly(vector<mint> init = {0}) : px(init){
        del0();
    }
    mint get(mint &x){
        mint res = 0;
        rep(i,px.size()){
            res += x.pow(i) * px[i];
        }
        return res;
    }
    void del0(){
        if (px.size() > 1 && px[px.size()-1] == 0LL){
            px.pop_back();
            del0();
        }
    }
    void coef(){
        del0();
        if (px.size() != 0){
            mint a = px[px.size()-1];
            rep(i,px.size()) px[i] /= a;
        }
    }
    void out(){
        rep(i,px.size()) cout << px[i] << " ";
        cout << endl;
    }
    poly& operator+=(const poly &rhs) {
        px.resize(max(px.size(),rhs.px.size()));
        rep(i,rhs.px.size()) px[i] += rhs.px[i];
        del0();
        return *this;
    }
    poly& operator-=(const poly &rhs) {
        px.resize(max(px.size(),rhs.px.size()));
        rep(i,rhs.px.size()) px[i] -= rhs.px[i];
        del0();
        return *this;
    }
    poly& operator*=(const poly &rhs) {
        vector<mint> res(px.size() + rhs.px.size() - 1);
        rep(i,rhs.px.size()){
            rep(j,px.size()){
                res[i+j] += rhs.px[i] * px[j];
            }
        }
        px = res;
        del0();
        return *this;
    }  
    poly& operator/=(const poly &rhs) {
        vector<mint> res(px.size() - rhs.px.size() + 1);
        int re = res.size(); int rh = rhs.px.size(); int pp = px.size();
        rep(i,re){
            res[re - 1 - i] = px[pp - 1 - i] / rhs.px[rh - 1];
            rep(j,rh) px[px.size() - 1 - i - j] -= res[re - 1 - i] * rhs.px[rh - 1 - j];
        }
        px = res;
        del0();
        return *this;
    }
    poly& operator%=(const poly &rhs) {
        vector<mint> res(px.size() - rhs.px.size() + 1);
        int re = res.size(); int rh = rhs.px.size(); int pp = px.size();
        rep(i,re){
            res[re - 1 - i] = px[pp - 1 - i] / rhs.px[rh - 1];
            rep(j,rh) px[px.size() - 1 - i - j] -= res[re - 1 - i] * rhs.px[rh - 1 - j];
        }
        del0();
        return *this;
    } 
    poly operator+(const poly a) const {
        poly res(*this);
        return res+=a;
    }
    poly operator-(const poly a) const {
        poly res(*this);
        return res-=a;
    }
    poly operator*(const poly a) const {
        poly res(*this);
        return res*=a;
    }
    poly operator/(const poly a) const {
        poly res(*this);
        return res/=a;
    }
    poly operator%(const poly a) const {
        poly res(*this);
        return res%=a;
    }
    int deg() {
        return (px.size() -1);
    }
    void reversepx(){
        rev(px);
        del0();
    }
};

vector<mint> cx(ll x, vector<vector<mint>> &rec, int m){
    if (0 <= x && x <= m) return rec[x];
    vector<mint> half = cx(x/2LL,rec,m);
    vector<mint> c2x(2*m-1);
    rep(k,2*m-1){
        repp(i,min(k+1,m),max(0,k-m+1)){
            int j = k - i;
            c2x[k] += half[i] * half[j];
        }
    }
    for (int i = 2*m-2; i >= m; --i){
        rep(j,m) c2x[i-m+j] += rec[m][j] * c2x[i];
        c2x.pop_back();
    }
    if (x % 2LL == 0LL) return c2x;
    vector<mint> ans(2*m-1);
    rep(k,2*m-1){
        repp(i,min(k+1,m),max(0,k-m+1)){
            int j = k - i;
            ans[k] += c2x[i] * rec[1][j];
        }
    }
    for (int i = 2*m-2; i >= m; --i){
        rep(j,m) ans[i-m+j] += rec[m][j] * ans[i];
        ans.pop_back();
    }
    return ans;
}

mint ax(ll x, vector<vector<mint>> &rec, vector<mint> &ini, int m){
    vector<mint> cij = cx(x,rec,m);
    mint ans = 0LL;
    rep(i,m) ans += ini[i] * cij[i];
    return ans;
}

vector<vector<ll>> bm = {
    {1,3,6}
,{3,13,40,108}
,{6,40,218,1126,5726,28992,146642,741556}
,{10,108,1126,11506,116166,1168586,11749134,118127408,187692415,941503421,64334502,171422003,349404639,414370691}
,{15,275,5726,116166,2301877,45280509,889477656,470102989,131617800,543346538,672693081,528691884,433100319,259856352,631703746,121492784,65000963,67868821,431503520,556143263,898859209,822402657,746831347,942022314,42461886,245383965,159194955,442319965,719053964,735342087,986228635,385914410,746460380}
,{21,681,28992,1168586,45280509,732082734,37461992,885687205,403247903,630794366,96311199,188560385,132214957,81864959,656832813,129969437,337127917,885747691,994734031,901081506,113735510,330166803,692897482,221245902,823578678,149151767,513212823,565413378,343413792,552163984,401017125,775469314,768705741,822998669,524634565,141276343,644398112,617812249,791340223,983870515,203398182,625614815,683890375,368195928,142285464,986226417,160965035,405204827,206471233,652493150,587867820,808610901,707659600,22802536,445444835,187616183,160982744,457176050,436730256,169883893,240716120,405440669,340484060,656210817,36771327,96126498,306426249,814430155,444930212,988328253,540530995}
,{28,1664,146642,11749134,889477656,37461992,949940562,34890374,408395779,465431123,169444072,476095424,659247954,873440607,926228358,615656154,946323264,52968124,753942504,466886220,131497623,574943442,651491966,558045773,251030380,281770571,626734327,538734009,338782739,544266404,882070771,638524752,866251039,377115307,677270990,923683803,407681394,135644897,799433050,734586418,252356851,562319011,202766611,459305661,237631148,937873188,999735041,471421437,196454674,548587822,155433694,513218158,425727801,201766011,618282733,853358524,794224019,317787454,420202005,208101995,561508157,165138107,680690785,440574802,642204069,1519935,740668820,993620892,358321040,609591537,544950607,452208170,885834624,821590676,398458087,516061104,713420418,988022777,345184826,285034175,821685364,13669476,704448103,129864472,272789356,791468167,22642555,191074948,725893030,621310461,91319075,716141215,100651620,124026881,366140815,685675711,544588613,31892809,733368799,814661720,416829950,25354705,920576064,404858750,224503153,408647840,32879424,449601451,954308700,384324116,674296838,792515237,188224955,323348585,972509240,558237931,478379644,769454589,5532215,665030504,378063244,50177022,152536855,592606999,936002695,561844587,98320627,393845743,234288387,975460550,94761064,230083310,437478027,493404365,809166706,952865395,30537948,269093029,454344596,528546169,743583991,647074729,593751773,863574928,753557944,354148307,464934709,275033859,450276861,375178856,24286587,880771043,120621725,710396662,135056587,742687865,845401042,8181486,277891374,585736419,570298110,955283694,601817563,141857657,613931527,134904117,127307580,914760872,56527073,515151064,85256390,867641311,644658123,516456196,546485053,695768127,950249035,737354235,328196921,664437558}
,{36,4040,741556,118127408,470102989,885687205,34890374,247777016,233426110,328755371,705627253,787442872,382905968,14599213,54410761,601006292,612557411,15449456,990194963,286282085,699722725,781620769,840139026,489073872,334785849,435236311,109774734,741619354,198733961,979223831,316303898,39151097,758722723,846456337,302710767,751509519,910422866,269441528,739223079,47041872,144990978,835832181,94144832,432122371,718847361,143249505,202420879,524474077,175432350,259981775,949834434,650788361,314338901,308488393,925015945,735629952,55340122,870087004,914406437,652461932,824517283,13384791,734924498,195917202,347913012,345009223,72962601,728865665,529666843,443583543,797807890,499559112,582526183,750449603,794171249,339435367,795879914,610395113,651525515,665256279,771083632,124044838,103256298,555278857,168723782,37135886,926137424,193565944,44104251,848927128,311714530,740363205,103826476,426742610,675142274,731839743,444416323,663478468,724122696,351972777,394976529,438819547,910482232,104665901,409225876,167205682,514913255,760105145,29299318,710711305,114816263,854763814,393789740,110116602,971095517,965304627,656067527,345333181,54369787,393350947,645767328,278297447,584309442,643959646,760481447,306899117,556007296,90782544,501999191,487093902,851119019,214855164,290938704,483935411,931413698,87706720,543982301,557974404,993894344,617966931,450284946,530064541,635450110,955879320,855098870,534537883,745899211,102957101,662330955,760521286,880202513,410332359,896841550,21942388,327590993,607470931,510274101,755158989,271684724,681115728,979634385,116288824,441075062,869557219,498624604,668265455,563569496,411144207,372553915,26571455,299681786,483501145,332251237,514296631,262088005,767350800,242709545,312245270,625558060,630739736,166453361,987400268,534085288,177342293,635886216,360697926,830064107,142999667,796390630,541632626,524331979,832128250,56784302,599770934,420185002,36118708,960687380,886180310,494123322,256629996,167297430,422622751,387880447,805197257,990906673,197392117,409215677,751867399,114891717,20016317,539423303,506437722,420323843,17970683,326175155,607163024,810675077,843118080,586603097,332437402,683685949,604167445,591515392,281318475,78155302,77262870,295568742,84378564,642943804,12418388,229594263,734305604,17384828,186823879,593406287,961690928,25278271,599757507,378599083,885999372,931931154,847818732,310703306,179718037,657210250,145528035,460498835,941558183,335135033,141616629,159440568,260876848,890714211,188331960,684788951,962770200,647749365,692000110,84789890,537064226,34450693,41361159,550194872,245249510,900342927,708273455,11582750,128969774,512056024,55621840,349004103,637116327,221258619,579454604,113893155,576214565,70474670,23918406,481813326,650352628,246808992,284149773,322921320,932867440,994253316,940618752,728504628,428989277,122474883,119546567,24132989,106306057,431011676,611024275,216092722,58878209,120907053,721629563,912245906,362994491,77928369,598179975,862251408,302060801,740845851,459478020,470575531,272055896,271404799,997912850,546477555,102801686,821058456,253389281,766070116,630671870,387593406,363890599,503970373,198459011,993364983,210948547,542855600,819226189,105570790,913838629,104902492,762607730,954174415,72362182,262189042,660554698,644882931,306650491,22189921,453123535,325669077,343206525,974951457,351413353,739439727,691749300,370158155,944047087,188614448,382554560,385741341,62378861,740868823,256532720,721260792,546722312,476298563,606762613,98776597,898445055,605244416,333859175,433695415,401161555,572855900,243667256,85343275,675159111,922771403,996753883,954048792,469148681,19943310,296231983,99393046,204271242,312577414,956614050,159362747,723539464,111719269,894138283,588450712,602782641,981925081,900433722,180543976,267328359,522848269,4196876,67000221,107779275,321728788,528597009,269434052,964941752,949825535,975030569,458728260,549511657,418171228,245570031,648210002,972434486,581872841,635344873,319802131,678265430,806155028,954458488,526854316,847377932,635338258,992797405,996032138,354562941,45336905,183006406,369367986,247817599,491651791,494803388,962480389,263666033,589248787,333002562,984917436,533517314,834849849,760791455,813814450,264438765,491534108,918145304,179243081,160538845,82373668,881806227,278695929,385349193}
};

vector<vector<ll>> recs = {
    {1,1000000004,3}
,{1,0,1000000003,4}
,{1,999999998,16,1000000004,999999985,35,999999981,9}
,{1,11,999999911,162,999999809,255,65,999999375,623,999999932,999999735,230,999999917,17}
,{1000000006,51,999999809,999995793,43282,999810824,402417,223797,996644365,5478389,2595314,986300473,9768918,963869,993847324,16003845,978012096,6980821,8542237,992845888,2622787,997448417,1514014,906816,998379872,800268,999942070,999864370,83965,999973375,5212,999999381,41}
,{1000000006,999999900,1472,57842,555056,999423842,970651995,788104398,778759299,323926634,658083892,324684919,79015122,761957547,595366047,441316887,12688266,201612744,847477522,858041020,451868870,223643742,306695658,77027412,173708838,474147171,793731894,264630700,154797729,871832255,115243176,389288711,223307320,881424398,979848061,936686122,945798937,62008594,810844222,523480614,505535302,983769096,982949299,941916815,776018349,223667986,704805532,228407485,821502095,486024197,720816875,979485868,986504724,922413135,515408927,189284953,275891884,961520636,294959301,670341682,948280892,942059966,549856378,20132019,93346877,968004573,6041799,999257343,60466,999996897,89}
,{1000000006,368,999981690,998922178,128702022,622171930,731677741,106140317,806848365,453924327,836855049,142949576,356971908,814732925,717825556,82972688,288503168,120122643,783939986,761261839,454492864,151480839,707484059,187778239,273758032,418269063,800082505,619069795,76178749,957681166,422561190,738918870,868324775,192285044,790478625,300278697,907983776,336543495,672491101,882414802,406838412,716911716,812021656,479173601,121377445,929977582,842638307,519092571,670937179,172224260,242913036,434770011,81772232,97058866,742622147,887421946,943784930,434994403,535882597,485531550,619565648,837313372,968658812,649591907,706383980,176997673,341889953,628738192,825278395,608672151,320688075,906198878,317067145,809564593,878742507,67173776,657673978,851043661,340084998,881179515,232253314,774737263,247463473,562691692,667156054,890629929,723950318,469838013,807785140,842937545,780020976,388085824,692100536,178612041,384920506,637412043,275031861,65727321,694762825,426116702,90858378,74519735,604011435,653207784,854209867,861488538,56370837,955488408,670965860,178494008,754971238,162264859,876592518,739879036,393937587,733541559,728294606,898584731,967224422,477920513,692790848,73969011,920747536,524709217,445485824,529489817,249104930,616150786,282273016,871078999,899999622,293201017,435241358,462351050,18433516,964904564,67047170,364288897,366586232,378352488,676358445,658876396,421940793,915747648,173877261,495743686,650176206,980414754,933240728,190218477,225769134,538216708,923631714,932091627,109931487,799086382,179972353,905430460,29154215,667161026,882157610,547589032,888811106,844270261,986376596,322699082,709615713,883399554,598871713,188714740,767594257,788348805,53766434,850171195,453154095,482639899,948734189,1292003,999977874,226}
,{1000000006,999999157,999961164,22691715,775147581,410175215,644656057,433867918,942780260,694126350,671278496,910277885,39627068,222159471,196903145,564566673,941751864,923053036,147723557,560425597,390658098,269999304,478209884,171351303,559568908,555958330,578529189,270567479,334046812,664084148,426141415,96693084,880004794,17943766,676144060,47682286,886235137,511505185,690272250,49592688,342788330,281389488,630052818,741527500,147162504,786489218,526080233,844683719,849360143,619409338,956474219,825297899,986361128,329483773,139819119,580748761,200535180,128966905,198638619,115964034,783781320,11302535,818145231,362031149,95306287,873292889,472403755,591992744,155624823,403015989,52369871,612067600,384010750,222103616,396297608,47575767,906775198,836323438,91975976,452204899,142236637,409527286,305068306,438587013,313061425,149815841,176463779,579007269,778594288,368560209,74891220,309307880,602519050,210318962,354371490,105171277,250427019,355580248,190319116,115692310,457939375,112841642,434280888,326239270,454086133,915188806,17980197,400073015,358452800,245408923,569938836,232125716,103712934,205173735,883612510,439686521,194095888,846959060,945111425,20003916,419336070,216226312,113595187,964766818,642525591,291756152,147039258,914303810,759539501,457304600,561456689,422156772,659902622,537726509,439944526,437792409,468918100,336414753,622809363,369761224,299791403,731949674,37727766,406896931,262654525,699531783,610657511,456922572,216496387,470173802,409763779,504753339,580555824,796293298,909091973,657940637,815300275,646852987,453485355,562438375,706429510,635132037,553586981,499649183,760812141,511948790,993907029,513039162,31720885,92110671,941835283,397116491,553937218,916554452,644836050,345369871,478546407,266964991,55705259,705666698,442839157,477454241,450600498,97498485,981508374,261633959,97309351,646004005,930569505,855279913,420763648,490136004,721997180,997543168,779631621,506769646,772955503,846397660,728106337,524341112,594481902,339700826,770828149,837823022,787805746,214220488,473371241,895746100,927355474,519878977,173362357,104688499,697584375,185968856,981552276,773183236,387510340,863722737,621285833,237323356,302437097,920548969,660838797,807197643,562669569,422543464,468001520,530195388,992250337,665724116,54578338,513178221,171247934,293744771,888956411,579173543,141592637,835142620,419319168,650565558,650909420,416192789,136898561,653379891,769443194,205628385,992906817,437508295,565166813,169893621,347807126,396291528,748503128,287931377,310615140,287209355,350162057,4315306,676099505,376573383,599594107,924150639,754137626,719280422,853577354,672613114,244257288,958537399,148612508,316169148,267165275,482266210,686545141,980432356,725358733,347604857,926015159,300427234,487182149,918737053,85486157,157808383,602121197,630435844,150339838,633160256,620789750,240730013,29717803,55580523,679161941,788585661,65514307,77500997,798399024,615612655,491098680,73797450,849842816,775561800,665002514,807977643,844974377,161412416,11353469,200369247,469673910,886570237,643100335,503005008,607898327,328714110,936349601,691444028,37872862,18216137,932544081,829923261,333508237,191920692,637675248,696274267,180557278,225913591,347690554,998781460,372734637,865576740,332888483,740444824,560416809,66651664,21968021,487248816,667752393,763417404,792794552,443161549,716270904,93941602,196969246,659554150,116360042,614468673,810414085,88530163,813557138,138511124,276210057,241295347,471498993,547802684,357882085,793694988,31836043,582295502,709527794,266700105,958596321,624742631,331287367,973526783,215293422,945599102,887795039,697018383,135467700,637066917,812387920,477713927,81703211,99583804,3895313,310415048,734017600,163896570,974599336,759702994,493515955,362201400,696217027,382787019,25195250,347804990,58770255,336807315,652135305,464250,612199562,703014308,3642639,142226513,254806040,860119414,335109643,316728669,931770997,768602119,530329205,831284225,631033789,357011056,52803150,453658842,650235010,639525339,53801475,70609024,289563782,511499519,55498233,763845687,958714294,497951360,474923844,879333867,715984295,101354107,532249251,295080098,756726770,369952284,919433882,157923496,258708087,274525434,761196060,570014743,992795005,946272379,825170939,12221018,271941042,17390127,999878386,520}
};

int main(){
    int n; cin >> n;
    int m = recs[n-1].size();
    vector<vector<mint>> rec(m+1,vector<mint>(m));
    rep(i,m+1){
        if (i < m){
            ll a = 1LL;
            rec[i][i] = a;
        }
        else {
            rep(j,m){
                rec[i][j] = recs[n-1][j];
            }
        }
    }
    vector<mint> ini(m);
    rep(i,m){
        ini[i] = bm[n-1][i];
    }
    ll x; cin >> x;x--;
    cout << ax(x,rec,ini,m) << endl;
}