QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#248189#7632. Balanced Arraysucup-team2307AC ✓216ms17796kbC++207.9kb2023-11-11 17:48:592023-11-11 17:48:59

Judging History

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

  • [2023-11-11 17:48:59]
  • 评测
  • 测评结果:AC
  • 用时:216ms
  • 内存:17796kb
  • [2023-11-11 17:48:59]
  • 提交

answer

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2")
#include<bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;

template<typename F>
void multitest(F func) {
	int t;
	cin >> t;
	while(t--) func();
}
void report(int ok) {
	cout << (ok?"YES":"NO") << '\n';
}

const int mod = 998244353;
namespace math {
const int L = 1<<20, A = 1<<20, B = 32, G = 3;

#define INLINE inline __attribute__ (( always_inline ))
struct mint {
	uint32_t v;
	template<class T = int>
	mint(T x = 0) {
		x %= mod;
		if(x < 0) x += mod;
		v = x;
	}
	mint operator-() const {
		return mint(v ? mod-v : 0);
	}
	mint &operator*=(const mint &r) {
		v = v*1ll*r.v%mod;
		return *this;
	}
	mint &operator+=(const mint &r) {
		v = v+r.v>=mod ? (v+r.v-mod) : (v+r.v);
		return *this;
	}
	mint &operator-=(const mint &r) { 
		return *this += -r;
	}
	mint &operator/=(const mint &r) {
		return *this *= r.inv();
	}
	friend mint operator+(mint a, const mint &b) {
		return a += b;
	}
	friend mint operator-(mint a, const mint &b) {
		return a -= b;
	}
	friend mint operator*(mint a, const mint &b) {
		return a *= b;
	}
	friend mint operator/(mint a, const mint &b) {
		return a /= b;
	}
	
	template<class T = int>
	mint pow(T p) const {
		mint res = 1, cur = *this;
		while(p) {
			if(p&1) res = res*cur;
			cur = cur*cur, p>>=1;
		}
		return res;
	}
	mint inv() const {
		return mint(*this).pow(mod-2);
	}
	
	friend bool operator==(const mint &a, const mint &b) {
		return a.v == b.v;
	}
	friend bool operator!=(const mint &a, const mint &b) {
		return !(a == b);
	}
	
