| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 875130 | vjudge1 | W (RMI18_w) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#pragma GCC target( "sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")
#include<bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define sz(x) (int)x.size()
#define bit(a, i) ((a>>i)&1)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int P = 31;
const int K = 500;
const ll inf = 1e9;
const ll INF = 1e18;
const int mod = 1e9+7;
const int maxn = 4e5 + 10;
const int dx[] = {0, 0, -1, 1};
const int dy[] = {1, -1, 0, 0};
int n, sz;
int a[maxn];
int cnt[maxn];
ll fact[maxn];
map<int, int>c;
ll dp[1<<5][maxn];
void add(ll &a, ll b){
a = (a+b) % mod;
}
ll bpow(int x, int n){
if(!n) return 1;
if(n&1) return x*bpow(x, n-1)%mod;
ll y = bpow(x, n/2);
return y*y%mod;
}
int C(int n, int k){
return fact[n]*bpow(fact[k], mod-2)%mod*bpow(fact[n-k], mod-2)%mod;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
set<int>st;
for(int i=1; i<=n; i++){
cin >> a[i];
st.insert(a[i]);
} fact[0] = 1;
for(int i=1; i<maxn; i++)
fact[i] = fact[i-1]*i%mod;
for(auto to: st){
c[to] = ++sz;
}
for(int i=1; i<=n; i++){
cnt[c[a[i]]]++;
} dp[0][0] = 1;
for(int i=0; i<sz; i++){
for(int mask=0; mask<(1<<5); mask++){
cout << dp[mask][i] << " ";
if(!dp[mask][i]) continue;
if((mask&5) && !bit(mask, 1)) continue;
if((mask&20) && !bit(mask, 3)) continue;
for(int mask2=mask; mask2<(1<<5); mask2++){
if((mask2&5) && !bit(mask2, 1)) continue;
if((mask2&20) && !bit(mask2, 3)) continue;
int num = 0;
int val = mask2^mask;
if((val&3) == 3) continue;
if((val&6) == 6) continue;
if((val&12) == 12) continue;
if((val&24) == 24) continue;
int count = __builtin_popcount(val);
if(count > cnt[i+1]) continue;
if(bit(mask2, 1) && (!bit(mask2, 0) || bit(val, 0))) num++;
if(bit(mask2, 1) && (!bit(mask2, 2) || bit(val, 2))) num++;
if(bit(mask2, 3) && (!bit(mask2, 2) || bit(val, 2))) num++;
if(bit(mask2, 3) && (!bit(mask2, 4) || bit(val, 4))) num++;
add(dp[mask2][i+1], dp[mask][i]*C(cnt[i+1]-count+num-1, num-1));
}
} cout << "\n";
}
for(int mask=0; mask<(1<<5); mask++){
cout << dp[mask][sz] << " ";
} cout << "\n";
cout << dp[(1<<5)-1][sz];
}