QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#229949#7634. Cardsucup-team052#AC ✓3449ms17044kbC++145.2kb2023-10-28 17:17:592023-10-28 19:29:05

Judging History

你现在查看的是最新测评结果

  • [2023-10-28 19:29:05]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:3449ms
  • 内存:17044kb
  • [2023-10-28 17:18:15]
  • 评测
  • 测评结果:100
  • 用时:3464ms
  • 内存:17052kb
  • [2023-10-28 17:17:59]
  • 提交

answer

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

const int md = 998244353;

inline int add(int x, int y) {
	if (x + y >= md) return x + y - md;
	return x + y;
}

inline int sub(int x, int y) {
	if (x < y) return x - y + md;
	return x - y;
}

inline int mul(int x, int y) {
	return 1ull * x * y % md;
}

inline int fpow(int x, int y) {
	int ans = 1;
	while (y) {
		if (y & 1) ans = mul(ans, x);
		y >>= 1; x = mul(x, x);
	}
	return ans;
}

namespace Module{ // by txc
	#define ll long long
	#define ull unsigned ll
	const int N = 1<<20, P = 998244353; // !!
	int Pow(ll x, int y=P-2){
		int ans=1;
		for(; y; y>>=1, x=x*x%P) if(y&1) ans=ans*x%P;
		return ans;
	}
	int w[N];
	ull F[N];
	struct init{
		init(){
			for(int i=1; i<N; i<<=1){
				w[i]=1;
				int t=Pow(3, (P-1)/i/2);
				for(int j=1; j<i; ++j) w[i+j]=(ll)w[i+j-1]*t%P;
			}
		}
	} foo;
	int Get(int x){ int n=1; while(n<=x) n<<=1; return n;}
	void DFT(vector<int> &f, int n){
		if((int)f.size()!=n) f.resize(n);
		for(int i=0, j=0; i<n; ++i){
			F[i]=f[j];
			for(int k=n>>1; (j^=k)<k; k>>=1);
		}
		for(int i=1; i<n; i<<=1) for(int j=0; j<n; j+=i<<1){
			int *W=w+i;
			ull *F0=F+j, *F1=F+j+i;
			for(int k=j; k<j+i; ++k, ++W, ++F0, ++F1){
				ull t=(*F1)**W%P;
				(*F1)=*F0+P-t, (*F0)+=t;
			}
		}
		for(int i=0; i<n; ++i) f[i]=F[i]%P;
	}
	void IDFT(vector<int> &f, int n){
		f.resize(n), reverse(f.begin()+1, f.end()), DFT(f, n);
		int I=1;
		for(int i=1; i<n; i<<=1) I=(ll)I*(P+1)/2%P;
		for(int i=0; i<n; ++i) f[i]=(ll)f[i]*I%P;
	}
	vector<int> operator +(const vector<int> &f, const vector<int> &g){
		vector<int> ans=f;
		ans.resize(max(f.size(), g.size()));
		for(int i=0; i<(int)g.size(); ++i) (ans[i]+=g[i])%=P;
		return ans;
	}
	vector<int> operator *(const vector<int> &f, const vector<int> &g){
		vector<int> F, G;
		F=f, G=g;
		int p=Get(f.size()+g.size()-2);
		DFT(F, p), DFT(G, p);
		for(int i=0; i<p; ++i) F[i]=(ll)F[i]*G[i]%P;
		IDFT(F, p);
		return F.resize(f.size()+g.size()-1), F;
	}
	vector<int> Inv(const vector<int> &f, int n=-1){
		if(n==-1) n=f.size();
		if(n==1) return {Pow(f[0])};
		vector<int> ans=Inv(f, (n+1)/2), tmp(f.begin(), f.begin()+n);
		int p=Get(n*2-2);
		DFT(tmp, p), DFT(ans, p);
		for(int i=0; i<p; ++i) ans[i]=(2-(ll)ans[i]*tmp[i]%P+P)*ans[i]%P;
		IDFT(ans, p);
		return ans.resize(n), ans;
	}
	vector<int> Mod(const vector<int> &a, const vector<int> &b){
		if(b.size()>a.size()) return a;
		vector<int> A=a, B=b, iB;
		int n=a.size(), m=b.size();
		reverse(A.begin(), A.end()), reverse(B.begin(), B.end());
		B.resize(n-m+1), iB=Inv(B, n-m+1);
		vector<int> d=A*iB;
		d.resize(n-m+1), reverse(d.begin(), d.end());
		vector<int> r=b*d;
		r.resize(m-1);
		for(int i=0; i<m-1; ++i) r[i]=(a[i]-r[i]+P)%P;
		return r;
	}
	vector<int> Prod(const vector<int> &a, const vector<int> &b){
		return a*b;
	}
	#undef ll
	#undef ull
}

