結果

問題 No.1939 Numbered Colorful Balls
ユーザー shobonvipshobonvip
提出日時 2023-05-30 00:29:06
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 175 ms / 2,000 ms
コード長 4,647 bytes
コンパイル時間 5,657 ms
コンパイル使用メモリ 278,584 KB
実行使用メモリ 18,992 KB
最終ジャッジ日時 2023-08-28 00:14:53
合計ジャッジ時間 8,623 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 174 ms
18,724 KB
testcase_01 AC 16 ms
13,088 KB
testcase_02 AC 172 ms
18,872 KB
testcase_03 AC 173 ms
18,732 KB
testcase_04 AC 16 ms
13,216 KB
testcase_05 AC 175 ms
18,992 KB
testcase_06 AC 173 ms
18,716 KB
testcase_07 AC 53 ms
14,220 KB
testcase_08 AC 33 ms
13,484 KB
testcase_09 AC 172 ms
18,620 KB
testcase_10 AC 18 ms
13,104 KB
testcase_11 AC 90 ms
15,980 KB
testcase_12 AC 25 ms
13,352 KB
testcase_13 AC 18 ms
13,240 KB
testcase_14 AC 51 ms
14,204 KB
testcase_15 AC 32 ms
13,552 KB
testcase_16 AC 91 ms
16,084 KB
testcase_17 AC 92 ms
15,860 KB
testcase_18 AC 51 ms
14,224 KB
testcase_19 AC 171 ms
18,288 KB
testcase_20 AC 53 ms
14,344 KB
testcase_21 AC 172 ms
18,404 KB
testcase_22 AC 25 ms
13,368 KB
testcase_23 AC 91 ms
15,932 KB
testcase_24 AC 173 ms
18,356 KB
testcase_25 AC 90 ms
15,924 KB
testcase_26 AC 172 ms
18,860 KB
testcase_27 AC 17 ms
13,160 KB
testcase_28 AC 15 ms
13,008 KB
testcase_29 AC 90 ms
16,028 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;

typedef modint998244353 mint;
typedef long long ll;

//defmodfact
const int COMinitMAX = 1234567;
mint fact[COMinitMAX+1], factinv[COMinitMAX+1];

void modfact(){
	fact[0] = 1;
	for (int i=1; i<=COMinitMAX; i++){
		fact[i] = fact[i-1] * i;
	}
	factinv[COMinitMAX] = fact[COMinitMAX].inv();
	for (int i=COMinitMAX-1; i>=0; i--){
		factinv[i] = factinv[i+1] * (i+1);
	}
}

mint cmb(int a, int b){
	if (a<b || b<0) return mint(0);
	return fact[a]*factinv[b]*factinv[a-b];
}
//--------


vector<mint> poly_inv(vector<mint> &a, int M = -314159265){
	if (M == -314159265) M = (int)a.size();
	else if (M <= 0) return {};
	int n = a.size();
	mint r = a[0].pow((ll)(mint::mod())-2);
	int m = 1;
	vector<mint> res = {r};
	while (m < M){
		vector<mint> f = a;
		f.resize(2 * m);
		vector<mint> g = res;
		g.resize(2 * m);
		internal::butterfly(f);
		internal::butterfly(g);
		for (int i=0; i<2*m; i++){
			f[i] = f[i] * g[i];
		}
		internal::butterfly_inv(f);
		for (int i=0; i<m; i++){
			f[i] = f[i + m];
		}
		for (int i=0; i<m; i++){
			f[i + m] = 0;
		}
		internal::butterfly(f);
		for (int i=0; i<2*m; i++){
			f[i] = f[i] * g[i];
		}
		internal::butterfly_inv(f);
		mint iz = mint(2*m).inv();
		iz = -iz * iz;
		for (int i=0; i<m; i++){
			f[i] = f[i] * iz;
		}
		res.insert(res.end(), f.begin(), f.begin()+m);
		m <<= 1;
	}
	res.resize(M);
	return res;
}

vector<mint> poly_log(vector<mint> &a, int M = -314159265){
	if (M == -314159265) M = (int)a.size();
	else if (M <= 0) return {};
	int n = a.size();
	if (n == 1) return vector<mint>(M, 0);
	vector<mint> b(n-1);
	for (int i=0; i<n-1; i++){
		b[i] = a[i+1] * (i+1);
	}
	vector<mint> t = convolution<mint>(b, poly_inv(a, M));
	vector<mint> ret(M);
	for (int i=0; i<M-1; i++){
		ret[i+1] = t[i] * factinv[i+1] * fact[i];
	}
	return ret;
}

