제출 #557912

#제출 시각아이디문제언어결과실행 시간메모리
557912FatihSolakW (RMI18_w)C++17
30 / 100
1097 ms32080 KiB
#include <bits/stdc++.h> #define N 300005 using namespace std; const int mod = 1e9 + 7; long long fact[N]; long long ifact[N]; long long binpow(long long a,long long b){ long long ret = 1; while(b){ if(b & 1) ret = ret*a%mod; a = a*a%mod; b >>= 1; } return ret; } long long C(int n,int r){ return fact[n] * ifact[r]%mod*ifact[n-r]%mod; } long long val[N][5]; void solve(){ int n; cin >> n; map<int,int> cnt; for(int i = 1;i<=n;i++){ int x; cin >> x; cnt[x]++; } vector<int> v; for(auto u:cnt) v.push_back(u.second); if(cnt.size() == 2){ if(v[0] < 2 || v[1] < 3){ cout << 0; return; } cout << C(v[0]-2+1,1) *C(v[1]-3+2,2) %mod; return; } for(int i = 2;i<=n;i++){ val[i][1] = 1; } for(int i = 3;i<=n;i++){ val[i][2] = (binpow(2,i-1) - 2 + mod)%mod; } for(int i = 4;i<=n;i++){ //val[n][3] = (3^n - 2^(n+2) - 2n + 11)/4 val[i][3] = (binpow(3,i) - binpow(2,i+2) - 2*i + 11 + 2*mod)%mod*binpow(4,mod-2)%mod; //cout << i << " " << val[i][3] << endl; } for(int i = 5;i<=n;i++){ for(int j = 2;j<=i-3;j++){ val[i][4] = (val[i][4] + C(i-1,j-1) * ( (binpow(3,i-j) - binpow(2,i-j+1) - 2 * (i-j) + 3 + 2*mod )%mod* binpow(4,mod-2)%mod )%mod); } val[i][4] = val[i][4] *2 %mod; //cout << i << " " << val[i][4] << endl; } cout << val[n][4] << endl; } int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); #ifdef Local freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif fact[0] = ifact[0]= 1; for(int i = 1;i<N;i++){ fact[i] = fact[i-1] * i %mod; ifact[i] = binpow(fact[i],mod-2); } int t = 1; //cin >> t; while(t--){ solve(); } #ifdef Local cout << endl << fixed << setprecision(2) << 1000.0*clock()/CLOCKS_PER_SEC << " milliseconds."; #endif }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...