QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #766736 | #1085. Brave Seekers of Unicorns | pan_g | AC ✓ | 100ms | 11428kb | C++20 | 2.1kb | 2024-11-20 18:27:01 | 2024-11-20 18:27:03 |
Judging History
answer
#include <bits/stdc++.h>
#define endl "\n"
typedef long long i64;
template <class T> constexpr T Pow(T a, i64 b){
T res = 1;
for( ; b ; b >>= 1, a *= a) if(b & 1) res *= a;
return res;
}
template <int P> struct mint{
int x;
constexpr mint() : x{} {}
constexpr mint(i64 x) : x(Set(x % P)) {}
constexpr int Set(int x) const {
if(x < 0) x += P;
if(x >= P) x -= P;
return x;
}
constexpr int val() const { return x; }
explicit constexpr operator int() const { return x; }
constexpr mint operator-() const { mint res; res.x = Set(P - x); return res; }
constexpr mint inv() const { assert(x != 0); return Pow(*this, P - 2); }
constexpr mint operator*=(mint a) { x = 1ll * x * a.x % P; return *this; }
constexpr mint operator+=(mint a) { x = Set(x + a.x); return *this; }
constexpr mint operator-=(mint a) { x = Set(x - a.x); return *this; }
constexpr mint operator/=(mint a) { return *this *= a.inv(); }
constexpr friend mint operator*(mint a, mint b) { mint res = a; res *= b; return res; }
constexpr friend mint operator+(mint a, mint b) { mint res = a; res += b; return res; }
constexpr friend mint operator-(mint a, mint b) { mint res = a; res -= b; return res; }
constexpr friend mint operator/(mint a, mint b) { mint res = a; res /= b; return res; }
constexpr friend bool operator==(mint a, mint b) { return a.val() == b.val(); }
constexpr friend bool operator!=(mint a, mint b) { return a.val() != b.val(); }
};
template<int V, int P> constexpr mint<P> CInv = mint<P>(V).inv();
constexpr int P = 998244353;
using Z = mint<P>;
const int N = 1e6 + 10;
Z dp[N], pre[N];
signed main(){
std::cin.tie(nullptr) -> sync_with_stdio(false);
int n;
std::cin >> n;
for(int i = 1;i <= n;i++){
dp[i] = pre[i - 1] + 1;
for(int j = 0;j <= 20;j++){
if((i >> j & 1) && i >= (1 << j + 1)){
dp[i] -= pre[(1 << j + 1) - 1] - pre[(1 << j) - 1];
}
}
pre[i] = pre[i - 1] + dp[i];
}
std::cout << pre[n].val() << endl;
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5644kb
input:
1
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 5584kb
input:
2
output:
3
result:
ok 1 number(s): "3"
Test #3:
score: 0
Accepted
time: 1ms
memory: 5500kb
input:
3
output:
6
result:
ok 1 number(s): "6"
Test #4:
score: 0
Accepted
time: 1ms
memory: 5584kb
input:
5
output:
26
result:
ok 1 number(s): "26"
Test #5:
score: 0
Accepted
time: 1ms
memory: 5540kb
input:
322
output:
782852421
result:
ok 1 number(s): "782852421"
Test #6:
score: 0
Accepted
time: 1ms
memory: 5636kb
input:
10
output:
728
result:
ok 1 number(s): "728"
Test #7:
score: 0
Accepted
time: 1ms
memory: 5612kb
input:
100
output:
234222727
result:
ok 1 number(s): "234222727"
Test #8:
score: 0
Accepted
time: 0ms
memory: 5640kb
input:
10000
output:
348787098
result:
ok 1 number(s): "348787098"
Test #9:
score: 0
Accepted
time: 97ms
memory: 11240kb
input:
1000000
output:
246427510
result:
ok 1 number(s): "246427510"
Test #10:
score: 0
Accepted
time: 95ms
memory: 11380kb
input:
999999
output:
525546416
result:
ok 1 number(s): "525546416"
Test #11:
score: 0
Accepted
time: 84ms
memory: 11172kb
input:
950000
output:
154241852
result:
ok 1 number(s): "154241852"
Test #12:
score: 0
Accepted
time: 100ms
memory: 11324kb
input:
999888
output:
254589934
result:
ok 1 number(s): "254589934"
Test #13:
score: 0
Accepted
time: 98ms
memory: 11428kb
input:
999423
output:
917909701
result:
ok 1 number(s): "917909701"
Test #14:
score: 0
Accepted
time: 58ms
memory: 11300kb
input:
600000
output:
546076071
result:
ok 1 number(s): "546076071"
Test #15:
score: 0
Accepted
time: 1ms
memory: 5568kb
input:
1337
output:
616951443
result:
ok 1 number(s): "616951443"