QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#396044#3082. Ascending MatrixSamponYWWA 10ms4952kbC++142.9kb2024-04-22 10:57:252024-04-22 10:57:26

Judging History

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

  • [2024-04-22 10:57:26]
  • 评测
  • 测评结果:WA
  • 用时:10ms
  • 内存:4952kb
  • [2024-04-22 10:57:25]
  • 提交

answer

#include <bits/stdc++.h>
#define db double
#define il inline
#define re register
#define ll long long
#define ui unsigned
#define ull ui ll
#define i128 __int128
#define pii pair<int, int>
#define fi first
#define se second
#define eb emplace_back
#define SZ(v) (int)v.size()
#define ALL(v) v.begin(), v.end()
#define mems(v, x) memset(v, x, sizeof(v))
#define memc(a, b) memcpy(a, b, sizeof(a))
#define FOR(i, L, R) for(re int i = (L); i <= (R); ++i)
#define ROF(i, R, L) for(re int i = (R); i >= (L); --i)
#define LS i << 1, l, mid
#define RS i << 1 | 1, mid + 1, r
#define popc(x) __builtin_popcount(x)
using namespace std;
using poly = vector<int> ;
using Fp = pair<poly, poly> ;
#define N 305
#define P 998244353
il int add(int x, int y) {return x + y < P ? x + y : x + y - P;}
il void addr(int &x, int y) {(x += y) >= P && (x -= P);}
il int qpow(int p, int n = P - 2) {
  int s = 1;
  while(n) {
    if(n & 1) s = 1ll * s * p % P;
    p = 1ll * p * p % P, n >>= 1;
  }
  return s;
}
int n, m, K, R, C, V;
bool u[N][N];
struct F {
  int k, b;
  il int v(int x) {return add(1ll * k * x % P, b);}
  il void operator += (const F &t) {addr(k, t.k), addr(b, t.b);}
  il void operator -= (const F &t) {addr(k, P - t.k), addr(b, P - t.b);}
} dp[N][N], f[N][N];
il void DP(int X, int Y) {
  mems(dp, 0), dp[X][Y] = {0, 1};
  ROF(i, X, 1) FOR(j, Y, m + K) {
    if(u[i][j]) addr(dp[i][j].k, dp[i][j].b), dp[i][j].b = 0;
    if(i == R + V - 1 && j == C + V - 1) dp[i][j] = {0, 0};
    if(i > 1) dp[i - 1][j] += dp[i][j]; if(j < m + K) dp[i][j + 1] += dp[i][j];
  }
}
int v[N][N], w[N];
il int det() {
  int s = 1;
  FOR(i, 1, K) {
    int t = i;
    FOR(j, i, K) if(v[j][i]) {t = j; break;}
    if(i != t) swap(v[i], v[t]), s = -s;
    int inv = qpow(v[i][i]);
    FOR(j, i + 1, K) {
      int c = 1ll * v[j][i] * inv % P;
      FOR(k, i, K) addr(v[j][k], P - 1ll * c * v[i][k] % P);
    }
  }
  FOR(i, 1, K) s = 1ll * s * v[i][i] % P;
  return (s + P) % P;
}
il void gauss() {
  FOR(i, 0, K) {
    int t = i;
    FOR(j, i, K) if(v[j][i]) {t = j; break;}
    if(i != t) swap(v[i], v[t]);
    int inv = qpow(v[i][i]);
    FOR(j, 0, K) if(i != j) {
      int c = 1ll * v[j][i] * inv % P;
      FOR(k, i, K + 1) addr(v[j][k], P - 1ll * c * v[i][k] % P);
    }
  }
  FOR(i, 0, K) w[i] = 1ll * v[i][K + 1] * qpow(v[i][i]) % P;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> n >> m >> K >> R >> C >> V, --K;
  FOR(i, 1, R + V - 1) FOR(j, 1, C + V - 1) u[i][j] = 1;
  FOR(i, 1, K) {DP(i + n, i); FOR(j, 1, K) f[i][j] = dp[j][j + m];}
  FOR(x, 1, K) {FOR(i, 1, K) FOR(j, 1, K) v[i][j] = f[i][j].v(x); w[x] = det();}
  FOR(x, 0, K) {
    int c = 1;
    FOR(i, 0, K) v[x][i] = c, c = 1ll * c * x % P;
    v[x][K + 1] = w[x];
  }
  gauss(), cout << w[V - 1];
  cerr << 1.0 * clock() / CLOCKS_PER_SEC;
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 10ms
memory: 4952kb

input:

148 129 48 144 105 13

output:

467058311

result:

ok single line: '467058311'

Test #2:

score: -100
Wrong Answer
time: 1ms
memory: 4748kb

input:

57 48 11 56 9 1

output:

0

result:

wrong answer 1st lines differ - expected: '951177245', found: '0'