#1110036 (C++23) No.2206 Popcount Sum 2

• 問題: No.2206 Popcount Sum 2
• ユーザー: vjudge1
• 提出日時: 2025-08-02 15:25:31
• 言語: C++23 (gcc 13.3.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 643 ms / 4,000 ms
• コード長: 14,092 bytes
• コンパイル時間: 3,314 ms
• コンパイル使用メモリ: 283,440 KB
• 実行使用メモリ: 23,256 KB
• 最終ジャッジ日時: 2025-08-02 15:25:47
• 合計ジャッジ時間: 14,504 ms
• ジャッジサーバーID （参考情報）: judge5 / judge1

ファイルパターン	結果
sample	AC * 1
other	AC * 18

ソースコード

#include <bits/stdc++.h>
using namespace std;
namespace fast_io
{
    template <size_t... Ints>
    struct index_sequence
    {
        using type = index_sequence;
        using value_type = size_t;
        static std::size_t size() { return sizeof...(Ints); }
    };
    template <class Sequence1, class Sequence2>
    struct merge_and_renumber;
    template <size_t... I1, size_t... I2>
    struct merge_and_renumber<index_sequence<I1...>, index_sequence<I2...>> : index_sequence<I1..., (sizeof...(I1) + I2)...>
    {
    };
    template <size_t N>
    struct make_index_sequence : merge_and_renumber<typename make_index_sequence<N / 2>::type, typename make_index_sequence<N - N / 2>::type>
    {
    };
    template <>
    struct make_index_sequence<0> : index_sequence<>
    {
    };
    template <>
    struct make_index_sequence<1> : index_sequence<0>
    {
    };
    template <typename Func, typename Tuple, std::size_t... index>
    auto apply_helper(Func &&func, Tuple &&tuple, index_sequence<index...>) -> decltype(func(std::get<index>(std::forward<Tuple>(tuple))...)) { return func(std::get<index>(std::forward<Tuple>(tuple))...); }
    template <typename Func, typename Tuple>
    auto apply(Func &&func, Tuple &&tuple) -> decltype(apply_helper(std::forward<Func>(func), std::forward<Tuple>(tuple), make_index_sequence<std::tuple_size<typename std::decay<Tuple>::type>::value>{})) { return apply_helper(std::forward<Func>(func), std::forward<Tuple>(tuple), make_index_sequence<std::tuple_size<typename std::decay<Tuple>::type>::value>{}); }
    namespace type_traits
    {
        template <class Tp>
        constexpr bool is_char_v = std::is_same<Tp, char>::value || std::is_same<Tp, signed char>::value || std::is_same<Tp, unsigned char>::value;
        template <class Tp>
        constexpr bool is_int_v = (std::is_integral<Tp>::value && std::is_signed<Tp>::value && !is_char_v<Tp>) || std::is_same<Tp, __int128_t>::value;
        template <class Tp>
        constexpr bool is_uint_v = (std::is_integral<Tp>::value && std::is_unsigned<Tp>::value && !is_char_v<Tp>) || std::is_same<Tp, __uint128_t>::value;
        template <class Tp>
        using make_uint_t = typename std::conditional_t<(std::is_same<Tp, __int128_t>::value || std::is_same<Tp, __uint128_t>::value), std::common_type<__uint128_t>, typename std::conditional_t<std::is_signed<Tp>::value, std::make_unsigned<Tp>, std::common_type<Tp>>>::type;
    }
    template <size_t BUFFER_SIZE>
    class FastIn
    {
        using self = FastIn<BUFFER_SIZE>;

    protected:
        char buffer_[BUFFER_SIZE], *now_ = buffer_, *end_ = buffer_;
        FILE *file_;

    public:
        explicit FastIn(FILE *file = stdin) : file_(file) {}
        char fetch() { return now_ == end_ && (end_ = (now_ = buffer_) + fread(buffer_, 1, BUFFER_SIZE, file_), now_ == end_) ? EOF : *(now_)++; }
        char visit() { return now_ == end_ && (end_ = (now_ = buffer_) + fread(buffer_, 1, BUFFER_SIZE, file_), now_ == end_) ? EOF : *(now_); }
        void set_file(FILE *file)
        {
            file_ = file;
            now_ = end_ = buffer_;
        }
        bool iseof() { return visit() == EOF; }
        template <class Tp, std::enable_if_t<type_traits::is_int_v<Tp>> * = nullptr>
        self &read(Tp &n)
        {
            bool is_neg = false;
            char ch = fetch();
            while (!isdigit(ch))
            {
                is_neg |= ch == '-';
                ch = fetch();
            }
            n = 0;
            while (isdigit(ch))
            {
                (n *= 10) += ch & 0x0f;
                ch = fetch();
            }
            if (is_neg)
                n = -n;
            return *this;
        }
        template <class Tp, std::enable_if_t<type_traits::is_uint_v<Tp>> * = nullptr>
        self &read(Tp &n)
        {
            char ch = fetch();
            while (!isdigit(ch))
                ch = fetch();
            n = 0;
            while (isdigit(ch))
            {
                (n *= 10) += ch & 0x0f;
                ch = fetch();
            }
            return *this;
        }
        template <class Tp, std::enable_if_t<type_traits::is_char_v<Tp>> * = nullptr>
        self &read(Tp &n)
        {
            while (!isgraph(n = fetch()))
                ;
            return *this;
        }
        self &read(char *n)
        {
            char *n_ = n;
            while (!isgraph(*n_ = fetch()))
                ;
            while (isgraph(*(++n_) = fetch()))
                ;
            *n_ = '\0';
            return *this;
        }
        self &read(std::string &n)
        {
            n.clear();
            char n_;
            while (!isgraph(n_ = fetch()))
                ;
            n.push_back(n_);
            while (isgraph(n_ = fetch()))
                n.push_back(n_);
            return *this;
        }
        template <class Tp, class Up>
        self &read(std::pair<Tp, Up> &p) { return read(p.first).read(p.second); }
        template <typename... Ts>
        self &read(std::tuple<Ts...> &p)
        {
            apply([&](Ts &...targs)
                                                                                                             { ((read(targs)), ...); }, p);
            return *this;
        }
        self &getline(char *n)
        {
            char *n_ = n;
            while (!isprint(*n_ = fetch()))
                ;
            while (isprint(*(++n_) = fetch()))
                ;
            *n_ = '\0';
            return *this;
        }
        self &getline(std::string &n)
        {
            char n_;
            while (!isprint(n_ = fetch()))
                ;
            n.push_back(n_);
            while (isprint(n_ = fetch()))
                n.push_back(n_);
            return *this;
        }
        template <class Tp, std::enable_if_t<type_traits::is_char_v<Tp>> * = nullptr>
        self &strict_read(Tp &n)
        {
            n = fetch();
            return *this;
        }
        template <class Tp>
        self &operator>>(Tp &val) { return read(val); }
    };
    template <size_t BUFFER_SIZE, size_t INT_BUFFER_SIZE>
    class FastOut
    {
        using self = FastOut<BUFFER_SIZE, INT_BUFFER_SIZE>;

    private:
        char int_buffer_[INT_BUFFER_SIZE], *now_ib_ = int_buffer_;

    protected:
        FILE *file_;
        char *now_, buffer_[BUFFER_SIZE];
        const char *const end_ = buffer_ + BUFFER_SIZE;

    public:
        explicit FastOut(FILE *file = stdout) : file_(file), now_(buffer_) {}
        self &operator=(const self &rhs)
        {
            file_ = rhs.file_;
            now_ = buffer_ + (rhs.now_ - rhs.buffer_);
            memcpy(buffer_, rhs.buffer_, sizeof(*buffer_) * (rhs.now_ - rhs.buffer_));
            return *this;
        }
        FastOut(const self &rhs) { *this = rhs; }
        ~FastOut() { flush(); }
        void flush()
        {
            fwrite(buffer_, 1, now_ - buffer_, file_);
            now_ = buffer_;
        }
        void rebind(FILE *file) { file_ = file; }
        template <class Tp, std::enable_if_t<type_traits::is_char_v<Tp>> * = nullptr>
        self &write(const Tp &n)
        {
            if (now_ == end_)
                flush();
            *(now_++) = n;
            return *this;
        }
        self &write(const char *n)
        {
            size_t len = strlen(n), l_;
            const char *n_ = n;
            while (now_ + len >= end_)
            {
                l_ = end_ - now_;
                memcpy(now_, n_, l_);
                now_ += l_;
                n_ += l_;
                len -= l_;
                flush();
            }
            memcpy(now_, n_, len);
            now_ += len;
            return *this;
        }
        template <class Tp, std::enable_if_t<type_traits::is_int_v<Tp>> * = nullptr>
        self &write(Tp n)
        {
            if (n < 0)
            {
                write('-');
                n = -n;
            }
            return write(static_cast<typename type_traits::make_uint_t<Tp>>(n));
        }
        template <class Tp, std::enable_if_t<type_traits::is_uint_v<Tp>> * = nullptr>
        self &write(Tp n)
        {
            now_ib_ = int_buffer_ + INT_BUFFER_SIZE - 1;
            do
            {
                *(--(now_ib_)) = char(n % 10) | '0';
            } while (n /= 10);
            return write(now_ib_);
        }
        self &write(const std::string &str) { return write(str.c_str()); }
        template <class Tp, class Up>
        self &write(const std::pair<Tp, Up> &p) { return write(p.first).space().write(p.second); }
        template <typename... Ts>
        self &write(const std::tuple<Ts...> &p)
        {
            apply([&](Ts const &...targs)
                                                                                                             {std::size_t n{0};((write(targs).space_if(++n!=sizeof...(Ts))),...); }, p);
            return *this;
        }
        self &linebreak() { return write('\n'); }
        self &linebreak_if(bool flag) { return flag ? linebreak() : *this; }
        self &space() { return write(' '); }
        self &space_if(bool flag) { return flag ? space() : *this; }
        template <class Tp>
        self &operator<<(const Tp &val) { return write(val); }
    };
    const std::size_t BUFFER_SIZE = (1 << 21) + 5;
    FastIn<BUFFER_SIZE> fin;
    FastOut<BUFFER_SIZE, 21> fout;
};
namespace __LYC__
{
    template <typename T>
    T lowbit(const T x) { return x & (-x); }
    int exgcd(int a, int b, int &x, int &y)
    {
        if (b == 0)
        {
            x = 1, y = 0;
            return a;
        }
        int tmp = exgcd(b, a % b, x, y);
        int tmpx = x;
        x = y;
        y = tmpx - y * (a / b);
        return tmp;
    }
    int finv(int a, int m)
    {
        int x, y;
        if (exgcd(a, m, x, y) != 1)
            return 0;
        x %= m;
        if (x < 0)
            x += m;
        return x;
    }
    template <typename T>
    class __value_add_value
    {
    public:
        constexpr T operator()(const T &lhs, const T &rhs) const { return lhs + rhs; }
    };
    template <typename T>
    class maxval
    {
    public:
        constexpr T operator()(const T &lhs, const T &rhs) const { return max(lhs, rhs); }
    };
    template <typename T>
    class minval
    {
    public:
        constexpr T operator()(const T &lhs, const T &rhs) const { return min(lhs, rhs); }
    };
    template <class T = int, class cmp = __value_add_value<T>>
    class BIT
    {
    public:
        int n = 0;
        T *c;
        BIT(int _n = 0)
        {
            c = new T[_n + 1];
            n = _n;
            for (int i = 0; i <= n; i++)
                c[i] = T();
        }
        void update(int x, T k)
        {
            if (x <= 0)
                return;
            while (x <= n)
            {
                c[x] = cmp{}(c[x], k);
                x += lowbit(x);
            }
        }
        void init(int _n = -1, T val = T(), T *a = NULL)
        {
            if (_n != n)
            {
                delete[] c;
                c = new T[_n + 1];
                n = _n;
            }
            for (int i = 0; i <= n; i++)
                c[i] = T();
            if (a == NULL)
                for (int i = 1; i <= n; i++)
                    update(i, val);
            else
                for (int i = 1; i <= n; i++)
                    update(i, a[i]);
        }
        void clear(T val = T(), T *a = NULL)
        {
            for (int i = 0; i <= n; i++)
                c[i] = T();
            if (a == NULL)
                for (int i = 1; i <= n; i++)
                    update(i, val);
            else
                for (int i = 1; i <= n; i++)
                    update(i, a[i]);
        }
        T query(int x)
        {
            T res = T();
            while (x)
            {
                res = cmp{}(res, c[x]);
                x -= lowbit(x);
            }
            return res;
        }
    };
};
using __LYC__::finv, __LYC__::exgcd, __LYC__::BIT, __LYC__::maxval, __LYC__::minval, __LYC__::lowbit;
#define rep(l, r, k) for (auto i = (l); i <= (r); i += (k))
//#define int long long
/*
#define cin fast_io::fin
#define cout fast_io::fout
*/
const int N = 1e6, INF = 1e9,P=998244353;
int a[N + 5],b[N+5],fac[N+5],inv[N+5];
long long fpow(long long p,int q){
    long long res=1;
    while(q){
        if(q&1) res=res*p%P;
        p=p*p%P;
        q>>=1;
    }
    return res;
}
int C(int x,int y){
    if(y<0||x<y) return 0;
    return (long long)fac[x]*inv[y]%P*inv[x-y]%P;
}
int q,ans[N+5],s;
struct quesion{
    int n,m,id;
    friend bool operator<(quesion x,quesion y){
        int idx=(x.n+s-1)/s,idy=(y.n+s-1)/s;
        if(idx==idy){
            if(idx&1) return x.m<y.m;
            else return x.m>y.m;
        }
        return idx<idy;
    }
} ques[N+5];
void solve()
{
    cin>>q;
    s=sqrt(q);
    for(int i=1;i<=q;i++){
        cin>>ques[i].n>>ques[i].m;
        ques[i].n--;
        ques[i].m--;
        ques[i].id=i;
    }
    sort(ques+1,ques+q+1);
    int n=0,m=0,res=1;
    for(int i=1;i<=q;i++){
        while(m<ques[i].m){
            m++;
            res+=C(n,m);
            if(res>=P) res-=P;
        }
        while(ques[i].n<n){
            n--;
            res=(long long)(res+C(n,m))*inv[2]%P;
        }
        while(n<ques[i].n){
            res=(res<<1)-C(n,m);
            if(res<0) res+=P;
            if(res>=P) res-=P;
            n++;
        }
        while(ques[i].m<m){
            res-=C(n,m);
            if(res<0) res+=P;
            m--;
        }
        ans[ques[i].id]=res*(fpow(2,ques[i].n+1)-1ll)%P;
    }
    for(int i=1;i<=q;i++) cout<<ans[i]<<"\n";
}
signed main()
{
    fac[0]=fac[1]=inv[0]=inv[1]=1;
    for(int i=2;i<=N;i++){
        fac[i]=(long long)fac[i-1]*i%P;
        inv[i]=(long long)(P-P/i)*inv[P%i]%P;
    }
    for(int i=3;i<=N;i++) inv[i]=(long long)inv[i-1]*inv[i]%P;
    
    int Tcases = 1;
    //cin >> Tcases;
    while (Tcases--)
        solve();
    return 0;
}