using Module::operator *;

const int N = 1e5 + 5, B = 500;

vector <int> f, g, F, nf;
int a[5], dp[4 * B + 1], ndp[4 * B + 1];
int n, m, ans;

int main() {
	ios::sync_with_stdio(false); cin.tie(0);
	cin >> n >> m;
	cin >> a[0] >> a[1] >> a[2] >> a[3] >> a[4];
	int sum = 0;
	for (int i = 0; i <= 4; i++) sum = add(sum, a[i]);
	for (int i = 0; i <= 4; i++) a[i] = mul(a[i], fpow(sum, md - 2));
	dp[0] = 1;
	for (int i = 1; i <= B; i++) {
		memset(ndp, 0, sizeof(ndp));
		for (int j = 0; j <= 4 * i; j++) {
			for (int k = 0; k <= 4; k++) {
				ndp[j + k] = add(ndp[j + k], mul(dp[j], a[k]));
			}
		}
		memcpy(dp, ndp, sizeof(dp));
	}
	g.resize(4 * B + 1);
	for (int i = 0; i <= 4 * B; i++) g[i] = dp[i];
	if (n >= m * 2) {
		cout << 1 << endl;
		return 0;
	}
	f.resize(m * 2); f[n] = 1;
	for (int __ = 1; __ <= m / B; __++) {
		nf.clear(); nf.resize(m * 2);
		memset(dp, 0, sizeof(dp));
		for (int j = 0; j < 2 * B; j++) {
			if (j < (int)f.size()) dp[j] = f[j];
		}
		for (int _ = 0; _ < B; _++) {
			memset(ndp, 0, sizeof(ndp));
			for (int j = 0; j < 2 * B + 2 * _; j++) {
				for (int k = -2; k <= 2; k++) {
					if (j + k >= 0) {
						ndp[j + k] = add(ndp[j + k], mul(dp[j], a[k + 2]));
					}
				}
			}
			memcpy(dp, ndp, sizeof(dp));
		}
		for (int i = 0; i < 4 * B; i++) {
			if (i < m * 2) nf[i] = add(nf[i], dp[i]);
			else ans = add(ans, dp[i]);
		}
		if ((int)f.size() >= 2 * B) {
			F.resize((int)f.size() - 2 * B);
			for (int j = 0; j < (int)F.size(); j++) F[j] = f[j + 2 * B];
			F = F * g;
			if ((int)F.size() > m * 2) {
				for (int i = m * 2; i < (int)F.size(); i++) ans = add(ans, F[i]);
				F.resize(m * 2);
			}
			for (int i = 0; i < (int)F.size(); i++) nf[i] = add(nf[i], F[i]);
		}
		f = nf;
	}
	for (int i = 2 * B; i < (int)f.size(); i++) ans = add(ans, f[i]);
	memset(dp, 0, sizeof(dp));
	for (int j = 0; j < 2 * B; j++) {
		if (j < (int)f.size()) dp[j] = f[j];
	}
	for (int _ = 0; _ < m % B; _++) {
		memset(ndp, 0, sizeof(ndp));
		for (int j = 0; j < 2 * B + 2 * _; j++) {
			for (int k = -2; k <= 2; k++) {
				if (j + k >= 0) {
					ndp[j + k] = add(ndp[j + k], mul(dp[j], a[k + 2]));
				}
			}
		}
		memcpy(dp, ndp, sizeof(dp));
	} 
	for (int i = 0; i < 4 * B; i++) ans = add(ans, dp[i]);
	cout << ans << endl;
	return 0;
}

