109882024-05-02 16:43:20mraronBástyák törött sakktábláncpp17Elfogadva 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva82ms128228 KiB
2Elfogadva323ms128504 KiB
subtask212/12
3Elfogadva86ms128248 KiB
4Elfogadva108ms128228 KiB
5Elfogadva108ms128260 KiB
6Elfogadva86ms128228 KiB
7Elfogadva108ms128228 KiB
8Elfogadva108ms128228 KiB
9Elfogadva86ms128396 KiB
10Elfogadva86ms128228 KiB
11Elfogadva86ms128228 KiB
12Elfogadva108ms128052 KiB
13Elfogadva108ms128484 KiB
14Elfogadva101ms128312 KiB
15Elfogadva86ms128080 KiB
16Elfogadva108ms128228 KiB
17Elfogadva108ms128228 KiB
18Elfogadva86ms128360 KiB
19Elfogadva86ms128364 KiB
20Elfogadva107ms128376 KiB
21Elfogadva103ms128228 KiB
subtask317/17
22Elfogadva108ms128228 KiB
23Elfogadva87ms128432 KiB
24Elfogadva85ms128380 KiB
25Elfogadva86ms128332 KiB
26Elfogadva108ms128296 KiB
27Elfogadva108ms128228 KiB
28Elfogadva89ms128376 KiB
29Elfogadva89ms128248 KiB
30Elfogadva108ms128140 KiB
31Elfogadva109ms128228 KiB
32Elfogadva87ms128376 KiB
33Elfogadva87ms128372 KiB
34Elfogadva82ms128228 KiB
subtask420/20
35Elfogadva86ms128248 KiB
36Elfogadva108ms128228 KiB
37Elfogadva108ms128260 KiB
38Elfogadva86ms128228 KiB
39Elfogadva108ms128228 KiB
40Elfogadva108ms128228 KiB
41Elfogadva86ms128396 KiB
42Elfogadva86ms128228 KiB
43Elfogadva86ms128228 KiB
44Elfogadva108ms128052 KiB
45Elfogadva108ms128484 KiB
46Elfogadva101ms128312 KiB
47Elfogadva86ms128080 KiB
48Elfogadva108ms128228 KiB
49Elfogadva108ms128228 KiB
50Elfogadva86ms128360 KiB
51Elfogadva86ms128364 KiB
52Elfogadva107ms128376 KiB
53Elfogadva103ms128228 KiB
54Elfogadva108ms128228 KiB
55Elfogadva87ms128432 KiB
56Elfogadva85ms128380 KiB
57Elfogadva86ms128332 KiB
58Elfogadva108ms128296 KiB
59Elfogadva108ms128228 KiB
60Elfogadva89ms128376 KiB
61Elfogadva89ms128248 KiB
62Elfogadva108ms128140 KiB
63Elfogadva109ms128228 KiB
64Elfogadva87ms128376 KiB
65Elfogadva87ms128372 KiB
66Elfogadva82ms128228 KiB
67Elfogadva86ms128228 KiB
68Elfogadva86ms128632 KiB
69Elfogadva90ms128496 KiB
70Elfogadva108ms128500 KiB
71Elfogadva86ms128100 KiB
72Elfogadva85ms128228 KiB
73Elfogadva85ms128360 KiB
subtask510/10
74Elfogadva108ms128228 KiB
75Elfogadva87ms128432 KiB
76Elfogadva85ms128380 KiB
77Elfogadva86ms128332 KiB
78Elfogadva108ms128296 KiB
79Elfogadva108ms128228 KiB
80Elfogadva89ms128376 KiB
81Elfogadva89ms128248 KiB
82Elfogadva108ms128140 KiB
83Elfogadva109ms128228 KiB
84Elfogadva87ms128376 KiB
85Elfogadva87ms128372 KiB
86Elfogadva82ms128228 KiB
87Elfogadva143ms128288 KiB
88Elfogadva150ms128200 KiB
89Elfogadva252ms128356 KiB
90Elfogadva284ms128356 KiB
91Elfogadva185ms128356 KiB
92Elfogadva268ms128356 KiB
93Elfogadva351ms128356 KiB
subtask641/41
94Elfogadva108ms128140 KiB
95Elfogadva328ms128504 KiB
96Elfogadva86ms128248 KiB
97Elfogadva108ms128228 KiB
98Elfogadva108ms128260 KiB
99Elfogadva86ms128228 KiB
100Elfogadva108ms128228 KiB
101Elfogadva108ms128228 KiB
102Elfogadva86ms128396 KiB
103Elfogadva86ms128228 KiB
104Elfogadva86ms128228 KiB
105Elfogadva108ms128052 KiB
106Elfogadva108ms128484 KiB
107Elfogadva101ms128312 KiB
108Elfogadva86ms128080 KiB
109Elfogadva108ms128228 KiB
110Elfogadva108ms128228 KiB
111Elfogadva86ms128360 KiB
112Elfogadva86ms128364 KiB
113Elfogadva107ms128376 KiB
114Elfogadva103ms128228 KiB
115Elfogadva108ms128228 KiB
116Elfogadva87ms128432 KiB
117Elfogadva85ms128380 KiB
118Elfogadva86ms128332 KiB
119Elfogadva108ms128296 KiB
120Elfogadva108ms128228 KiB
121Elfogadva89ms128376 KiB
122Elfogadva89ms128248 KiB
123Elfogadva108ms128140 KiB
124Elfogadva109ms128228 KiB
125Elfogadva87ms128376 KiB
126Elfogadva87ms128372 KiB
127Elfogadva82ms128228 KiB
128Elfogadva86ms128228 KiB
129Elfogadva86ms128632 KiB
130Elfogadva90ms128496 KiB
131Elfogadva108ms128500 KiB
132Elfogadva86ms128100 KiB
133Elfogadva85ms128228 KiB
134Elfogadva85ms128360 KiB
135Elfogadva143ms128288 KiB
136Elfogadva150ms128200 KiB
137Elfogadva252ms128356 KiB
138Elfogadva284ms128356 KiB
139Elfogadva185ms128356 KiB
140Elfogadva268ms128356 KiB
141Elfogadva351ms128356 KiB
142Elfogadva87ms128356 KiB
143Elfogadva114ms128412 KiB
144Elfogadva168ms128484 KiB
145Elfogadva201ms128416 KiB
146Elfogadva277ms128484 KiB
147Elfogadva289ms128356 KiB
148Elfogadva319ms128492 KiB
149Elfogadva397ms128356 KiB
150Elfogadva393ms128484 KiB
151Elfogadva330ms128484 KiB
152Elfogadva324ms128484 KiB