結果
| 問題 |
No.3190 Scoring
|
| ユーザー |
 蜜蜂
|
| 提出日時 | 2025-05-07 00:23:15 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,897 ms / 10,000 ms |
| コード長 | 5,932 bytes |
| コンパイル時間 | 4,449 ms |
| コンパイル使用メモリ | 262,772 KB |
| 実行使用メモリ | 104,996 KB |
| 最終ジャッジ日時 | 2025-06-20 20:51:36 |
| 合計ジャッジ時間 | 39,053 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 32 |
ソースコード
// g++-14 1.cpp -std=c++20 -O2 -I .
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/tag_and_trait.hpp>
using namespace __gnu_pbds;
#include <atcoder/modint>
#include <atcoder/convolution>
using namespace atcoder;
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vld = vector<ld>;
using vvld = vector<vld>;
using vst = vector<string>;
using vvst = vector<vst>;
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define pq_big(T) priority_queue<T,vector<T>,less<T>>
#define pq_small(T) priority_queue<T,vector<T>,greater<T>>
#define all(a) a.begin(),a.end()
#define rep(i,start,end) for(ll i=start;i<(ll)(end);i++)
#define per(i,start,end) for(ll i=start;i>=(ll)(end);i--)
#define uniq(a) sort(all(a));a.erase(unique(all(a)),a.end())
random_device seed;
mt19937_64 randint(seed());
ll grr(ll mi, ll ma) { // [mi, ma)
return mi + randint() % (ma - mi);
}
using mint = modint998244353;
using fps = vector<mint>;
const int MAX=510000;
const long long MOD=998244353;
long long fac[MAX],finv[MAX],inv[MAX];
void COMinit(){
fac[0]=fac[1]=1;
finv[0]=finv[1]=1;
inv[1]=1;
for(int i=2;i<MAX;i++){
fac[i]=fac[i-1]*i%MOD;
inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD;
finv[i]=finv[i-1]*inv[i]%MOD;
}
}
long long COM(int n,int k){
if(n<k) return 0;
if(n<0||k<0) return 0;
return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD;
}
// fg = 1 mod x^d となるgを求める
// https://judge.yosupo.jp/submission/33016
fps inv_fps(fps &f,int d){
int n=f.size();
assert(n!=0&&f[0]!=0);
assert(d>=0);
fps res(1);
res[0]=1/f[0];
for(int m=1;m<d;m*=2){
fps f1(f.begin(),f.begin()+min(n,2*m));
fps g(res);
f1.resize(2*m),internal::butterfly(f1);
g.resize(2*m),internal::butterfly(g);
rep(i,0,2*m){
f1[i]*=g[i];
}
internal::butterfly_inv(f1);
f1.erase(f1.begin(),f1.begin()+m);
f1.resize(2*m),internal::butterfly(f1);
rep(i,0,2*m){
f1[i]*=g[i];
}
internal::butterfly_inv(f1);
mint iz=mint(2*m).inv(); iz*=-iz;
rep(i,0,m)f1[i]*=iz;
res.insert(res.end(),f1.begin(),f1.begin()+m);
}
res.resize(d);
return res;
}
// f=g*q+rとなるq,rを{q,r}で返す
// https://judge.yosupo.jp/submission/71356
// https://judge.yosupo.jp/submission/142762
pair<fps,fps> div_fps(fps &f,fps g){
while(!g.empty()&&g.back().val()==0){
g.pop_back();
}
if(g.empty()){
cerr<<"ERROR : g is 0"<<endl;
exit(9);
}
if(f.size()<g.size()){
return {{},f};
}
reverse(all(g));
int n=f.size(),m=g.size();
fps invg=inv_fps(g,n-m+1);
reverse(all(f));
fps t=convolution(f,invg);
t.resize(n-m+1);
fps q(n-m+1);
rep(i,0,n-m+1){
q[n-m-i]=t[i];
}
reverse(all(f));
reverse(all(g));
t=convolution(g,q);
fps r(m-1);
rep(i,0,m-1){
r[i]=f[i]-t[i];
}
while(!r.empty()&&r.back().val()==0){
r.pop_back();
}
return {q,r};
}
// f(x0),f(x1),... を求める
// https://37zigen.com/multipoint-evaluation/
vector<mint> multipoint_evalution(fps &f,vector<mint> &x){
int m=x.size();
int d=0;
while((1<<d)<m){
d++;
}
int n=(1<<d);
vector<fps> tree1(2*n),tree2(2*n);
rep(i,0,n){
if(i<m){
tree1[n+i]={-x[i],1};
}
else{
tree1[n+i]={1};
}
}
per(i,n-1,1){
tree1[i]=move(convolution(tree1[2*i],tree1[2*i+1]));
}
tree2[1]=div_fps(f,tree1[1]).se;
rep(i,2,2*n){
tree2[i]=div_fps(tree2[i/2],tree1[i]).se;
}
vector<mint> res;
rep(i,0,m){
if(tree2[n+i].size()==0){
res.emplace_back(0);
}
else{
res.emplace_back(tree2[n+i][0].val());
}
}
return res;
}
// sum i = [l, r) : nCi x^i (1 - x)^(n - i)
fps sub(int n,int l,int r){
// prod i = [l, r) : 1/i
auto finv_rng = [&](int left,int right){
if(left>=right)return (mint)1;
mint res=finv[right-1];
res*=fac[left-1];
return res;
};
// sum i = [0, lim) : x^i/((ofset_l + 1) * ... * (ofset_l + i)) (1 - x)^(lim - 1 - i) / ((ofset_r + 1) * ... + (ofset_r + lim - 1 - i))
auto work = [&](auto& work,int lim,int ofset_l,int ofset_r){
fps res;
if(lim==0){
res={0};
return res;
}
if(lim==1){
res={1};
return res;
}
int mid=lim/2;
int rem=lim-mid;
fps f1=work(work,mid,ofset_l,ofset_r+rem);
fps f2=work(work,rem,ofset_l+mid,ofset_r);
// f1 * (1 - x)^rem / fac_rng(ofset_r + 1, ofset_r + rem + 1)
// f2 * x^mid / fac_rng(ofset_l + 1, ofset_l + mid + 1)
fps tag1(rem+1);
rep(i,0,rem+1){
tag1[i]=COM(rem,i);
if(i%2==1)tag1[i]*=-1;
}
f1=convolution(f1,tag1);
reverse(all(f2));
rep(i,0,mid)f2.emplace_back(0);
reverse(all(f2));
mint fac1=finv_rng(ofset_r+1,ofset_r+rem+1),fac2=finv_rng(ofset_l+1,ofset_l+mid+1);
for(mint &v1:f1)v1*=fac1;
for(mint &v2:f2)v2*=fac2;
rep(i,0,max(f1.size(),f2.size())){
res.emplace_back(0);
if(i<f1.size())res[i]+=f1[i];
if(i<f2.size())res[i]+=f2[i];
}
return res;
};
fps w=work(work,r-l,l,n-r+1);
mint fac1=finv_rng(1,l+1),fac2=finv_rng(1,n-r+2);
fps tag(n-r+2);
rep(i,0,n-r+2){
tag[i]=COM(n-r+1,i);
if(i%2==1)tag[i]*=-1;
}
w=convolution(w,tag);
reverse(all(w));
rep(i,0,l)w.emplace_back(0);
reverse(all(w));
for(mint &v:w)v*=(fac1*fac2);
for(mint &v:w)v*=fac[n];
return w;
}
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
COMinit();
int n,s,m;cin>>n>>s>>m;
vector<mint> ps;
rep(i,1,s+1){
mint prob=fac[s]*fac[n+s-i-1];
prob*=finv[s-i]*finv[n+s-1];
ps.emplace_back(prob);
}
vector<mint> a(m+1,0);
rep(i,(m+1)/2,m+1){
a[i]=COM(m,i);
if((m-i)%2==1)a[i]*=-1;
}
fps f=sub(m,(m+1)/2,m+1);
vector<mint> evals=multipoint_evalution(f,ps);
mint ans=0;
for(mint e:evals){
ans+=e;
}
ans*=n;
cout<<ans.val()<<endl;
}