結果

問題 No.3190 Scoring
コンテスト
ユーザー 蜜蜂
提出日時 2025-05-07 00:25:28
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2,096 ms / 10,000 ms
コード長 5,106 bytes
コンパイル時間 5,055 ms
コンパイル使用メモリ 260,472 KB
実行使用メモリ 106,116 KB
最終ジャッジ日時 2025-06-20 20:52:31
合計ジャッジ時間 43,279 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

// 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;
}

// f(x) の係数が与えられて f(x+c) を x の多項式として展開する
// https://judge.yosupo.jp/submission/283667
fps taylor_shift(fps &f,ll c){
	if(c==0)return f;
  int n=f.size();

  fps f2=f;
  rep(i,0,n)f2[i]*=fac[i];
  reverse(all(f2));

  fps expcx(n,1);
	mint cs=c;
  rep(i,1,n){
		expcx[i]=cs*finv[i];
		cs*=c;
  }

  f2=convolution(f2,expcx);
  while(f2.size()>n)f2.pop_back();
  reverse(all(f2));

  rep(i,0,n){
    f2[i]*=finv[i];
  }
  return f2;
}

// sum i = [0, n]: a_i (x + p)^i (x + q)^(n - i)
// a の長さは n + 1 を要求
fps sub(int n,vector<mint> &a,mint p,mint q){
	fps f(n+1);
	mint c=1;
	rep(i,0,n+1){
		f[i]=c*a[i];
		c*=p-q;
	}
	f=taylor_shift(f,((mint)1/(p-q)).val());
	reverse(all(f));
	f=taylor_shift(f,q.val());
	return f;
}

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,a,0,-1);
	vector<mint> evals=multipoint_evalution(f,ps);
	mint ans=0;
	for(mint e:evals){
		ans+=e;
	}
	ans*=n;
	cout<<ans.val()<<endl;
}
0