QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#474030 | #3082. Ascending Matrix | BINYU | WA | 15ms | 6228kb | C++14 | 2.9kb | 2024-07-12 15:38:21 | 2024-07-12 15:38:21 |
Judging History
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'