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

提出ソース
結果

問題	No.3190 Scoring
コンテスト
ユーザー	蜜蜂
提出日時	2025-05-06 19:36:17
言語	C++14 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	2,062 ms / 10,000 ms
コード長	8,145 bytes
コンパイル時間	5,351 ms
コンパイル使用メモリ	271,384 KB
実行使用メモリ	107,036 KB
最終ジャッジ日時	2025-06-20 20:50:44
合計ジャッジ時間	42,508 ms
ジャッジサーバーID （参考情報）	judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
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;
}

// 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();

  vector<mint> fact(n), rfact(n);
  fact[0]=1;
  rfact[0]=1;
  rep(i,1,n){
    fact[i]=fact[i-1]*i;
  }
  rfact[n-1]=mint(1)/fact[n-1];
  per(i,n-1,2){
    rfact[i-1]=rfact[i]*i;
  }

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

  fps expcx(n,1);
  rep(i,1,n){
    expcx[i]=expcx[i-1]*c*rfact[i]*fact[i-1];
  }

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

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

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

// sum i = [0, n]: a_i (x + p)^i (x + q)^(n - i)
// a の長さは n + 1 を要求
fps sub2(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;
}

fps nv2(int n,vector<mint> &a,mint p,mint q){
	fps f(n+1,0);
	fps x1={p-q,1};
	fps g={1};
	rep(i,0,n+1){
		rep(j,0,i+1){
			f[n-i+j]+=a[i]*g[j];
		}
		g=convolution(g,x1);
	}
	f=taylor_shift(f,q.val());
	return f;
}

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());
	}
	vector<mint> a(n+1,0);
	rep(i,l,r){
		a[i]=COM(n,i);
		if((n-i)%2==1)a[i]*=-1;
	}
	rep(i,0,n+1){
		cout<<a[i].val()<<" ";
	}
	cout<<endl;
	fps f2=sub2(n,a,0,-1);
	for(mint v:f2)cerr<<v.val()<<" ";
	cerr<<endl;
	fps f_nv2=nv2(n,a,0,-1);
	for(mint v:f_nv2)cerr<<v.val()<<" ";
	cerr<<endl;
	rep(i,0,n+1){
		assert(f2[i].val()==f_nv2[i].val());
	}
}

int main(){
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

	COMinit();

	// int t;cin>>t;
	// while(t--)check();

	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=sub2(m,a,0,-1);
	fps f2=sub(m,(m+1)/2,m+1);
	// for(mint vf:f)cout<<vf.val()<<" ";
	// cout<<endl;
	// for(mint vf:f2)cout<<vf.val()<<" ";
	// cout<<endl;
	vector<mint> evals=multipoint_evalution(f,ps);
	mint ans=0;
	for(mint e:evals){
		ans+=e;
	}
	ans*=n;
	cout<<ans.val()<<endl;
}
yukicoder

結果

ソースコード
