#1082460 (C++14) No.3190 Scoring

提出ソース
結果

問題	No.3190 Scoring
ユーザー	蜜蜂
提出日時	2025-05-06 11:44:22
言語	C++14 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	2,148 ms / 10,000 ms
コード長	6,352 bytes
コンパイル時間	5,386 ms
コンパイル使用メモリ	263,680 KB
実行使用メモリ	104,084 KB
最終ジャッジ日時	2025-06-20 20:50:47
合計ジャッジ時間	45,324 ms
ジャッジサーバーID （参考情報）	judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 4
other	AC * 32
権限があれば一括ダウンロードができます
ソースコード

raw source code
// 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>;

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

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

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

fps nv(int n,int l,int r){
	fps res(n+1,0);
	rep(i,l,r){
		fps nw(n-i+1);
		rep(j,0,n-i+1){
			nw[j]=COM(n-i,j);
			if(j%2==1)nw[j]*=-1;
		}
		reverse(all(nw));
		rep(j,0,i)nw.emplace_back(0);
		reverse(all(nw));
		rep(j,0,n+1){
			res[j]+=nw[j]*COM(n,i);
		}
	}
	return res;
}

void check(){
	int n,l,r;cin>>n>>l>>r;
	fps f=sub(n,l,r);
	for(mint v:f)cerr<<v.val()<<" ";
	cerr<<endl;
	fps f_nv=nv(n,l,r);
	for(mint v:f_nv)cerr<<v.val()<<" ";
	cerr<<endl;
	rep(i,0,n+1){
		assert(f[i].val()==f_nv[i].val());
	}
}

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);
	}
	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;
}
yukicoder

結果

ソースコード
