結果
| 問題 | No.3123 Inversion |
| コンテスト | |
| ユーザー |
 ramdos
|
| 提出日時 | 2025-12-09 22:49:54 |
| 言語 | C++17 (gcc 15.2.0 + boost 1.90.0) |
| 結果 |
AC
|
| 実行時間 | 300 ms / 10,000 ms |
| + 109µs | |
| コード長 | 4,918 bytes |
| 記録 | |
| コンパイル時間 | 1,163 ms |
| コンパイル使用メモリ | 221,428 KB |
| 実行使用メモリ | 77,696 KB |
| 最終ジャッジ日時 | 2026-07-19 08:27:49 |
| 合計ジャッジ時間 | 22,469 ms |
|
ジャッジサーバーID （参考情報） |
judge2_0 / judge1_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 21 |
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:91:5: warning: 'M' may be used uninitialized [-Wmaybe-uninitialized]
91 | if (M == 1) {
| ^~
main.cpp:83:14: note: 'M' was declared here
83 | uint32_t M;
| ^
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc@15/15.3.0/include/c++/15/x86_64-pc-linux-gnu/bits/c++allocator.h:33,
from /home/linuxbrew/.linuxbrew/Cellar/gcc@15/15.3.0/include/c++/15/bits/allocator.h:46,
from /home/linuxbrew/.linuxbrew/Cellar/gcc@15/15.3.0/include/c++/15/string:45,
from /home/linuxbrew/.linuxbrew/Cellar/gcc@15/15.3.0/include/c++/15/bitset:54,
from /home/linuxbrew/.linuxbrew/Cellar/gcc@15/15.3.0/include/c++/15/x86_64-pc-linux-gnu/bits/stdc++.h:54,
from main.cpp:5:
In member function 'void std::__new_allocator<_Tp>::construct(_Up*, _Args&& ...) [with _Up = int; _Args = {const int&}; _Tp = int]',
inlined from 'static void std::allocator_traits<std::allocator<_CharT> >::construct(allocator_type&, _Up*, _Args&& ...) [with _Up = int; _Args = {const int&}; _Tp = int]' at /home/linuxbrew/.linuxbrew/Cellar/gcc@15/15.3.0/include/c++/15/bits/alloc_traits.h:674:17,
inlined from 'void std::vector<_Tp, _Alloc>::_M_realloc_append(_Args&& ...) [with _Args = {const int&}; _Tp = int; _Alloc = std::allocator<int>]' at /home/linuxbrew/.linuxbrew/Cellar/gcc@15/15.3.0/include/c++/15/bits/vector.tcc:586:26,
inlined from 'void std::vector<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = int; _Alloc = std::allocator<int>]' at /home/linuxbrew/.linuxbrew/Cellar/gcc@15/15.3.0/include/c++/15/bits/stl_vector.h:1427:21,
inlined from 'int main()' at main.cpp:102:21:
/home/linuxbrew/.linuxbrew/Cellar/gcc@15/15.3.0/include/c++/15/bits/new_allocator.h:191:11: warning: 'N' may be used uninitialized [-Wmaybe-uninitialized]
191 | { ::new((void *)__p) _Up(std::forward<_Args>(__args)...); }
| ^~~~~~~~~~
ソースコード
// generated by GPT 5 pro
// LLMの作問能力評価のために自動生成された回答
// by CPCTF 運営チーム
#include <bits/stdc++.h>
using namespace std;
struct FastScanner {
static const size_t BUFSIZE = 1 << 20;
int idx, size;
char buf[BUFSIZE];
FastScanner() : idx(0), size(0) {}
inline char getChar() {
if (idx >= size) {
size = (int)fread(buf, 1, BUFSIZE, stdin);
idx = 0;
if (size == 0) return 0;
}
return buf[idx++];
}
template<typename T>
bool nextInt(T &out) {
char c;
T sign = 1;
T val = 0;
c = getChar();
if (!c) return false;
while (c != '-' && (c < '0' || c > '9')) {
c = getChar();
if (!c) return false;
}
if (c == '-') {
sign = -1;
c = getChar();
}
for (; c >= '0' && c <= '9'; c = getChar())
val = val * 10 + (c - '0');
out = val * sign;
return true;
}
};
struct FastWriter {
static const size_t BUFSIZE = 1 << 20;
char buf[BUFSIZE];
size_t idx;
FastWriter() : idx(0) {}
~FastWriter() { flush(); }
inline void pushChar(char c) {
if (idx >= BUFSIZE) flush();
buf[idx++] = c;
}
inline void writeUInt(uint32_t x) {
char s[16];
int n = 0;
if (x == 0) {
pushChar('0');
pushChar('\n');
return;
}
while (x) {
s[n++] = char('0' + (x % 10));
x /= 10;
}
while (n--) pushChar(s[n]);
pushChar('\n');
}
inline void flush() {
if (idx) {
fwrite(buf, 1, idx, stdout);
idx = 0;
}
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
FastScanner fs;
FastWriter fw;
int T;
uint32_t M;
if (!fs.nextInt(T)) return 0;
fs.nextInt(M);
vector<int> Ns;
Ns.reserve(T);
int maxN = 0;
if (M == 1) {
// Everything is 0 mod 1
for (int i = 0; i < T; ++i) {
int N; fs.nextInt(N);
fw.writeUInt(0);
}
return 0;
}
for (int i = 0; i < T; ++i) {
int N; fs.nextInt(N);
Ns.push_back(N);
if (N > maxN) maxN = N;
}
int maxM = maxN / 2;
// Precompute factorials up to maxN mod M
vector<uint32_t> fact(maxN + 1);
fact[0] = 1 % M;
for (int i = 1; i <= maxN; ++i) {
fact[i] = (uint64_t)fact[i - 1] * (uint64_t)i % M;
}
// Precompute involution counts A(n) up to maxN: A(0)=1, A(1)=1, A(n)=A(n-1)+(n-1)A(n-2)
vector<uint32_t> invcnt(maxN + 1);
invcnt[0] = 1 % M;
if (maxN >= 1) invcnt[1] = 1 % M;
for (int n = 2; n <= maxN; ++n) {
uint64_t term = ((uint64_t)(n - 1) * invcnt[n - 2]) % M;
uint64_t val = invcnt[n - 1] + term;
if (val >= M) val -= M;
invcnt[n] = (uint32_t)val;
}
// Precompute pow2 up to maxM
vector<uint32_t> pow2(maxM + 1);
pow2[0] = 1 % M;
for (int i = 1; i <= maxM; ++i) pow2[i] = (pow2[i - 1] << 1) % M;
// Precompute E(m): number of permutations commuting with J and involutive on 2m elements
// E(0)=1, E(1)=2, E(m)=2 E(m-1) + 2 (m-1) E(m-2)
vector<uint32_t> E(maxM + 1);
E[0] = 1 % M;
if (maxM >= 1) E[1] = 2 % M;
for (int m = 2; m <= maxM; ++m) {
uint64_t t1 = (2ULL * E[m - 1]) % M;
uint64_t t2 = (2ULL * (m - 1)) % M;
t2 = (t2 * E[m - 2]) % M;
uint64_t val = t1 + t2;
if (val >= M) val -= M;
E[m] = (uint32_t)val;
}
// Precompute FD(m): number of permutations P with P^2 = J (J has m transpositions)
// FD(0)=1, FD(1)=0, FD(m)=2 (m-1) FD(m-2)
vector<uint32_t> FD(maxM + 1);
FD[0] = 1 % M;
if (maxM >= 1) FD[1] = 0;
for (int m = 2; m <= maxM; ++m) {
uint64_t val = (2ULL * (m - 1)) % M;
val = (val * FD[m - 2]) % M;
FD[m] = (uint32_t)val;
}
for (int i = 0; i < T; ++i) {
int N = Ns[i];
if (N == 1) {
fw.writeUInt(1 % M);
continue;
}
int m = N >> 1;
uint64_t ans = 0;
// + 8 * N!
ans += (8ULL * fact[N]) % M;
if (ans >= M) ans -= M;
// - 8 * A(N)
uint64_t t = (8ULL * invcnt[N]) % M;
if (ans >= t) ans -= t;
else ans = ans + M - t;
// - 4 * (2^m * m!)
uint64_t fr2 = (uint64_t)pow2[m] * fact[m] % M;
t = (4ULL * fr2) % M;
if (ans >= t) ans -= t;
else ans = ans + M - t;
// + 6 * E(m)
t = (6ULL * E[m]) % M;
ans += t;
if (ans >= M) ans -= M;
// - 2 * FD(m)
t = (2ULL * FD[m]) % M;
if (ans >= t) ans -= t;
else ans = ans + M - t;
fw.writeUInt((uint32_t)ans);
}
fw.flush();
return 0;
}