UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#203192#3546. countyllcm1007730ms111804kbC++3.6kb2024-02-20 11:10:372024-02-20 13:44:49

answer

#include<bits/stdc++.h>
#define ll long long
#define db double
#define ull unsigned long long
#define pb push_back
#define pii pair<int, int>
#define FR first
#define SE second
using namespace std;
inline int read() {
  int x = 0; bool op = false;
  char c = getchar();
  while(!isdigit(c))op |= (c == '-'), c = getchar();
  while(isdigit(c))x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
  return op ? -x : x;
}
const int N = 1e7 + 10;
const int P = 998244353;
void add(int &a, int b) {a += b; a >= P ? a -= P : 0;}
void sub(int &a, int b) {a -= b; a < 0 ? a += P : 0;}
int ksm(int x, int k) {
  int res = 1;
  for(int pw = x; k; (k & 1) ? res = 1ll * res * pw % P : 0, pw = 1ll * pw * pw % P, k >>= 1);
  return res;
}
int fac[N], ifac[N], pw[N], ipw[N];
void init() {
  fac[0] = ifac[0] = 1;
  for(int i = 1; i < N; i++)fac[i] = 1ll * fac[i - 1] * i % P;
  ifac[N - 1] = ksm(fac[N - 1], P - 2);
  for(int i = N - 2; i; i--)ifac[i] = 1ll * ifac[i + 1] * (i + 1) % P;
  for(int i = 1; i < N; i <<= 1)pw[i] = ksm(3, (P - 1) / i);
  for(int i = 1; i < N; i <<= 1)ipw[i] = ksm(pw[i], P - 2);
  return ;
}
int com(int n, int m) {return n < m || m < 0 ? 0 : 1ll * fac[n] * ifac[m] % P * ifac[n - m] % P;}
int n, m, x;
int pre[N], suf[N], f[N], g[N], h[N], rev[N];
void NTT(int *f, int len, int op) {
  for(int i = 0; i < len; i++)rev[i] = (rev[i >> 1] >> 1) | ((i & 1) * (len >> 1));
  for(int i = 0; i < len; i++)if(i < rev[i])swap(f[i], f[rev[i]]);
  for(int k = 1; k < len; k <<= 1) {
    for(int i = 0; i < len; i += k + k) {
      int gn = (op == 1 ? pw[k + k] : ipw[k + k]), g = 1;
      for(int j = 0; j < k; j++, g = 1ll * g * gn % P) {
        int x = f[i + j], y = 1ll * g * f[i + j + k] % P;
        f[i + j] = (x + y) % P;
        f[i + j + k] = (x - y + P) % P;
      }
    }
  }
  if(op == -1) {
    int inv = ksm(len, P - 2);
    for(int i = 0; i < len; i++)f[i] = 1ll * f[i] * inv % P;
  }
  return ;
}
int main() {
  init();
  n = read(); m = read(); x = read();
  int ans = 0;
  suf[n + 1] = suf[n + 2] = 1;
  for(int i = n; i; i--)suf[i] = 1ll * suf[i + 1] * (n - (i - 1)) % P;
  for(int i = 1; i < x; i++)f[i] = 1ll * (i - 1) * fac[n - i - 1] % P;
  for(int i = 0; i <= n; i++)g[i] = ifac[i];
  int ln = 1;
  while(ln < (n + n + 5))ln <<= 1;
  NTT(f, ln, 1); NTT(g, ln, 1);
  for(int i = 0; i < ln; i++)f[i] = 1ll * f[i] * g[i] % P;
  NTT(f, ln, -1);
  // for(int i = 0; i < ln; i++)cout << f[i] << ' '; cout << endl;
  for(int r = 1; r < n; r++) {
    int res = com(r - 1 + m, m + 1);
    res = 1ll * res * suf[r + 2] % P;
    res = 1ll * res * f[n - r + 1] % P;
    add(ans, res);
  }
  if(x > 1) {
    int res = com(n - 1 + m, m + 1);
    res = 1ll * res * fac[n - 2] % P;
    add(ans, res);
  }
  for(int i = 0; i < ln; i++)f[i] = g[i] = 0;
  for(int i = 1; i < x; i++)f[i] = fac[n - i + 1];
  for(int i = 1; i <= n; i++)g[i] = ifac[i];
  // for(int v = 1; v < x; v++) {
  //   pre[1] = 1;
  //   for(int i = 2; i <= n; i++)pre[i] = 1ll * pre[i - 1] * (n - v - (i - 1)) % P;
  //   for(int r = 1; r <= n; r++) {
  //     int res = com(r - 1 + m, m + 1);
  //     res = 1ll * res * pre[r - 1] % P;
  //     res = 1ll * res * suf[r + 2] % P;
  //     if(r < n)res = 1ll * res * (v - 1) % P;
  //     add(ans, res);
  //   }
  // }
  pre[1] = 1;
  for(int i = 2; i <= n; i++)pre[i] = 1ll * pre[i - 1] * (n - x + 1 - (i - 1)) % P;
  for(int r = 1; r <= n; r++) {
    int res = com(r - 1 + m, m);
    res = 1ll * res * pre[r] % P;
    if(r < n)res = 1ll * res * (x - 1) % P;
    res = 1ll * res * suf[r + 2] % P;
    add(ans, res);
  }
  printf("%d\n", ans); 
  return 0;
}

