QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#197038 | #6678. Gem Island 2 | jeffqi | WA | 445ms | 599316kb | C++20 | 1.9kb | 2023-10-02 09:13:56 | 2023-10-02 09:13:57 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define vi vector<int>
#define vll vector<ll>
#define eb emplace_back
#define pb push_back
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define umap unordered_map
#define uset unordered_set
#define mset multiset
#define ui unsigned int
#define ull unsigned ll
#define i128 __int128
using namespace std;
namespace qiqi {
const int N = 3e7,P = 998244353;
array<ll,N+1> fac,ifac; vi p;
ll pow(ll b,ll k) {
ll a = 1;
for (; k; b = b*b%P,k >>= 1) {
if (k&1) {
a = a*b%P;
}
}
return a;
}
void init(int n = N) {
fac[0] = 1;
for (int i = 1; i <= n; i++) {
fac[i] = i*fac[i-1]%P;
}
ifac[n] = pow(fac[n],P-2);
for (int i = n; i >= 1; i--) {
ifac[i-1] = i*ifac[i]%P;
}
vi isp(n+1,1);
for (int i = 2; i <= n; i++) {
if (isp[i]) {
p.eb(i);
}
for (auto x:p|views::take_while([&](int k) {return i*k <= n;})) {
isp[i*x] = 0; if (!(i%x)) {break;}
}
}
}
ll C(int n,int m) {
return m < 0 || n < m ? 0 : fac[n]*ifac[m]%P*ifac[n-m]%P;
}
void main() {
init();
int n,d,r;
cin >> n >> d >> r;
const int m = n-1+d;
vi f(m+1); iota(f.begin(),f.end(),0);
ranges::transform(f,f.begin(),[&](int x) {
return C(m-x,n-1);
});
for (auto x:p) {
for (int i = m/x; i >= 1; i--) {
f[i] = (f[i]+f[i*x])%P;
}
}
int ans = 0;
for (int i = 1; i <= n; i++) {
ll k = f[i]*C(n,i)%P;
if (i > r) {
k = k*C(i-2,r-1)%P;
if ((i+r)%2) {
k = -k;
}
}
ans = (ans+k)%P;
}
ans = (ans*pow(C(m,n-1),P-2)+r)%P;
cout << (ans+P)%P << '\n';
}
}
int main() {
// clock_t st = clock();
// freopen("test.in","r",stdin);
// freopen("test.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
// cin >> T;
while (T--) {
qiqi::main();
}
// cout << (double)(clock()-st)/CLOCKS_PER_SEC;
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 445ms
memory: 598036kb
input:
2 3 1
output:
499122180
result:
ok 1 number(s): "499122180"
Test #2:
score: -100
Wrong Answer
time: 379ms
memory: 599316kb
input:
3 3 2
output:
399297747
result:
wrong answer 1st numbers differ - expected: '698771052', found: '399297747'