結果

問題 No.1891 Static Xor Range Composite Query
ユーザー tails
提出日時 2022-04-04 19:46:11
言語 cLay
(20241019-1)
結果
AC  
実行時間 247 ms / 5,000 ms
コード長 507 bytes
コンパイル時間 4,033 ms
コンパイル使用メモリ 177,476 KB
実行使用メモリ 44,544 KB
最終ジャッジ日時 2024-11-25 12:27:44
合計ジャッジ時間 13,248 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#define MD 998244353
struct AB {
    Mint a,b;
};
inline
AB operator*(AB x,AB y){
    return {y.a*x.a,y.a*x.b+y.b};
}
AB ab[19][262144];
{
    ll@n,@q;
    rep(i,n){
        rd(ab[0][i].a,ab[0][i].b);
    }
    rep(d,1,19){
        ll m=1<<d-1;
        rep(i,262144){
            ab[d][i]=ab[d-1][i]*ab[d-1][i^m];
        }
    }
    rep(q){
        ll@l,@r,@p,@x;
        AB u{1,0};
        AB v{1,0};
        ll d=0;
        while(l<r){
            ll m=1<<d;
            if(l&m){
                u=u*ab[d][l^p];
                l+=m;
            }
            if(r&m){
                r-=m;
                v=ab[d][r^p]*v;
            }
            ++d;
        }
        u=u*v;
        wt(u.a*x+u.b);
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0