10988 | 2024-05-02 16:43:20 | mraron | Bástyák törött sakktáblán | cpp17 | Accepted 100/100 | 397ms | 128632 KiB |
#include<bits/stdc++.h>
using namespace std;
template<int m>
struct modular {
int64_t r;
modular() : r(0) {}
modular(int64_t rr) : r(rr) {if(abs(r) >= m) r %= m; if(r < 0) r += m;}
modular inv() const {return bpow(*this, m - 2);}
modular operator * (const modular &t) const {return (r * t.r) % m;}
modular operator / (const modular &t) const {return *this * t.inv();}
modular operator += (const modular &t) {r += t.r; if(r >= m) r -= m; return *this;}
modular operator -= (const modular &t) {r -= t.r; if(r < 0) r += m; return *this;}
modular operator + (const modular &t) const {return modular(*this) += t;}
modular operator - (const modular &t) const {return modular(*this) -= t;}
modular operator *= (const modular &t) {return *this = *this * t;}
modular operator /= (const modular &t) {return *this = *this / t;}
bool operator == (const modular &t) const {return r == t.r;}
bool operator != (const modular &t) const {return r != t.r;}
operator int64_t() const {return r;}
int64_t bpow(int64_t a, int64_t b) const {
int64_t res=1;
while(b) {
if(b&1) res=(res*a)%m;
a=(a*a)%m;
b/=2;
}
return res;
}
};
using Mint = modular<(int)1e9+7>;
int n;
int m;
vector<int> a;
vector<int> b;
pair<Mint, bool> dp[2][2021][2021];
Mint calc1(int row, int need) {
if(need==0) return 1;
if(row<0) return 0;
if(row==0) {
if(need==1) return a[0];
return 0;
}
if(dp[0][row][need].second) return dp[0][row][need].first;
Mint uj=a[row]-a[row-1];
dp[0][row][need]={calc1(row-1, need)+calc1(row-1, need-1)*(uj+Mint(a[row-1]-need+1)), true};
return dp[0][row][need].first;
}
Mint calc2(int col, int need) {
if(need==0) return 1;
if(col>m) return 0;
if(col==m) {
if(need==1) return b[m];
return 0;
}
if(dp[1][col][need].second) return dp[1][col][need].first;
Mint uj=b[col]-b[col+1];
dp[1][col][need]={calc2(col+1, need)+calc2(col+1, need-1)*(uj+Mint(b[col+1]-need+1)), true};
return dp[1][col][need].first;
}
int main() {
cin>>n;
a.resize(n);
for(int& i:a) cin>>i;
m=*max_element(a.begin(), a.end());
b.resize(m+1);
for(int i=0;i<n;++i) {
b[1]++;
if(a[i]+1<=m) b[a[i]+1]--;
}
for(int i=1;i<=m;++i) b[i]+=b[i-1];
vector<Mint> fact(m+1);
fact[0]=1;
for(int i=1;i<=m;++i) fact[i]=fact[i-1]*Mint(i);
Mint ans=1;
for(int i=0;i<n;++i) {
ans*=a[i]-i;
}
for(int i=0;i<n;++i) {
for(int j=0;j<=(!i?0:a[i-1]);++j) {
int rem_cols=a[i]-j;
int rem_rows=n-i-1;
if(rem_cols<=rem_rows) {
int need=rem_rows-rem_cols;
ans+=calc1(i-1, j)*calc2(a[i]+1,need)*fact[rem_cols];
}
}
}
cout<<ans<<"\n";
return 0;
}
Subtask | Sum | Test | Verdict | Time | Memory | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Accepted | 82ms | 128228 KiB | ||||
2 | Accepted | 323ms | 128504 KiB | ||||
subtask2 | 12/12 | ||||||
3 | Accepted | 86ms | 128248 KiB | ||||
4 | Accepted | 108ms | 128228 KiB | ||||
5 | Accepted | 108ms | 128260 KiB | ||||
6 | Accepted | 86ms | 128228 KiB | ||||
7 | Accepted | 108ms | 128228 KiB | ||||
8 | Accepted | 108ms | 128228 KiB | ||||
9 | Accepted | 86ms | 128396 KiB | ||||
10 | Accepted | 86ms | 128228 KiB | ||||
11 | Accepted | 86ms | 128228 KiB | ||||
12 | Accepted | 108ms | 128052 KiB | ||||
13 | Accepted | 108ms | 128484 KiB | ||||
14 | Accepted | 101ms | 128312 KiB | ||||
15 | Accepted | 86ms | 128080 KiB | ||||
16 | Accepted | 108ms | 128228 KiB | ||||
17 | Accepted | 108ms | 128228 KiB | ||||
18 | Accepted | 86ms | 128360 KiB | ||||
19 | Accepted | 86ms | 128364 KiB | ||||
20 | Accepted | 107ms | 128376 KiB | ||||
21 | Accepted | 103ms | 128228 KiB | ||||
subtask3 | 17/17 | ||||||
22 | Accepted | 108ms | 128228 KiB | ||||
23 | Accepted | 87ms | 128432 KiB | ||||
24 | Accepted | 85ms | 128380 KiB | ||||
25 | Accepted | 86ms | 128332 KiB | ||||
26 | Accepted | 108ms | 128296 KiB | ||||
27 | Accepted | 108ms | 128228 KiB | ||||
28 | Accepted | 89ms | 128376 KiB | ||||
29 | Accepted | 89ms | 128248 KiB | ||||
30 | Accepted | 108ms | 128140 KiB | ||||
31 | Accepted | 109ms | 128228 KiB | ||||
32 | Accepted | 87ms | 128376 KiB | ||||
33 | Accepted | 87ms | 128372 KiB | ||||
34 | Accepted | 82ms | 128228 KiB | ||||
subtask4 | 20/20 | ||||||
35 | Accepted | 86ms | 128248 KiB | ||||
36 | Accepted | 108ms | 128228 KiB | ||||
37 | Accepted | 108ms | 128260 KiB | ||||
38 | Accepted | 86ms | 128228 KiB | ||||
39 | Accepted | 108ms | 128228 KiB | ||||
40 | Accepted | 108ms | 128228 KiB | ||||
41 | Accepted | 86ms | 128396 KiB | ||||
42 | Accepted | 86ms | 128228 KiB | ||||
43 | Accepted | 86ms | 128228 KiB | ||||
44 | Accepted | 108ms | 128052 KiB | ||||
45 | Accepted | 108ms | 128484 KiB | ||||
46 | Accepted | 101ms | 128312 KiB | ||||
47 | Accepted | 86ms | 128080 KiB | ||||
48 | Accepted | 108ms | 128228 KiB | ||||
49 | Accepted | 108ms | 128228 KiB | ||||
50 | Accepted | 86ms | 128360 KiB | ||||
51 | Accepted | 86ms | 128364 KiB | ||||
52 | Accepted | 107ms | 128376 KiB | ||||
53 | Accepted | 103ms | 128228 KiB | ||||
54 | Accepted | 108ms | 128228 KiB | ||||
55 | Accepted | 87ms | 128432 KiB | ||||
56 | Accepted | 85ms | 128380 KiB | ||||
57 | Accepted | 86ms | 128332 KiB | ||||
58 | Accepted | 108ms | 128296 KiB | ||||
59 | Accepted | 108ms | 128228 KiB | ||||
60 | Accepted | 89ms | 128376 KiB | ||||
61 | Accepted | 89ms | 128248 KiB | ||||
62 | Accepted | 108ms | 128140 KiB | ||||
63 | Accepted | 109ms | 128228 KiB | ||||
64 | Accepted | 87ms | 128376 KiB | ||||
65 | Accepted | 87ms | 128372 KiB | ||||
66 | Accepted | 82ms | 128228 KiB | ||||
67 | Accepted | 86ms | 128228 KiB | ||||
68 | Accepted | 86ms | 128632 KiB | ||||
69 | Accepted | 90ms | 128496 KiB | ||||
70 | Accepted | 108ms | 128500 KiB | ||||
71 | Accepted | 86ms | 128100 KiB | ||||
72 | Accepted | 85ms | 128228 KiB | ||||
73 | Accepted | 85ms | 128360 KiB | ||||
subtask5 | 10/10 | ||||||
74 | Accepted | 108ms | 128228 KiB | ||||
75 | Accepted | 87ms | 128432 KiB | ||||
76 | Accepted | 85ms | 128380 KiB | ||||
77 | Accepted | 86ms | 128332 KiB | ||||
78 | Accepted | 108ms | 128296 KiB | ||||
79 | Accepted | 108ms | 128228 KiB | ||||
80 | Accepted | 89ms | 128376 KiB | ||||
81 | Accepted | 89ms | 128248 KiB | ||||
82 | Accepted | 108ms | 128140 KiB | ||||
83 | Accepted | 109ms | 128228 KiB | ||||
84 | Accepted | 87ms | 128376 KiB | ||||
85 | Accepted | 87ms | 128372 KiB | ||||
86 | Accepted | 82ms | 128228 KiB | ||||
87 | Accepted | 143ms | 128288 KiB | ||||
88 | Accepted | 150ms | 128200 KiB | ||||
89 | Accepted | 252ms | 128356 KiB | ||||
90 | Accepted | 284ms | 128356 KiB | ||||
91 | Accepted | 185ms | 128356 KiB | ||||
92 | Accepted | 268ms | 128356 KiB | ||||
93 | Accepted | 351ms | 128356 KiB | ||||
subtask6 | 41/41 | ||||||
94 | Accepted | 108ms | 128140 KiB | ||||
95 | Accepted | 328ms | 128504 KiB | ||||
96 | Accepted | 86ms | 128248 KiB | ||||
97 | Accepted | 108ms | 128228 KiB | ||||
98 | Accepted | 108ms | 128260 KiB | ||||
99 | Accepted | 86ms | 128228 KiB | ||||
100 | Accepted | 108ms | 128228 KiB | ||||
101 | Accepted | 108ms | 128228 KiB | ||||
102 | Accepted | 86ms | 128396 KiB | ||||
103 | Accepted | 86ms | 128228 KiB | ||||
104 | Accepted | 86ms | 128228 KiB | ||||
105 | Accepted | 108ms | 128052 KiB | ||||
106 | Accepted | 108ms | 128484 KiB | ||||
107 | Accepted | 101ms | 128312 KiB | ||||
108 | Accepted | 86ms | 128080 KiB | ||||
109 | Accepted | 108ms | 128228 KiB | ||||
110 | Accepted | 108ms | 128228 KiB | ||||
111 | Accepted | 86ms | 128360 KiB | ||||
112 | Accepted | 86ms | 128364 KiB | ||||
113 | Accepted | 107ms | 128376 KiB | ||||
114 | Accepted | 103ms | 128228 KiB | ||||
115 | Accepted | 108ms | 128228 KiB | ||||
116 | Accepted | 87ms | 128432 KiB | ||||
117 | Accepted | 85ms | 128380 KiB | ||||
118 | Accepted | 86ms | 128332 KiB | ||||
119 | Accepted | 108ms | 128296 KiB | ||||
120 | Accepted | 108ms | 128228 KiB | ||||
121 | Accepted | 89ms | 128376 KiB | ||||
122 | Accepted | 89ms | 128248 KiB | ||||
123 | Accepted | 108ms | 128140 KiB | ||||
124 | Accepted | 109ms | 128228 KiB | ||||
125 | Accepted | 87ms | 128376 KiB | ||||
126 | Accepted | 87ms | 128372 KiB | ||||
127 | Accepted | 82ms | 128228 KiB | ||||
128 | Accepted | 86ms | 128228 KiB | ||||
129 | Accepted | 86ms | 128632 KiB | ||||
130 | Accepted | 90ms | 128496 KiB | ||||
131 | Accepted | 108ms | 128500 KiB | ||||
132 | Accepted | 86ms | 128100 KiB | ||||
133 | Accepted | 85ms | 128228 KiB | ||||
134 | Accepted | 85ms | 128360 KiB | ||||
135 | Accepted | 143ms | 128288 KiB | ||||
136 | Accepted | 150ms | 128200 KiB | ||||
137 | Accepted | 252ms | 128356 KiB | ||||
138 | Accepted | 284ms | 128356 KiB | ||||
139 | Accepted | 185ms | 128356 KiB | ||||
140 | Accepted | 268ms | 128356 KiB | ||||
141 | Accepted | 351ms | 128356 KiB | ||||
142 | Accepted | 87ms | 128356 KiB | ||||
143 | Accepted | 114ms | 128412 KiB | ||||
144 | Accepted | 168ms | 128484 KiB | ||||
145 | Accepted | 201ms | 128416 KiB | ||||
146 | Accepted | 277ms | 128484 KiB | ||||
147 | Accepted | 289ms | 128356 KiB | ||||
148 | Accepted | 319ms | 128492 KiB | ||||
149 | Accepted | 397ms | 128356 KiB | ||||
150 | Accepted | 393ms | 128484 KiB | ||||
151 | Accepted | 330ms | 128484 KiB | ||||
152 | Accepted | 324ms | 128484 KiB |