	friend istream& operator>>(istream &is, mint &m) {
		ll v;
		is >> v;
		m = mint(v);
		return is;
	}
	friend ostream& operator<<(ostream &os, const mint &m) {
		os << m.v; 
		return os;
	}
};

mint fact[A], inum[A], ifact[A];
void calc_inum() {
	inum[1] = 1;
	for(int i = 2; i < A; i++) inum[i] = -inum[mod%i]*(mod/i);
}
void calc_combi() {
	if(0 == inum[1]) calc_inum();
	fact[0] = ifact[0] = 1;
	for(int i = 1; i < A; i++) fact[i] = fact[i-1]*i;
	for(int i = 1; i < A; i++) ifact[i] = ifact[i-1]*inum[i];
}

mint nck(int n, int k) {
	if(0 == fact[0]) calc_combi();
	if(k > n || k < 0) return 0;
	return fact[n]*ifact[k]*ifact[n-k];
}

uint W[L], WI[L];
INLINE void calc_roots() {
	W[0] = 1;
	int g = mint(G).pow((mod-1)/L).v;
	int i;
	for(i = 1; i < L/2; i++) W[i] = W[i-1]*1ull*g%mod;
	for(int x = 2; x < L; x*=2) {
		for(int y = 0; y < L/2; y+=x)
			W[i++] = W[y];
	}
	for(i = 0; i < L; i++) {
		WI[i] = (uint64_t(W[i])<<B)/mod;
	}
}
INLINE void _ntt(int N, vector<mint> &a) {//normal poly -> bit-rev dft | internally [0; 2*mod)
	int pos = 0;
	for(int l = L/2; l != N/2; l/=2)
		pos += l;
	for(int l = N/2; l; l/=2) {
		for(int x = 0; x < N; x+=2*l) {
			for(int j = pos, i = 0; i < l; i++, j++) {
				uint u = a[x+i].v+a[x+l+i].v;
				if(u >= 2*mod) u -= 2*mod;
				uint v = a[x+i].v-a[x+l+i].v+2*mod;
				uint Q = (v*1ull*WI[j])>>B;
				v = v*W[j] - Q*mod;
				a[x+i].v = u, a[x+l+i].v = v;
			}
		}
		pos += l;
	}
	for(int i = 0; i < N; i++) if(a[i].v >= mod) a[i].v -= mod;
}

INLINE void _ntt_inv(int N, vector<mint> &a) {//bit-rev dft -> normal poly | internally [0; 4*mod)
	int pos = L-2;
	for(int l = 1; l < N; l*=2) {
		for(int x = 0; x < N; x += 2*l) {
			for(int j = pos, i = 0; i < l; i++, j++) {
				uint u = a[x+i].v, v = a[x+l+i].v;
				uint Q = (WI[j]*1ull*v)>>B;
				if(u >= 2*mod) u -= 2*mod;
				v = v*W[j] - Q*mod;
				a[x+i].v = u+v, a[x+l+i].v = u-v+2*mod;
			}
		}
		pos -= 2*l;
	}
	reverse(1 + all(a));
	mint x = mint((mod+1)/2).pow(__lg(N));
	for(auto &i : a) i *= x;//takes care of 2*mod
}
template<bool inv>
INLINE void ntt(int n, vector<mint> &a) {//don't forget about reverse order
	if(W[0] == 0) calc_roots();
	if(!inv) _ntt(n, a);
	else _ntt_inv(n, a);
}


struct poly : vector<mint> {
	template<class... Args>
	explicit poly(Args... args) : vector<mint>(args...) {}
	poly(initializer_list<mint> il) : vector<mint>(il.begin(), il.end()) {}
	poly &trim(int k) {// mod x^k
		if(size() > k) {
			erase(begin()+k, end());
			shrink_to_fit();
		}
		return *this;
	}
	poly &trim() {//remove heading zeroes
		int k = 0;
		while(k < size() && (*this)[size()-k-1] == 0) k++;
		trim(size()-k);
		return *this;
	}
	poly low(int k) const {//get first k coefficients
		k = min(k, (int)size());
		poly res;
		for(int i = 0; i < k; i++) res.push_back((*this)[i]);
		return res;
	}
	friend poly operator*(poly a, const poly &b) {
		poly res = b;
		int n = a.size()+b.size()-1;
		while(n&(n-1)) n += n&-n;
		a.resize(n);
		res.resize(n);
		ntt<0>(n, a);
		ntt<0>(n, res);
		for(int i = 0; i < n; i++) res[i] *= a[i];
		ntt<1>(n, res);
		res.trim();//remove ?
		return res;
	}
	poly &operator*=(const poly &b) {
		return (*this) = (*this)*b;
	}
	
	template<class T>
	poly &operator*=(const T &x) {
		for(auto &i : *this) i *= x;
		return *this;
	}
	poly &operator+=(const poly &x) {
		if(size() < x.size()) resize(x.size());
		for(int i = 0; i < min(size(), x.size()); i++) (*this)[i] += x[i];
		return *this;
	}
	poly &operator-=(const poly &x) {
		if(size() < x.size()) resize(x.size());
		for(int i = 0; i < min(size(), x.size()); i++) (*this)[i] -= x[i];
		return *this;
	}
	
	template<class T> friend poly operator*(poly p, const T &x) { return p *= x; }
	template<class T> friend poly operator*(const T &x, poly p) { return p *= x; }
	friend poly operator+(poly p, const poly &x) { return p += x; }
	friend poly operator-(poly p, const poly &x) { return p -= x; }
	