这程序好像有点Bug,我给组数据试试?

详细

Test #1:

score: 100
Accepted
time: 8ms
memory: 8136kb

input:

1 1
1 1 1 1 1

output:

399297742

result:

ok 1 number(s): "399297742"

Test #2:

score: 0
Accepted
time: 3316ms
memory: 16916kb

input:

100000 100000
1234 4567 7890 4321 54321

output:

348074135

result:

ok 1 number(s): "348074135"

Test #3:

score: 0
Accepted
time: 3086ms
memory: 16888kb

input:

100000 100000
1 2 3 4 5

output:

639188342

result:

ok 1 number(s): "639188342"

Test #4:

score: 0
Accepted
time: 3162ms
memory: 16972kb

input:

100000 100000
5 4 3 2 1

output:

211669278

result:

ok 1 number(s): "211669278"

Test #5:

score: 0
Accepted
time: 9ms
memory: 8912kb

input:

0 0
1 1 1 1 1

output:

1

result:

ok 1 number(s): "1"

Test #6:

score: 0
Accepted
time: 955ms
memory: 14256kb

input:

1 50000
1 1 1 1 1

output:

548880636

result:

ok 1 number(s): "548880636"

Test #7:

score: 0
Accepted
time: 8ms
memory: 8648kb

input:

50000 1
1 1 1 1 1

output:

1

result:

ok 1 number(s): "1"

Test #8:

score: 0
Accepted
time: 3108ms
memory: 16900kb

input:

100000 100000
234 666 7655 12234 0

output:

45268602

result:

ok 1 number(s): "45268602"

Test #9:

score: 0
Accepted
time: 3072ms
memory: 17024kb

input:

99999 99999
12345 54332 12345 65432 34444

output:

360543661

result:

ok 1 number(s): "360543661"

Test #10:

score: 0
Accepted
time: 3320ms
memory: 16912kb

input:

99998 99998
1 1 1 1 1

output:

602326230

result:

ok 1 number(s): "602326230"

Test #11:

score: 0
Accepted
time: 3449ms
memory: 17024kb

input:

99998 99997
1 1 1 1 1

output:

159752985

result:

ok 1 number(s): "159752985"

Test #12:

score: 0
Accepted
time: 3411ms
memory: 16980kb

input:

99997 100000
1 2 3 4 5

output:

139603712

result:

ok 1 number(s): "139603712"

Test #13:

score: 0
Accepted
time: 3100ms
memory: 17044kb

input:

100000 99997
1 2 2 1 3232323

output:

363030953

result:

ok 1 number(s): "363030953"

Test #14:

score: 0
Accepted
time: 8ms
memory: 8168kb

input:

0 0
0 0 1 0 0

output:

1

result:

ok 1 number(s): "1"

Test #15:

score: 0
Accepted
time: 119ms
memory: 12024kb

input:

10000 10000
91095828 93770094 5303328 491263 50290308

output:

135900098

result:

ok 1 number(s): "135900098"

Test #16:

score: 0
Accepted
time: 118ms
memory: 8908kb

input:

9226 9995
62366139 253808 1929312 491263 4375669

output:

812662634

result:

ok 1 number(s): "812662634"

Test #17:

score: 0
Accepted
time: 120ms
memory: 12032kb

input:

18641 10000
1061 4359 1330 13764 16043

output:

112339046

result:

ok 1 number(s): "112339046"

Extra Test:

score: 0
Extra Test Passed