QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#577685 | #9353. Interesting Permutation | plutos | AC ✓ | 336ms | 7116kb | C++17 | 4.3kb | 2024-09-20 14:04:06 | 2024-09-20 14:04:07 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;
template<long long P>
struct ModInt {
public:
ModInt() : v(0) {}
template<typename T>
ModInt(T x) { v = ((long long) x % P + P) % P; }
long long val() const { return v; }
ModInt &operator++() {
++v;
if (v == P)
v = 0;
return *this;
}
ModInt &operator--() {
if (v == 0)
v = P;
--v;
return *this;
}
ModInt operator++(int) {
ModInt oldVal = *this;
++*this;
return oldVal;
}
ModInt operator--(int) {
ModInt oldVal = *this;
--*this;
return oldVal;
}
ModInt &operator+=(const ModInt &rhs) {
v += rhs.v;
v %= P;
return *this;
}
ModInt &operator-=(const ModInt &rhs) {
v -= rhs.v;
v = (v + P) % P;
return *this;
}
ModInt &operator*=(const ModInt &rhs) {
v *= rhs.v;
v %= P;
return *this;
}
ModInt &operator/=(const ModInt &rhs) { return *this = *this * rhs.inv(); }
ModInt operator+() const { return *this; }
ModInt operator-() const { return ModInt() - *this; }
ModInt pow(long long exp) const {
// assert(exp>=0);
ModInt res = 1;
ModInt base = *this;
while (exp) {
if (exp & 1)
res *= base;
base *= base;
exp >>= 1;
}
return res;
}
ModInt inv() const {
// assert(v);
return pow(P - 2);
}
friend ModInt operator+(const ModInt &lhs, const ModInt &rhs) {
ModInt res = lhs;
res += rhs;
return res;
}
friend ModInt operator-(const ModInt &lhs, const ModInt &rhs) {
ModInt res = lhs;
res -= rhs;
return res;
}
friend ModInt operator*(const ModInt &lhs, const ModInt &rhs) {
ModInt res = lhs;
res *= rhs;
return res;
}
friend ModInt operator/(const ModInt &lhs, const ModInt &rhs) {
ModInt res = lhs;
res /= rhs;
return res;
}
friend bool operator==(const ModInt &lhs, const ModInt &rhs) { return lhs.v == rhs.v; }
friend bool operator!=(const ModInt &lhs, const ModInt &rhs) { return lhs.v != rhs.v; }
friend std::istream &operator>>(std::istream &is, ModInt &aim) {
long long tmp;
is >> tmp;
aim = ModInt(tmp);
return is;
}
friend std::ostream &operator<<(std::ostream &os, const ModInt &aim) { return os << aim.val(); }
private:
long long v;
};
using mint = ModInt<MOD>;
mint fact[200005];
mint infact[200005];
void init() {
infact[0] = fact[0] = 1;
for (int i = 1; i <= 100002; i++)
fact[i] = fact[i - 1] * i, infact[i] = infact[i - 1] / i;
}
mint C(int a, int b) {
if (a < b || a < 0 || b < 0) return 0;
return fact[a] * infact[b] * infact[a - b];
}
int a[100005];
void Solve() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for(int i = 2; i <= n ;i++) {
if(a[i] > n-1 || a[i] < i-1) {
cout<<0<<"\n";
return;
}
if(a[i] < a[i-1]){
cout<<0<<"\n";
return;
}
}
if (a[1] != 0 || a[n] != n - 1) {
cout<<0<<"\n";
return;
}
if (n == 1) {
cout<<1<<"\n";
return;
}
if (n == 2) {
cout<<2<<"\n";
return;
}
mint ans = 2;
int rem = 0;
for (int i = 2; i <= n; i++) {
if(a[i] != n-1)
ans *= 2;
int num = 0;
int ti = i;
int nexti = i;
for(int j = i + 1; j <= n ; j++ ) {
if(a[j] == a[i])
num++ , nexti = j;
else {
nexti = j - 1;
break;
}
}
i = nexti;
rem += (a[ti] - a[ti-1] - 1) ;
ans *= fact[num];
ans *= C(rem,num);
rem -=num;
// cout<<rem<<" "<<num<<"\n";
// cout<<ti<<" "<<ans<<"\n";
}
cout<<ans<<"\n";
}
int main() {
init();
int t;
cin >> t;
while(t--) {
Solve();
}
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 8ms
memory: 6816kb
input:
3 3 0 2 2 3 0 1 2 3 0 2 3
output:
2 4 0
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 222ms
memory: 7116kb
input:
10039 14 5 6 7 8 9 10 11 12 13 13 13 13 13 13 14 0 5 6 7 8 9 10 11 12 13 14 14 14 14 1 1 14 0 5 4 8 9 10 11 12 13 13 13 13 13 13 45 0 1 1 2 2 3 5 5 6 6 8 9 11 13 15 17 18 18 20 22 22 24 26 26 26 26 27 27 27 28 30 32 32 33 34 34 34 36 36 38 38 38 39 39 44 24 0 2 3 5 7 9 9 10 11 12 13 14 14 14 14 15 1...
output:
0 0 0 0 0 0 24576 0 0 0 0 0 658159182 0 805306368 8 572589350 12288 2 0 981283070 0 0 2 0 0 0 0 4423680 0 0 14155776 16 0 768 0 0 0 855189487 0 2 0 0 0 0 2 0 2 797370259 0 0 0 0 4 0 0 0 301989888 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 192 0 0 12288 0 0 2 8 0 0 495514526 0 0 955131071 768 0 0 147456 0 0...
result:
ok 10039 lines
Test #3:
score: 0
Accepted
time: 336ms
memory: 7084kb
input:
20 100000 0 1 2 3 5 6 7 9 10 10 12 12 12 13 14 15 17 17 18 19 21 22 24 26 28 28 28 28 29 31 32 34 35 36 38 39 39 39 41 41 42 44 45 47 48 49 51 53 54 56 58 58 58 60 62 62 64 64 64 66 66 66 66 68 70 70 71 72 72 74 74 75 76 77 77 78 80 80 82 82 84 85 86 86 88 88 89 90 91 91 93 93 95 97 98 100 101 103 1...
output:
202795881 940225306 406525679 536765675 729062616 366047380 66289678 199278830 570456350 993317415 17778389 674797620 787821942 841428534 632185280 579006079 822641126 664256526 482813708 821188194
result:
ok 20 lines
Test #4:
score: 0
Accepted
time: 8ms
memory: 6728kb
input:
1 14 5 6 7 8 9 10 11 12 13 13 13 13 13 13
output:
0
result:
ok single line: '0'
Test #5:
score: 0
Accepted
time: 12ms
memory: 6764kb
input:
1 14 0 5 6 7 8 9 10 11 12 13 14 14 14 14
output:
0
result:
ok single line: '0'
Test #6:
score: 0
Accepted
time: 12ms
memory: 6732kb
input:
1 1 1
output:
0
result:
ok single line: '0'
Test #7:
score: 0
Accepted
time: 5ms
memory: 6820kb
input:
1 14 0 5 4 8 9 10 11 12 13 13 13 13 13 13
output:
0
result:
ok single line: '0'
Extra Test:
score: 0
Extra Test Passed