	poly inv(int N) {//first n coefficients of P^-1
		assert((*this)[0].v);
		poly R {(*this)[0].inv()};
		R.reserve(2*N);
		for(int len = 2; len/2 < N; len*=2) {//R' = R(2 - RT)
			poly T = low(len);
			T.resize(2*len);ntt<0>(2*len, T);
			R.resize(2*len);ntt<0>(2*len, R);
			for(int i = 0; i < 2*len; i++) R[i] = R[i]*(2 - R[i]*T[i]);
			ntt<1>(2*len, R);
			R.trim(len);
		}
		return R.trim(N);
	}
	poly &derive() {
		for(int i = 0; i+1 < size(); i++) {
			(*this)[i] = (*this)[i+1]*(i+1);
		}
		pop_back();
		return *this;
	}
	
	poly derivative() { return poly(*this).derive(); }
	poly &integrate() {
		if(0 == inum[1]) calc_inum();
		push_back(0);
		for(int i = size(); i-- > 1;) {
			(*this)[i] = (*this)[i-1] * inum[i];
		}
		(*this)[0] = 0;
		return *this;
	}
	poly integral() { return poly(*this).integrate(); }
	
	poly ln(int N) {//first n coefficients of ln(P) = P'/P
		return (low(N+1).derivative() * inv(N)).trim(N-1).integrate().trim(N);
	}
	poly exp(int N) {//first n coefficients of exp(P), quite slow
		poly R{1};
		for(int len = 2; len/2 < N; len*=2) {
			R = (R*(poly{1}+low(len)-R.ln(len))).trim(len);
		}
		return R.trim(N);
	}
};
}
using namespace math;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	//multitest([&](){});
	auto f = [&](int N, int M) -> mint {
		mint ans = 1;
		// for(int j = 0; j < N; j++)
			// ans *= mint(M + j);
		ans *= fact[M + N - 1] / fact[M - 1];
		// for(int j = 0; j < N; j++)
			// ans /= mint(N + 1 - j);
		ans /= fact[N + 1];
		// for(int j = 0; j < N; j++)
			// ans *= mint(M - 1 + j);
		ans *= fact[M + N - 2] / fact[M - 2];
		// for(int j = 0; j < N; j++)
			// ans /= mint(N - j);
		ans /= fact[N];
		// cout << N << " " << M << " " << ans << endl;
		return ans;
	};
	
	// int cnt = 0;
	// for(int a = 1; a <= 4; a++) {
		// for(int b = 1; b <= 4; b++) {
			// for(int c = 1; c <= 4; c++) {
				// for(int d = 1; d <= 4; d++) {
					// if(a < b && c < d && a <= c && b <= d) {
						// //ab
						// //cd
						// if(a - b == -1 || a - d == -1 || c - b == -1 || c - d == -1) continue;
						// cnt++;
					// }
				// }
			// }
		// }
	// }
	// cout << cnt << '\n';
	
	int n, m;
	cin >> n >> m;
	mint ans = 0;
	for(int i = 0; i <= min(m, n); i++) {
		ans += f(m - i, n + 2) * (i % 2 ? -1 : 1) * nck(n, i);
	}
	cout << ans << '\n';
}

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

详细

Test #1:

score: 100
Accepted
time: 17ms
memory: 16224kb

input:

2 2

output:

9

result:

ok 1 number(s): "9"

Test #2:

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

input:

500000 500000

output:

984531374

result:

ok 1 number(s): "984531374"

Test #3:

score: 0
Accepted
time: 14ms
memory: 17276kb

input:

500000 1

output:

219705876

result:

ok 1 number(s): "219705876"

Test #4:

score: 0
Accepted
time: 10ms
memory: 17152kb

input:

1 500000

output:

500001

result:

ok 1 number(s): "500001"

Test #5:

score: 0
Accepted
time: 156ms
memory: 16308kb

input:

500000 353535

output:

33730077

result:

ok 1 number(s): "33730077"

Test #6:

score: 0
Accepted
time: 156ms
memory: 16132kb

input:

353535 500000

output:

182445298

result:

ok 1 number(s): "182445298"

Test #7:

score: 0
Accepted
time: 216ms
memory: 16564kb

