Submission #526555

#TimeUsernameProblemLanguageResultExecution timeMemory
526555radalRuins 3 (JOI20_ruins3)C++14
58 / 100
10 ms6332 KiB
#include <bits/stdc++.h> #pragma GCC optimize("O3") #pragma GCC target("avx2,fma") #define rep(i,l,r) for (int i = l; i < r; i++) #define repr(i,r,l) for (int i = r; i >= l; i--) #define X first #define Y second #define pb push_back #define endl '\n' #define debug(x) cerr << #x << " : " << x << endl; using namespace std; typedef long long ll; typedef long double ld; typedef pair<int,int> pll; const long long int N = 6e2+20,mod = 1e9+7,inf = 1e18+10,maxm= (1 << 21); inline int mkay(int a,int b){ if (a+b >= mod) return a+b-mod; if (a+b < 0) return a+b+mod; return a+b; } inline int poww(int a,int k){ if (k < 0) return 0; int z = 1; while (k){ if (k&1) z = 1ll*z*a%mod; a = 1ll*a*a%mod; k >>= 1; } return z; } bool b[N]; int dp[N],pre[N][N],c[N][N]; int main(){ ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; rep(i,0,n){ int x; cin >> x; b[x] = 1; } int m = n * 2; rep(i,0,m+1) c[0][i] = 1; rep(i,1,m+1) rep(j,i,m+1) c[i][j] = mkay(c[i-1][j-1],c[i][j-1]); dp[0] = 1; rep(i,1,n+1){ rep(j,1,i+1){ dp[i] = mkay(dp[i],1ll*c[j-1][i-1]*dp[j-1]%mod*dp[i-j]%mod*(i-j+2)%mod); } } int c0 = 0,c1 = 0; pre[m+1][0] = 1; repr(i,m,1){ if (b[i]){ rep(j,0,c1+2){ pre[i][j] = pre[i+1][j]; rep(y,1,j+1){ pre[i][j] = mkay(pre[i][j],1ll*pre[i+1][y-1]*dp[j-y]%mod*c[j-y][c1-y+1]%mod*(j-y+2)%mod); } } c1++; } else{ rep(j,0,c1+1){ pre[i][j] = 1ll*pre[i+1][j]*max(0,-c0+j)%mod; } c0++; } } cout << 1ll*pre[1][n]*poww(poww(2,n),mod-2)%mod; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...