#1191369 (C++23(gcc16)) No.3740 Troublesome Congestion

• 問題: No.3740 Troublesome Congestion
• ユーザー: silv723
• 提出日時: 2026-10-03 23:50:43
• 言語: C++23(gcc16) (gcc 16.1.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 1,432 ms / 2,000 ms
• コード長: 16,051 bytes
• コンパイル時間: 11,641 ms
• コンパイル使用メモリ: 700,200 KB
• 実行使用メモリ: 7,852 KB
• 最終ジャッジ日時: 2026-10-03 23:51:33
• 合計ジャッジ時間: 37,464 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge4_1

サブタスク	配点	結果
部分点1	20 %	AC * 7
部分点2	30 %	AC * 12
満点	50 %	AC * 26
合計	4 * 100% = 400 点

ソースコード

#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
using boost::multiprecision::cpp_int;
using u64 = uint64_t;

namespace monotone_paths {

static constexpr u64 SM64_A = 0x9e3779b97f4a7c15ULL;
static constexpr u64 SM64_B = 0xbf58476d1ce4e5b9ULL;
static constexpr u64 SM64_C = 0x94d049bb133111ebULL;
static constexpr int DIRECT_MAX_SIDE = 60;

struct RNG {
    u64 x;
    explicit RNG(u64 seed) : x(seed) {}
    u64 next() {
        u64 z = (x += SM64_A);
        z = (z ^ (z >> 30)) * SM64_B;
        z = (z ^ (z >> 27)) * SM64_C;
        return z ^ (z >> 31);
    }
    int pick(int n) { return int(next() % u64(n)); }
};

cpp_int binom_big(int n, int r) {
    if (r < 0 || r > n) return 0;
    r = min(r, n - r);
    cpp_int x = 1;
    for (int i = 1; i <= r; ++i) x = x * (n - r + i) / i;
    return x;
}

uint64_t binom_u64(int n, int r) {
    if (r < 0 || r > n) return 0;
    r = min(r, n-r);
    uint64_t x = 1;
    for (int i = 1; i <= r; ++i) x = x * uint64_t(n-r+i) / uint64_t(i);
    return x;
}

int bit_length(const cpp_int& x) {
    if (x == 0) return 0;
    return int(boost::multiprecision::msb(x)) + 1;
}

u64 low64(const cpp_int& x) {
    static const cpp_int MASK = (cpp_int(1) << 64) - 1;
    return (x & MASK).convert_to<u64>();
}

cpp_int count_paths(const vector<string>& g) {
    int H = (int)g.size(), W = (int)g[0].size();
    vector<cpp_int> dp(W);
    for (int r = 0; r < H; ++r) for (int c = 0; c < W; ++c) {
        if (g[r][c] == '#') { dp[c] = 0; continue; }
        if (r == 0 && c == 0) { dp[c] = 1; continue; }
        cpp_int left = c ? dp[c-1] : 0;
        cpp_int up = r ? dp[c] : 0;
        dp[c] = left + up;
    }
    return dp.back();
}

// ---------- Small exact component used by the guaranteed <2^60 fallback ----------

vector<uint8_t> solve_rect_num(uint64_t target, int H, int W, int max_restarts = 500) {
    const int N = H * W;
    if (target == 0) return vector<uint8_t>(N, 0);
    vector<uint8_t> g(N, 1);
    vector<uint64_t> fw(N), bw(N);
    RNG rng(target * 123456789123ULL + 7);

    auto eval = [&]() -> uint64_t {
        fill(fw.begin(), fw.end(), 0);
        fill(bw.begin(), bw.end(), 0);
        if (!g[0] || !g[N-1]) return 0;
        fw[0] = 1;
        for (int r = 0; r < H; ++r) for (int c = 0; c < W; ++c) {
            int id = r*W+c;
            if (id == 0 || !g[id]) continue;
            fw[id] = (r ? fw[id-W] : 0) + (c ? fw[id-1] : 0);
        }
        bw[N-1] = 1;
        for (int r = H-1; r >= 0; --r) for (int c = W-1; c >= 0; --c) {
            int id = r*W+c;
            if (id == N-1 || !g[id]) continue;
            bw[id] = (r+1 < H ? bw[id+W] : 0) + (c+1 < W ? bw[id+1] : 0);
        }
        return fw[N-1];
    };

    for (int rep = 0; rep < max_restarts; ++rep) {
        fill(g.begin(), g.end(), 1);
        uint64_t cur = eval();
        for (int step = 0; step < 70 && cur > target; ++step) {
            uint64_t rem = cur - target;
            vector<pair<uint64_t,int>> cs;
            for (int id = 1; id+1 < N; ++id) if (g[id] && fw[id] && bw[id]) {
                uint64_t d = fw[id] * bw[id];
                if (d && d <= rem) cs.push_back({d,id});
            }
            if (cs.empty()) break;
            sort(cs.begin(), cs.end(), greater<>());
            int pool = min<int>(cs.size(), 1 + rep % 23), pick = 0;
            if (rep >= 8) {
                int z = int(rng.next() % 100);
                if (z < 55) pick = 0;
                else if (z < 90) pick = rng.pick(min(pool, 7));
                else pick = rng.pick(pool);
            }
            g[cs[pick].second] = 0;
            cur = eval();
        }
        if (cur == target) return g;
    }
    return {};
}

vector<string> build13(uint32_t t) {
    vector<string> out(13, string(12, '#'));
    if (t == 0) return out;
    struct R { uint64_t cap; int h,w; };
    vector<R> rs;
    for (int h = 1; h <= 13; ++h) for (int w = 1; w <= 12; ++w) {
        uint64_t cap = binom_u64(h+w-2, h-1);
        if (cap >= t) rs.push_back({cap,h,w});
    }
    sort(rs.begin(), rs.end(), [&](const R& x, const R& y){
        if (x.cap - t != y.cap - t) return x.cap - t < y.cap - t;
        return x.h*x.w < y.h*y.w;
    });
    vector<uint8_t> a;
    int H = 13, W = 12, tr = 0;
    for (auto rr : rs) {
        if (tr++ >= 12) break;
        a = solve_rect_num(t, rr.h, rr.w, 220);
        if (!a.empty()) { H = rr.h; W = rr.w; break; }
    }
    if (a.empty()) { a = solve_rect_num(t, 13, 12, 2400); H=13; W=12; }
    if (a.empty()) throw runtime_error("13x12 component search failed");
    for (int i = 0; i < H; ++i) for (int j = 0; j < W; ++j)
        if (a[i*W+j]) out[i][j] = '.';
    for (int j = W-1; j < 12; ++j) out[H-1][j] = '.';
    for (int i = H-1; i < 13; ++i) out[i][11] = '.';
    return out;
}

vector<string> transpose13(const vector<string>& g) {
    vector<string> t(12, string(13, '#'));
    for (int i = 0; i < 13; ++i) for (int j = 0; j < 12; ++j) t[j][i] = g[i][j];
    return t;
}

void put(vector<string>& G, const vector<string>& g, int r0, int c0) {
    for (int i = 0; i < (int)g.size(); ++i)
        for (int j = 0; j < (int)g[i].size(); ++j)
            if (g[i][j] == '.') G[r0+i][c0+j] = '.';
}

vector<string> construct40(const cpp_int& k) {
    const uint64_t M = (1ULL<<20) - 1;
    uint32_t a = ((k >> 40) & M).convert_to<uint32_t>();
    uint32_t b = ((k >> 20) & M).convert_to<uint32_t>();
    uint32_t c = (k & M).convert_to<uint32_t>();
    auto ga = build13(a), gb = build13(b), gc = build13(c), gq = build13(1u<<20);
    vector<string> G(40, string(40, '#'));
    for (int r = 0; r <= 27; ++r) G[r][0] = '.';
    G[0][1] = G[13][1] = G[27][1] = '.';
    put(G, transpose13(ga), 0, 2);
    put(G, transpose13(gq), 11, 15);
    put(G, gb, 13, 2);
    put(G, transpose13(gq), 25, 27);
    put(G, gc, 27, 2);
    for (int r = 23; r <= 25; ++r) G[r][27] = '.';
    for (int cc = 13; cc <= 27; ++cc) G[25][cc] = '.';
    for (int r = 37; r <= 39; ++r) G[r][39] = '.';
    for (int cc = 13; cc <= 39; ++cc) G[39][cc] = '.';
    return G;
}

// ---------- Direct BigInt wall search ----------

cpp_int eval_big_grid(const vector<uint8_t>& g, int H, int W,
                      vector<cpp_int>& fw, vector<cpp_int>& bw) {
    int N = H*W;
    fill(fw.begin(), fw.end(), 0);
    fill(bw.begin(), bw.end(), 0);
    if (!g[0] || !g[N-1]) return 0;
    fw[0] = 1;
    for (int r=0;r<H;++r) for (int c=0;c<W;++c) {
        int id=r*W+c;
        if (id==0 || !g[id]) continue;
        fw[id]=(r?fw[id-W]:0)+(c?fw[id-1]:0);
    }
    bw[N-1]=1;
    for (int r=H-1;r>=0;--r) for (int c=W-1;c>=0;--c) {
        int id=r*W+c;
        if (id==N-1 || !g[id]) continue;
        bw[id]=(r+1<H?bw[id+W]:0)+(c+1<W?bw[id+1]:0);
    }
    return fw[N-1];
}

using Clock = chrono::steady_clock;

optional<vector<string>> solve_rect_big(const cpp_int& target, int H, int W,
                                         Clock::time_point deadline, u64 seed) {
    int N=H*W;
    vector<cpp_int> fw(N),bw(N);
    RNG rng(seed);
    int reps=0;
    while (Clock::now() < deadline) {
        ++reps;
        vector<uint8_t> g(N,1);
        cpp_int cur=eval_big_grid(g,H,W,fw,bw);
        if(cur==target){
            vector<string> G(H,string(W,'#'));
            for(int r=0;r<H;++r)for(int c=0;c<W;++c)if(g[r*W+c])G[r][c]='.';
            return G;
        }
        for(int step=0;step<180&&cur>target;++step){
            cpp_int rem=cur-target;
            vector<pair<cpp_int,int>> top;
            top.reserve(16);
            for(int id=1;id+1<N;++id){
                if(!g[id]||fw[id]==0||bw[id]==0)continue;
                cpp_int d=fw[id]*bw[id];
                if(d<=0||d>rem)continue;
                if(d==rem){top={{d,id}};break;}
                auto it=top.begin();
                while(it!=top.end()&&it->first>=d)++it;
                top.insert(it,{d,id});
                if(top.size()>16)top.pop_back();
            }
            if(top.empty())break;
            int pick=0;
            if(top[0].first!=rem&&reps>2){
                int z=int(rng.next()%100);
                if(z>=58){
                    int lim=min<int>(top.size(),1+(reps%(int)top.size()));
                    pick=rng.pick(lim);
                }
            }
            g[top[pick].second]=0;
            cur=eval_big_grid(g,H,W,fw,bw);
            if(cur==target){
                vector<string> G(H,string(W,'#'));
                for(int r=0;r<H;++r)for(int c=0;c<W;++c)if(g[r*W+c])G[r][c]='.';
                return G;
            }
            if(Clock::now()>=deadline)break;
        }
    }
    return nullopt;
}

int min_square_side(const cpp_int& k){
    if(k<=1)return 1;
    int bits=bit_length(k);
    int D=max(2,int(ceil((bits+0.5*log2(max(2,bits))+1)/2.0))+1);
    if(bits>12000)return D;
    while(D>1&&binom_big(2*(D-2),D-2)>=k)--D;
    while(binom_big(2*(D-1),D-1)<k)++D;
    return D;
}

vector<pair<int,int>> direct_candidates(const cpp_int& k,int D){
    struct X{int H,W,area;cpp_int cap;};
    vector<X>a;
    for(int h=1;h<=D;++h){
        cpp_int cap=binom_big(h+D-2,h-1);
        if(cap>=k)a.push_back({h,D,h*D,cap});
    }
    sort(a.begin(),a.end(),[](const X&x,const X&y){
        if(x.area!=y.area)return x.area<y.area;
        return x.cap<y.cap;
    });
    vector<pair<int,int>> out;
    for(int i=0;i<(int)a.size()&&i<4;++i)out.push_back({a[i].H,a[i].W});
    return out;
}

optional<vector<string>> search_direct(const cpp_int& k,int minD,int maxD,int budget_ms){
    auto start=Clock::now(), deadline=start+chrono::milliseconds(budget_ms);
    for(int D=minD;D<=maxD&&Clock::now()<deadline;++D){
        auto cs=direct_candidates(k,D);
        for(int q=0;q<(int)cs.size()&&Clock::now()<deadline;++q){
            auto now=Clock::now();
            auto remain=chrono::duration_cast<chrono::milliseconds>(deadline-now).count();
            long long slice=min<long long>((D==minD&&q==0)?450:170,remain);
            if(slice<8)break;
            auto [H,W]=cs[q];
            auto local_deadline=now+chrono::milliseconds(slice);
            u64 seed=low64(k) ^ (u64(H)<<32) ^ (u64(W)*SM64_A);
            auto z=solve_rect_big(k,H,W,local_deadline,seed);
            if(z)return z;
        }
    }
    return nullopt;
}

// ---------- Deterministic arbitrary-precision Horner fallback ----------

struct Plan{
    int a,b,B,u,h,H,W,max_side;
    cpp_int Q;
};

int digits_count_base(cpp_int x,int B){int u=0;do{x/=B;++u;}while(x>0);return u;}
int exact_h(cpp_int x,const cpp_int&Q){int h=0;do{x/=Q;++h;}while(x>0);return h;}

Plan plan_asym(const cpp_int& k){
    static const int BASES[]={2,3,4,5,6,7,8,10,12,16,20,24,32,40,48,64,80,96,128};
    int n=bit_length(k),maxAB=min(300,max(30,int(ceil(4*sqrt((double)n)))));
    vector<double> lf(2*maxAB+1);
    for(int i=1;i<(int)lf.size();++i)lf[i]=lf[i-1]+log2((double)i);
    struct A{int a,b,B,mx,sum,area;};
    vector<A> approx;
    for(int a=3;a<=maxAB;++a)for(int b=1;b<=maxAB;++b){
        double L=lf[a+b]-lf[a]-lf[b];
        if(L<1)continue;
        for(int B:BASES){
            int u=int(ceil(L/log2((double)B)-1e-12));
            if(3*u>a)continue;
            int h=max(1,int(ceil(n/L)));
            int wd=(B+1)*u+3,H=h*(a+2),W=wd+5+(h-1)*(b+2);
            approx.push_back({a,b,B,max(H,W),H+W,H*W});
        }
    }
    sort(approx.begin(),approx.end(),[](const A&x,const A&y){
        if(x.mx!=y.mx)return x.mx<y.mx;
        if(x.sum!=y.sum)return x.sum<y.sum;
        return x.area<y.area;
    });
    bool have=false; Plan best{}; int bestSum=0,bestArea=0;
    set<tuple<int,int,int>> seen;
    for(int ii=0;ii<(int)approx.size()&&ii<100;++ii){
        auto z=approx[ii];
        if(!seen.insert({z.a,z.b,z.B}).second)continue;
        cpp_int Q=binom_big(z.a+z.b,z.a);
        int u=digits_count_base(Q-1,z.B);
        if(3*u>z.a)continue;
        int h=exact_h(k,Q),wd=(z.B+1)*u+3,H=h*(z.a+2),W=wd+5+(h-1)*(z.b+2);
        int mx=max(H,W),sum=H+W,area=H*W;
        if(!have||tie(mx,sum,area)<tie(best.max_side,bestSum,bestArea)){
            have=true;best={z.a,z.b,z.B,u,h,H,W,mx,Q};bestSum=sum;bestArea=area;
        }
    }
    if(!have)throw runtime_error("large-number parameter search failed");
    return best;
}

vector<int> to_base_digits(cpp_int x,int B){
    vector<int>a;do{cpp_int q=x/B;cpp_int r=x-q*B;a.push_back(r.convert_to<int>());x=q;}while(x>0);
    reverse(a.begin(),a.end());return a;
}

pair<int,int> put_digit_component(vector<string>&G,const cpp_int&d,int B,int R,int compC,int SEP){
    auto digs=to_base_digits(d,B);int u=digs.size(),P=B+1,A0=B+3,H=3*u;
    G[R][1]='.';for(int rr=0;rr<H;++rr)G[R+rr][compC]='.';
    int e0=digs[0];G[R][compC+1]='.';
    for(int c=2;c<2+e0;++c)G[R][compC+c]=G[R+1][compC+c]='.';
    int outc=compC+1+e0;for(int c=outc;c<=compC+P;++c)G[R+1][c]='.';
    G[R+2][compC+P]='.';for(int c=compC+P;c<=compC+A0;++c)G[R+2][c]='.';
    int ra=R+2,ca=compC+A0;
    for(int z=1;z<(int)digs.size();++z){
        int e=digs[z];
        for(int rr=ra;rr<=ra+1;++rr)for(int c=ca;c<ca+B;++c)G[rr][c]='.';
        G[ra+1][ca+B]=G[ra+1][ca+B+1]=G[ra+2][ca+B+1]='.';
        int nr=ra+3,nc=ca+B+1;G[nr][nc]='.';
        if(e>0){
            G[ra+1][compC+1]='.';
            for(int c=2;c<2+e;++c)G[ra+1][compC+c]=G[ra+2][compC+c]='.';
            int ec=compC+1+e;for(int c=ec;c<=compC+P;++c)G[ra+2][c]='.';
            G[ra+3][compC+P]='.';for(int c=compC+P;c<nc;++c)G[ra+3][c]='.';
        }
        ra=nr;ca=nc;
    }
    for(int c=ca;c<=SEP;++c)G[ra][c]='.';
    return {ra,SEP};
}

vector<string> construct_asym(const cpp_int& k,const Plan&p){
    int a=p.a,b=p.b,B=p.B,u=p.u,h=p.h,H=p.H,W=p.W;cpp_int Q=p.Q;
    vector<cpp_int>digs;cpp_int x=k;do{cpp_int q=x/Q;digs.push_back(x-q*Q);x=q;}while(x>0);reverse(digs.begin(),digs.end());
    int wd=(B+1)*u+3,compC=2,compLast=compC+wd-1,SEP=compLast+1,C0=SEP+2;
    vector<string>G(H,string(W,'#'));for(int r=0;r<H;++r)G[r][0]='.';
    auto pp=put_digit_component(G,digs[0],B,0,compC,SEP);int r0=a+1;
    for(int r=pp.first;r<=r0;++r)G[r][SEP]='.';for(int c=SEP;c<=C0;++c)G[r0][c]='.';
    int r=r0,c=C0;
    for(int j=1;j<(int)digs.size();++j){
        for(int rr=r;rr<=r+a;++rr)for(int cc=c;cc<=c+b;++cc)G[rr][cc]='.';
        G[r+a][c+b+1]=G[r+a][c+b+2]=G[r+a+1][c+b+2]='.';
        int nr=r+a+2,nc=c+b+2;G[nr][nc]='.';
        if(digs[j]>0){
            auto q=put_digit_component(G,digs[j],B,r+1,compC,SEP);
            for(int rr=q.first;rr<=nr;++rr)G[rr][SEP]='.';
            for(int cc=SEP;cc<nc;++cc)G[nr][cc]='.';
        }
        r=nr;c=nc;
    }
    return G;
}

// Main API.  budget_ms controls only the heuristic direct search.
vector<string> construct(const cpp_int& k,int budget_ms=1000){
    if(k<0)throw invalid_argument("k must be nonnegative");
    if(k==0)return {"#"};
    if(k==1)return {"."};
    static const cpp_int LIMIT60=cpp_int(1)<<60;
    int lower=min_square_side(k);
    optional<Plan> safePlan;
    int safeMax;
    if(k<LIMIT60)safeMax=40;
    else{safePlan=plan_asym(k);safeMax=safePlan->max_side;}
    if(lower<=DIRECT_MAX_SIDE&&lower<safeMax&&budget_ms>0){
        auto z=search_direct(k,lower,min(DIRECT_MAX_SIDE,safeMax-1),budget_ms);
        if(z)return *z;
    }
    return k<LIMIT60?construct40(k):construct_asym(k,*safePlan);
}

} // namespace monotone_paths

int T;

void solve(){
    using namespace monotone_paths;
    string s; cin>>s; cpp_int k(s);
    auto g=construct(k,1500 / T);
    
    int H = g.size();
    int W = g[0].size();
    int m = max(2, max(H, W));
    for(auto& row : g) row.resize(m, '#');
    g.resize(m, string(m, '#'));
    for(int r = H - 1; r < m; ++r) {
        g[r][W - 1] = '.';
    }
    for(int c = W - 1; c < m; ++c) {
        g[m - 1][c] = '.';
    }
    if(g[m-1][m-2] == '.') g[m-1][m-2] = 'P';
    if(g[m-2][m-1] == '.') g[m-2][m-1] = 'P';
    cout << m << '\n';
    for(auto& row : g) cout << row << '\n';
}
int main(){
    std::cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int t;
    cin >> t;
    T = t;
    while(t--) solve();
}