QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#474030#3082. Ascending MatrixBINYUWA 15ms6228kbC++142.9kb2024-07-12 15:38:212024-07-12 15:38:21

Judging History

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

  • [2024-07-12 15:38:21]
  • 评测
  • 测评结果:WA
  • 用时:15ms
  • 内存:6228kb
  • [2024-07-12 15:38:21]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod = 998244353;
const int N = 200,M = 1e5;
int n,m,k,r,c,v;
pair <ll,ll> cnt[N + 5][N + 5];
ll f[M + 5] = {1,1},inv[M + 5] = {1,1},invf[M + 5] = {1,1};
ll lenw,w[N + 5] = {1},F[N + 5],ans[N + 5];
struct Matrix
{
	int n;
	ll a[N + 5][N + 5],ans;
	void write()
	{
		for(int i = 1;i <= n;i++,puts(""))
			for(int j = 1;j <= n;j++)
				cout<<a[i][j]<<" ";puts("");
	}
	void clear()
	{
		for(int i = 1;i <= n;i++)
			for(int j = 1;j <= n;j++)
				a[i][j] = 0;
		n = 0; 
	}
	void Swap(int i,int j)
	{
		for(int k = 1;k <= n;k++)
			swap(a[i][k],a[j][k]);
	}
	void add(int i,int j,ll v)
	{
		(v += mod) %= mod;
		for(int k = 1;k <= n;k++)
			(a[i][k] += a[j][k] * v) %= mod;
	}
	void update(int i,int j)
	{
		while(a[j][i] != 0)
			add(i,j,-a[i][i] / a[j][i]),
			Swap(i,j),(ans *= mod - 1) %= mod;
	}
	ll det()
	{
		ans = 1;
		for(int i = 1;i <= n;(ans *= mod + a[i][i]) %= mod,i++)
			for(int j = n;j > i;j--)update(i,j);
		return ans;
	}
}a;
ll C(ll n,ll m)
{
	if(n < 0||m < 0||n < m)return 0;
	return f[n] * invf[m] % mod * invf[n - m] % mod;
}
void mul(ll x)
{
	for(int i = lenw;~i;i--)
		(w[i + 1] += w[i]) %= mod,
		(w[i] *= x) %= mod;
	lenw++;
}
ll qpow(ll a,ll b)
{
	a %= mod;
	ll res = 1;
	while(b)
	{
		if(b & 1)(res *= a) %= mod;
		(a *= a) %= mod;b >>= 1;
	}
	return res;
}
void div(ll x)
{
	x = qpow(x,mod - 2);F[0] = w[0] * x % mod;
	for(int i = 1;i <= lenw;i++)
		F[i] = (w[i] - F[i - 1] + mod) * x % mod;
}
ll solve(ll x)
{
	a.clear();a.n = k;
	for(int i = 1;i <= k;i++)
		for(int j = 1;j <= k;j++)
			a.a[i][j] = cnt[i][j].first * x + cnt[i][j].second;
	return a.det();
}
pair <ll,ll> calc(int sx,int sy,int ex,int ey)
{
	if(sx < ex||ey < sy)return make_pair(0,0);
	ll tot = C(sx - ex + ey - sy,sx - ex);
	if(ex > r||sy > c)return {0,tot};
	if(sx < r||ey < c)return {tot,0};
	ll res = 0;
	(tot += mod - C(sx - r + c - sy,c - sy) * C(r - ex + ey - c,ey - c) % mod) %= mod;
	for(int i = ex;i < r;i++)
		(res += C(sx - i + c - sy - 1,c - sy - 1) * C(i - ex + ey - c,ey - c)) %= mod;
	return {res,(tot + mod - res) % mod};
}
int main()
{
	scanf("%d %d %d %d %d %d",&n,&m,&k,&r,&c,&v);
	if(k == 1)return puts("1"),0;
	k--;
	r += v - 1;c += v - 1;
	for(int i = 2;i <= M;i++)
		f[i] = f[i - 1] * i % mod,
		inv[i] = inv[mod % i] * (mod - mod / i) % mod,
		invf[i] = invf[i - 1] * inv[i] % mod;
	a.n = k;
	for(int i = 1;i <= k;i++)
		for(int j = 1;j <= k;j++)
			cnt[i][j] = calc(n + i,i,j,m + j);
	for(int i = 1;i <= k + 1;i++)mul(mod - i);
	for(int i = 1;i <= k + 1;i++)
	{
		div(mod - i);
		ll now = 1;
		for(int j = 1;j <= k + 1;j++)
			if(i != j)
				(now *= mod + i - j) %= mod;
		now = qpow(now,mod - 2) * solve(i) % mod; 
		for(int j = 0;j < k + 1;j++)
			(ans[j] += now * F[j]) %= mod; 
	}
	cout<<ans[v - 1];
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 15ms
memory: 6228kb

input:

148 129 48 144 105 13

output:

101253740

result:

wrong answer 1st lines differ - expected: '467058311', found: '101253740'