input:

499999 499999

output:

933220940

result:

ok 1 number(s): "933220940"

Test #8:

score: 0
Accepted
time: 216ms
memory: 17700kb

input:

499999 499998

output:

899786345

result:

ok 1 number(s): "899786345"

Test #9:

score: 0
Accepted
time: 170ms
memory: 16248kb

input:

377773 400009

output:

206748715

result:

ok 1 number(s): "206748715"

Test #10:

score: 0
Accepted
time: 54ms
memory: 16820kb

input:

499999 100001

output:

482775773

result:

ok 1 number(s): "482775773"

Test #11:

score: 0
Accepted
time: 194ms
memory: 17796kb

input:

444445 488884

output:

70939759

result:

ok 1 number(s): "70939759"

Test #12:

score: 0
Accepted
time: 193ms
memory: 16472kb

input:

488885 444449

output:

591315327

result:

ok 1 number(s): "591315327"

Test #13:

score: 0
Accepted
time: 14ms
memory: 16704kb

input:

500000 111

output:

313439156

result:

ok 1 number(s): "313439156"

Test #14:

score: 0
Accepted
time: 149ms
memory: 17664kb

input:

333333 444444

output:

403492103

result:

ok 1 number(s): "403492103"

Test #15:

score: 0
Accepted
time: 157ms
memory: 16996kb

input:

499994 343433

output:

334451699

result:

ok 1 number(s): "334451699"

Test #16:

score: 0
Accepted
time: 180ms
memory: 17196kb

input:

477774 411113

output:

63883341

result:

ok 1 number(s): "63883341"

Test #17:

score: 0
Accepted
time: 67ms
memory: 16368kb

input:

123456 432109

output:

238795570

result:

ok 1 number(s): "238795570"

Test #18:

score: 0
Accepted
time: 66ms
memory: 17340kb

input:

131331 467777

output:

834790039

result:

ok 1 number(s): "834790039"

Test #19:

score: 0
Accepted
time: 17ms
memory: 17384kb

input:

500000 2

output:

304727284

result:

ok 1 number(s): "304727284"

Test #20:

score: 0
Accepted
time: 13ms
memory: 17208kb

input:

1111 111

output:

98321603

result:

ok 1 number(s): "98321603"

Test #21:

score: 0
Accepted
time: 186ms
memory: 16468kb

input:

416084 493105

output:

916827025

result:

ok 1 number(s): "916827025"

Test #22:

score: 0
Accepted
time: 35ms
memory: 16032kb

input:

53888 138663

output:

57263952

result:

ok 1 number(s): "57263952"

Test #23:

score: 0
Accepted
time: 98ms
memory: 17580kb

input:

219161 382743

output:

304889787

result:

ok 1 number(s): "304889787"

Test #24:

score: 0
Accepted
time: 87ms
memory: 17004kb

input:

181392 318090

output:

12528742

result:

ok 1 number(s): "12528742"

Test #25:

score: 0
Accepted
time: 68ms
memory: 17488kb

input:

135930 422947

output:

554153000

result:

ok 1 number(s): "554153000"

Test #26:

score: 0
Accepted
time: 103ms
memory: 16748kb

input:

280507 210276

output:

812816587

result:

ok 1 number(s): "812816587"

Test #27:

score: 0
Accepted
time: 115ms
memory: 16016kb

input:

253119 420465

output:

124024302

result:

ok 1 number(s): "124024302"

Test #28:

score: 0
Accepted
time: 53ms
memory: 16144kb

input:

446636 97448

output:

150388382

result:

ok 1 number(s): "150388382"

Test #29:

score: 0
Accepted
time: 64ms
memory: 16012kb

input:

284890 126665

output:

786559507

result:

ok 1 number(s): "786559507"

Test #30:

score: 0
Accepted
time: 24ms
memory: 16032kb

input:

186708 28279

output:

607509026

result:

ok 1 number(s): "607509026"

Extra Test:

score: 0
Extra Test Passed