intqpow(int a, int k){ int res = 1; while (k) { if (k & 1) res = (longlong)res * a % kMod; k >>= 1; a = (longlong)a * a % kMod; } return res; }
voidprepare(){ fac[0] = 1; for (longlong i = 1; i <= 100000; i++) { fac[i] = fac[i - 1] * i % kMod; inv[i] = qpow(fac[i], kMod - 2); } inv[0] = inv[1]; }
int a[kN];
inlineintA(int m, int n){ return1LL * fac[m] * inv[m - n] % kMod; }
inlinevoidwork(){ int n; scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", a + i); pos[a[i]] = i; } int l, r; l = r = pos[0]; int x = 1; int fixed = 1; int in = 0; int ans = 1; while (x <= n) { if (x == n) { // 计算之前的区间的方案数 ans = 1LL * ans * A(r - l + 1 - fixed, in) % kMod; break; } int p = pos[x]; if (p >= l && p <= r) { in++; x++; continue; } // 计算之前的区间的方案数 ans = 1LL * ans * A(r - l + 1 - fixed, in) % kMod; if (p < l) l = p; elseif (p > r) r = p; fixed += in + 1; in = 0; x++; } printf("%d\n", ans); }
intmain(){ prepare(); int t; scanf("%d", &t); while (t--) work(); return0; }
bool exist[kM]; int maxfac[kM]; int cntmaxfac[kM];
inlinevoidwork(){ int n, m, mi = kM, ma = -1; scanf("%d%d", &n, &m); memset(exist, 0, sizeof(bool) * (m + 1)); memset(cntmaxfac, 0, sizeof(int) * (m + 1)); for (int i = 1, v; i <= n; i++) { scanf("%d", &v); if (v > ma) { ma = v; } if (v < mi) { mi = v; } exist[v] = true; } for (int v = 1; v <= ma; v++) { maxfac[v] = v; if (exist[v]) cntmaxfac[v]++; } int p = ma; int ans = ma - mi; for (int l = ma; l > 0; l--) { if (1LL * l * l <= ma) { for (int v = l * l; v <= ma; v += l) { if (exist[v]) cntmaxfac[maxfac[v]]--; int pre = maxfac[v / l]; if (pre < maxfac[v]) maxfac[v] = pre; if (exist[v]) cntmaxfac[maxfac[v]]++; } } while (!cntmaxfac[p]) p--; int now = p - mi; if (l <= mi) { now = p - l; } if (now < ans) ans = now; } printf("%d\n", ans); }
intmain(){ int t; scanf("%d", &t); while (t--) work(); return0; }