結果
| 問題 | No.2206 Popcount Sum 2 |
| コンテスト | |
| ユーザー |
 vjudge1
|
| 提出日時 | 2025-08-01 21:18:37 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 878 ms / 4,000 ms |
| コード長 | 5,310 bytes |
| 記録 | |
| コンパイル時間 | 2,253 ms |
| コンパイル使用メモリ | 202,192 KB |
| 実行使用メモリ | 16,700 KB |
| 最終ジャッジ日時 | 2025-08-01 21:18:50 |
| 合計ジャッジ時間 | 12,238 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 18 |
コンパイルメッセージ
main.cpp: In member function ‘FastIO::Ot& FastIO::Ot::operator<<(long double)’:
main.cpp:32:69: warning: field precision specifier ‘.*’ expects argument of type ‘int’, but argument 4 has type ‘long long int’ [-Wformat=]
32 | Wt(long double){snprintf(buf,sizeof(buf),"%.*Lf",dt,x);return(*this)<<buf;}Wt(Ot&){return x;}
| ~~^~~ ~~
| | |
| int long long int
ソースコード
#include <bits/stdc++.h>
#define int long long
#define gcd(x, y) __gcd(x,y)
#define IOS cin.tie(0),cout.tie(0)->sync_with_stdio(0)
#define qwq 0
#define ldb long double
using namespace std;
namespace FastIO{
// #define _gc() (St==Ed&&(Ed=(St=in)+fread(in,1,N,stdin),St==Ed)?EOF:*St++)
#define _gc() getchar()
#define _fl() (fwrite(ot,1,now-ot,stdout))
#define _pc(x) (now==ot+N&&(_fl(),now=ot),*now++=(x))
const int N=1<<20;char in[N],*St=in,*Ed=in,ot[N],*now=ot;
class __f{public:~__f(){_fl();}} _f;
#define TYPES template<typename T>
class In{
public:
#define Ipt(typ) inline In&operator>>(typ x)
TYPES Ipt(T&){bool f=0;x=0;char c=_gc();while(c<48||c>57)f|=(c=='-'),c=_gc();while(c>=48&&c<=57)x=x*10+(c^48),c=_gc();if(c=='.'){__float128 dot=1;for(c=_gc();c>=48&&c<=57;c=_gc())x+=(c^48)*(dot*=0.1);}return x=(f?-x:x),*this;}
Ipt(char&){while(isspace(x=_gc()));return*this;}
#define Instr(add) char c=_gc();for(;isspace(c);c=_gc());while(!isspace(c)&&~c)add,c=_gc();
#define Gline(add) char c=_gc();for(;!(c==' '||!isspace(c));c=_gc());while(c==' '||!isspace(c))add,c=_gc();
inline In&getline(char*x){Gline((*x++)=c);return*x=0,*this;}inline In&getline(string&x){x.clear();Gline(x.push_back(c));return*this;}
Ipt(char*){Instr((*x++)=c);return*x=0,*this;}Ipt(string&){x.clear();Instr(x.push_back(c));return*this;}Ipt(In&){return x;}
}fin;
TYPES inline In&getline(T&x,In&in=fin){return fin.getline(x),in;}
class Ot{
char buf[80];int dt=6,tp=0;public:
#define Wt(typ) inline Ot&operator<<(typ x)
TYPES Wt(T){if(x<0)_pc('-'),x=-x;do buf[++tp]=x%10,x/=10;while(x);while(tp)_pc(buf[tp--]^48);return*this;}Wt(char){return _pc(x),*this;}
Wt(const char*){while(*x)_pc(*(x++));return*this;}Wt(char*){return(*this)<<(const char*)x;}Wt(string){return(*this)<<x.c_str();}
Wt(long double){snprintf(buf,sizeof(buf),"%.*Lf",dt,x);return(*this)<<buf;}Wt(Ot&){return x;}
#define OD(typ) Wt(typ){return (*this)<<(long double)x;}
OD(double)OD(__float128)inline Ot&setdot(const int n){return dt=n,*this;}
}fout;
inline Ot&setdot(const int n,Ot&ot=fout){return ot.setdot(n),ot;}
} using FastIO::fin, FastIO::fout;
#define cin fin
#define cout fout
bool Mbg;
const int P(20170408);
template<int P>
struct modint {
private:
template<typename T>
inline static const T Down(const T&x) {return x >= P ? x - P : x;}
public:
unsigned int v;
modint(unsigned int v=0) : v(v%P) {}
using mint = modint;
#define FI friend inline
FI ostream&operator<<(ostream&o, mint v) {return o<<v.v;}
FI istream&operator>>(istream&i, mint&v) {int x;return i>>x,v.v=Down(x%P+P),i;}
#ifdef FASTIO
FI FastIO::In&operator>>(FastIO::In&i, mint&v) {int x; return i>>x,v.v=Down(x%P+P),i;}
FI FastIO::Ot&operator<<(FastIO::Ot&o, mint v) {return o<<v.v;}
#endif
FI mint operator+(mint a, mint b) {return Down(a.v + b.v);}
FI mint operator-(mint a, mint b) {return Down(a.v - b.v + P);}
FI mint operator*(mint a, mint b) {return 1ull * a.v * b.v % P;}
FI mint operator/(mint a, mint b) {return a * ~b;}
FI mint operator^(mint a, int p) {mint r=1; for(; p; p >>= 1, a = a * a) if (p & 1) r = r * a; return r;}
FI mint operator~(mint a) {return a ^ (P - 2);}
FI mint operator-(mint a) {return a.v ? P - a.v : 0;}
FI mint&operator+=(mint&a, mint b) {return a=a+b;}
FI mint&operator-=(mint&a, mint b) {return a=a-b;}
FI mint&operator*=(mint&a, mint b) {return a=a*b;}
FI mint&operator/=(mint&a, mint b) {return a=a/b;}
FI mint&operator^=(mint&a, int b) {return a=a^b;}
FI mint&operator++(mint&a) {return a += 1;}
FI mint&operator--(mint&a) {return a -= 1;}
FI mint operator++(mint&a, signed) {mint x=a; return ++a, x;}
FI mint operator--(mint&a, signed) {mint x=a; return --a, x;}
FI bool operator==(mint a, mint b) {return a.v==b.v;}
FI bool operator!=(mint a, mint b) {return a.v!=b.v;}
};
typedef modint<998244353> mint;
const int N(2e5 + 5), sq(455);
int q;
struct Node {
int n, m, id;
bool operator<(Node x) {
if (m / sq == x.m / sq) return n < x.n;
return m < x.m;
}
} Q[N];
mint fac[N], ifac[N], p2[N], ans[N], res=1;
void init(int x) {
fac[0] = p2[0] = 1;
for (int i = 1; i <= x; i++) fac[i] = fac[i - 1] * i;
ifac[x] = 1 / fac[x];
for (int i = x; i; i--) ifac[i - 1] = ifac[i] * i;
for (int i = 1; i <= x; i++) p2[i] = p2[i - 1] * 2;
}
mint C(int x, int y) {return fac[x] * ifac[y] * ifac[x - y];}
void work() {
cin >> q;
for (int i = 1; i <= q; i++) cin >> Q[i].n >> Q[i].m, Q[i].n--, Q[i].m--, Q[i].id = i;
sort(Q + 1, Q + q + 1);
int m = 0, n = 0;
for (int i = 1; i <= q; i++) {
while (n < Q[i].n) {
res *= 2;
n++;
res -= C(n - 1, m);
// cout << res.v << ' ';
}
// cout << '\n';
while (m < Q[i].m) {
res += C(n, m + 1);
// cout << res.v << ' ';
m++;
}
// cout << '\n';
while (m > Q[i].m) {
res -= C(n, m);
// cout << res.v << ' ';
m--;
}
// cout << '\n';
while (n > Q[i].n) {
res += C(n - 1, m);
res *= ifac[2];
// cout << res.v << ' ';
n--;
}
// cout << '\n';
ans[Q[i].id] = res * (p2[n + 1] - 1);
}
for (int i = 1; i <= q; i++) cout << ans[i].v << "\n";
}
bool Med;
signed main() {
// freopen("P8131_2.in", "r", stdin);
// IOS;
init(N-5);
int T(1);
// cin >> T;
clock_t st = clock();
while (T--) work();
cerr << (clock()-st)/1.0/CLOCKS_PER_SEC << " s\n";
cerr << (&Mbg-&Med)/1024.0/1024.0 << " MB\n";
return qwq;
}