109882024-05-02 16:43:20mraronBástyák törött sakktábláncpp17Accepted 100/100397ms128632 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;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted82ms128228 KiB
2Accepted323ms128504 KiB
subtask212/12
3Accepted86ms128248 KiB
4Accepted108ms128228 KiB
5Accepted108ms128260 KiB
6Accepted86ms128228 KiB
7Accepted108ms128228 KiB
8Accepted108ms128228 KiB
9Accepted86ms128396 KiB
10Accepted86ms128228 KiB
11Accepted86ms128228 KiB
12Accepted108ms128052 KiB
13Accepted108ms128484 KiB
14Accepted101ms128312 KiB
15Accepted86ms128080 KiB
16Accepted108ms128228 KiB
17Accepted108ms128228 KiB
18Accepted86ms128360 KiB
19Accepted86ms128364 KiB
20Accepted107ms128376 KiB
21Accepted103ms128228 KiB
subtask317/17
22Accepted108ms128228 KiB
23Accepted87ms128432 KiB
24Accepted85ms128380 KiB
25Accepted86ms128332 KiB
26Accepted108ms128296 KiB
27Accepted108ms128228 KiB
28Accepted89ms128376 KiB
29Accepted89ms128248 KiB
30Accepted108ms128140 KiB
31Accepted109ms128228 KiB
32Accepted87ms128376 KiB
33Accepted87ms128372 KiB
34Accepted82ms128228 KiB
subtask420/20
35Accepted86ms128248 KiB
36Accepted108ms128228 KiB
37Accepted108ms128260 KiB
38Accepted86ms128228 KiB
39Accepted108ms128228 KiB
40Accepted108ms128228 KiB
41Accepted86ms128396 KiB
42Accepted86ms128228 KiB
43Accepted86ms128228 KiB
44Accepted108ms128052 KiB
45Accepted108ms128484 KiB
46Accepted101ms128312 KiB
47Accepted86ms128080 KiB
48Accepted108ms128228 KiB
49Accepted108ms128228 KiB
50Accepted86ms128360 KiB
51Accepted86ms128364 KiB
52Accepted107ms128376 KiB
53Accepted103ms128228 KiB
54Accepted108ms128228 KiB
55Accepted87ms128432 KiB
56Accepted85ms128380 KiB
57Accepted86ms128332 KiB
58Accepted108ms128296 KiB
59Accepted108ms128228 KiB
60Accepted89ms128376 KiB
61Accepted89ms128248 KiB
62Accepted108ms128140 KiB
63Accepted109ms128228 KiB
64Accepted87ms128376 KiB
65Accepted87ms128372 KiB
66Accepted82ms128228 KiB
67Accepted86ms128228 KiB
68Accepted86ms128632 KiB
69Accepted90ms128496 KiB
70Accepted108ms128500 KiB
71Accepted86ms128100 KiB
72Accepted85ms128228 KiB
73Accepted85ms128360 KiB
subtask510/10
74Accepted108ms128228 KiB
75Accepted87ms128432 KiB
76Accepted85ms128380 KiB
77Accepted86ms128332 KiB
78Accepted108ms128296 KiB
79Accepted108ms128228 KiB
80Accepted89ms128376 KiB
81Accepted89ms128248 KiB
82Accepted108ms128140 KiB
83Accepted109ms128228 KiB
84Accepted87ms128376 KiB
85Accepted87ms128372 KiB
86Accepted82ms128228 KiB
87Accepted143ms128288 KiB
88Accepted150ms128200 KiB
89Accepted252ms128356 KiB
90Accepted284ms128356 KiB
91Accepted185ms128356 KiB
92Accepted268ms128356 KiB
93Accepted351ms128356 KiB
subtask641/41
94Accepted108ms128140 KiB
95Accepted328ms128504 KiB
96Accepted86ms128248 KiB
97Accepted108ms128228 KiB
98Accepted108ms128260 KiB
99Accepted86ms128228 KiB
100Accepted108ms128228 KiB
101Accepted108ms128228 KiB
102Accepted86ms128396 KiB
103Accepted86ms128228 KiB
104Accepted86ms128228 KiB
105Accepted108ms128052 KiB
106Accepted108ms128484 KiB
107Accepted101ms128312 KiB
108Accepted86ms128080 KiB
109Accepted108ms128228 KiB
110Accepted108ms128228 KiB
111Accepted86ms128360 KiB
112Accepted86ms128364 KiB
113Accepted107ms128376 KiB
114Accepted103ms128228 KiB
115Accepted108ms128228 KiB
116Accepted87ms128432 KiB
117Accepted85ms128380 KiB
118Accepted86ms128332 KiB
119Accepted108ms128296 KiB
120Accepted108ms128228 KiB
121Accepted89ms128376 KiB
122Accepted89ms128248 KiB
123Accepted108ms128140 KiB
124Accepted109ms128228 KiB
125Accepted87ms128376 KiB
126Accepted87ms128372 KiB
127Accepted82ms128228 KiB
128Accepted86ms128228 KiB
129Accepted86ms128632 KiB
130Accepted90ms128496 KiB
131Accepted108ms128500 KiB
132Accepted86ms128100 KiB
133Accepted85ms128228 KiB
134Accepted85ms128360 KiB
135Accepted143ms128288 KiB
136Accepted150ms128200 KiB
137Accepted252ms128356 KiB
138Accepted284ms128356 KiB
139Accepted185ms128356 KiB
140Accepted268ms128356 KiB
141Accepted351ms128356 KiB
142Accepted87ms128356 KiB
143Accepted114ms128412 KiB
144Accepted168ms128484 KiB
145Accepted201ms128416 KiB
146Accepted277ms128484 KiB
147Accepted289ms128356 KiB
148Accepted319ms128492 KiB
149Accepted397ms128356 KiB
150Accepted393ms128484 KiB
151Accepted330ms128484 KiB
152Accepted324ms128484 KiB