Details

小提示:点击横条可展开更详细的信息

Test #1:

score: 5
Accepted
time: 112ms
memory: 79412kb

input:

7 3 7

output:

20640

result:

ok single line: '20640'

Test #2:

score: 5
Accepted
time: 108ms
memory: 79412kb

input:

7 2 6

output:

10560

result:

ok single line: '10560'

Test #3:

score: 5
Accepted
time: 120ms
memory: 79420kb

input:

178 88 176

output:

263756452

result:

ok single line: '263756452'

Test #4:

score: 5
Accepted
time: 131ms
memory: 79416kb

input:

165 64 151

output:

675678116

result:

ok single line: '675678116'

Test #5:

score: 5
Accepted
time: 133ms
memory: 79420kb

input:

188 83 184

output:

69478022

result:

ok single line: '69478022'

Test #6:

score: 5
Accepted
time: 102ms
memory: 79420kb

input:

158 62 144

output:

203749473

result:

ok single line: '203749473'

Test #7:

score: 5
Accepted
time: 128ms
memory: 79476kb

input:

1974 459 1845

output:

535987457

result:

ok single line: '535987457'

Test #8:

score: 5
Accepted
time: 137ms
memory: 79480kb

input:

1970 499 1944

output:

118089661

result:

ok single line: '118089661'

Test #9:

score: 5
Accepted
time: 137ms
memory: 79476kb

input:

1962 195 1766

output:

563043519

result:

ok single line: '563043519'

Test #10:

score: 5
Accepted
time: 134ms
memory: 79476kb

input:

1957 408 1858

output:

368025374

result:

ok single line: '368025374'

Test #11:

score: 5
Accepted
time: 679ms
memory: 111804kb

input:

999966 2907 1

output:

891313743

result:

ok single line: '891313743'

Test #12:

score: 5
Accepted
time: 651ms
memory: 111800kb

input:

999997 4828 2

output:

815004193

result:

ok single line: '815004193'

Test #13:

score: 5
Accepted
time: 656ms
memory: 111804kb

input:

999959 5271 2

output:

600125008

result:

ok single line: '600125008'

Test #14:

score: 5
Accepted
time: 632ms
memory: 111800kb

input:

999961 24134 10

output:

784444417

result:

ok single line: '784444417'

Test #15:

score: 5
Accepted
time: 636ms
memory: 111800kb

input:

999983 33966 10

output:

744109998

result:

ok single line: '744109998'

Test #16:

score: 5
Accepted
time: 658ms
memory: 111804kb

input:

999951 31503 999934

output:

518818294

result:

ok single line: '518818294'

Test #17:

score: 5
Accepted
time: 636ms
memory: 111804kb

input:

999953 21775 999941

output:

459927485

result:

ok single line: '459927485'

Test #18:

score: 5
Accepted
time: 636ms
memory: 111800kb

input:

999970 7889 999782

output:

979137112

result:

ok single line: '979137112'

Test #19:

score: 5
Accepted
time: 641ms
memory: 111804kb

input:

999972 6809 999964

output:

64469239

result:

ok single line: '64469239'

Test #20:

score: 5
Accepted
time: 663ms
memory: 111804kb

input:

999952 29898 999948

output:

801924273

result:

ok single line: '801924273'

Extra Test:

score: 0
Extra Test Passed