vector<mint> poly_exp(vector<mint> &a, int M = -314159265){
	if (M == -314159265) M = (int)a.size();
	else if (M <= 0) return {};
	int n = a.size();
	int m = 1;
	vector<mint> res = {1};
	while (m < M){
		vector<mint> f(2*m);
		for (int i=0; i<min(n, 2*m); i++) f[i] = a[i];
		vector<mint> v = poly_log(res, 2*m);
		vector<mint> w(2*m);
		for (int i=0; i<2*m; i++) w[i] = f[i] - v[i];
		w[0] += 1;
		vector<mint> g = convolution<mint>(res, w);
		res.insert(res.end(), g.begin()+m, g.begin()+2*m);
		m <<= 1;
	}
	res.resize(M);
	return res;
}

vector<mint> poly_pow_nonzero(vector<mint> &a, ll m, ll l){
	int n = a.size();
	mint bais = a[0].pow(m);
	mint invs;
	if (a[0].val() == 0) invs = 0;
	else invs = a[0].inv();
	vector<mint> r(n);
	for (int i=0; i<n; i++) r[i] = a[i] * invs;
	r = poly_log(r, l);
	for (int i=0; i<l; i++) r[i] = r[i] * m;
	r = poly_exp(r, l);
	for (int i=0; i<l; i++) r[i] = r[i] * bais;
	return r;
}

vector<mint> poly_pow(vector<mint> &a, ll m, ll l){
	int n = a.size();
	int ind = 0;
	for (int i=0; i<n; i++){
		if (a[i].val() != 0){
			ind = i;
			break;
		}
	}
	ll g = min(m, (ll)3141592653);
	if (g*ind >= l){
		return vector<mint>(l, 0);
	}
	vector<mint> ret(g*ind);
	vector<mint> b(n-ind);
	for (int i=0; i<n-ind; i++) b[i] = a[i+ind];
	vector<mint> tmp;
	if (l-g*ind > 0) tmp = poly_pow_nonzero(b, m, l-g*ind);
	else tmp = {};
	ret.insert(ret.end(), tmp.begin(), tmp.end());
	return ret;
}

int ceil_pow2(int n) {
    int x = 0;
    while ((1U << x) < (unsigned int)(n)) x++;
    return x;
}

vector<mint> multi_eval(vector<mint> x, vector<mint> a){
	int n = x.size();
	int siz = 1 << ceil_pow2(n);
	vector<vector<mint>> g(2*siz, vector<mint>{1});
	for (int i=0; i<n; i++) g[i + siz] = {-x[i], 1};
	for (int i=siz-1; i>0; i--) g[i] = convolution(g[2*i], g[2*i+1]);
	vector<mint> f;
	for (int i=1; i<2*siz; i++){
		if (i==1) f = a;
		else f = g[i>>1];
		int fs = f.size(), gs = g[i].size();
		int m = fs - gs + 1;
		vector<mint> v = {}, w = {};
		if (m > 0){
			vector<mint> ft(m);
			for (int j=0; j<m; j++) ft[j] = f[fs-1-j];
			vector<mint> gt(gs);
			for (int j=0; j<gs; j++) gt[j] = g[i][gs-1-j];
			v = convolution(ft, poly_inv(gt, m));
			v.resize(m);
			reverse(v.begin(), v.end());
			w = convolution(v, g[i]);
		}
		g[i] = f;
		for (int j=0; j<w.size(); j++){
			g[i][j] -= w[j];
		}
		while (g[i].size() > 1 && g[i][g[i].size() - 1] == 0){
			g[i].pop_back();
		}
	}
	vector<mint> ret(n);
	for (int i=0; i<n; i++){
		ret[i] = g[i+siz][0];
	}
	return ret;
}



int main(){
	modfact();
	int n, m; cin >> n >> m;
	vector<int> l(m);
	vector<mint> f(n+1);
	for (int i=0; i<m; i++){
		cin >> l[i];
		f[l[i]]++;
	}
	f[0]++;
	vector<mint> g = poly_pow(f, n+1, n+1);
	mint ans = g[n] * mint(n+1).inv();
	cout << ans.val() << endl;
}
0