結果

問題 No.118 門松列(2)
ユーザー nowasoma
提出日時 2021-03-29 10:06:56
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,674 bytes
コンパイル時間 1,738 ms
コンパイル使用メモリ 177,468 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-11-29 09:42:35
合計ジャッジ時間 2,966 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 WA * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using uint = unsigned;
using ull = unsigned long long;
#define rep(i, n) for(ll i = 0; i < n; ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < (t); ++i)
#define dsrep(i,t,s) for(int i = (t)-1; i >= (s); --i)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define vvi vector<vector<int>>
#define vll vector<ll>
#define vst vector<string>
#define vpi vector<pii>
#define vpll vector<pll>
#define fi first
#define se second
#define all(c) begin(c), end(c)
#define SUM(v) accumulate(all(v), 0LL)
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define drop(s) cout << #s << endl, exit(0)
#define endl '\n'
using Graph = vector<vector<int>>;
const int inf = 100100101;
const ll ll_inf = 1e18;
const int mod = 1000000007;
template <class T> using vc = vector<T>;
template <class T> using vvc = vector<vc<T>>;
template <class T> using vvvc = vector<vvc<T>>;
template <class T> using vvvvc = vector<vvvc<T>>;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a = b; return 1; } return 0; }

//https://yukicoder.me/problems/no/118


// Mod int
const int minmod = 1000000007;
// const int minmod = 998244353;
struct mint {
  unsigned x;
  mint(): x(0) {}
  mint(ll x):x((x%minmod+minmod)%minmod) {}
  mint operator-() const { return mint(0) - *this;}
  mint operator~() const { return mint(1) / *this;}
  mint& operator+=(const mint& a) { if((x+=a.x)>=minmod) x-=minmod; return *this;}
  mint& operator-=(const mint& a) { if((x+=minmod-a.x)>=minmod) x-=minmod; return *this;}
  mint& operator*=(const mint& a) { x=(ull)x*a.x%minmod; return *this;}
  mint& operator/=(const mint& a) { x=(ull)x*a.pow(minmod-2).x%minmod; return *this;}
  mint operator+(const mint& a) const { return mint(*this) += a;}
  mint operator-(const mint& a) const { return mint(*this) -= a;}
  mint operator*(const mint& a) const { return mint(*this) *= a;}
  mint operator/(const mint& a) const { return mint(*this) /= a;}
  mint pow(ll t) const {
    if(!t) return 1;
    mint res = pow(t/2);
    res *= res;
    return (t&1)?res*x:res;
  }
  bool operator<(const mint& a) const { return x < a.x;}
  bool operator==(const mint& a) const { return x == a.x;}
  bool operator!=(const mint& a) const { return x != a.x;}
};
mint ex(mint x, ll t) { return x.pow(t);}
istream& operator>>(istream&i,mint&a) {i>>a.x;return i;}
//*
ostream& operator<<(ostream&o,const mint&a) {o<<a.x;return o;}
/*/
ostream& operator<<(ostream&o, const mint&x) {
  int a = x.x, b = 1;
  rep(s,2)rrep(i,1000) {
    int y = ((s?-x:x)*i).x;
    if (abs(a)+b > y+i) a = s?-y:y, b = i;
  }
  o<<a; if (b != 1) o<<'/'<<b; return o;
}//*/
using vm = vector<mint>;
using vvm = vector<vm>;
struct comb {
  vm f, g;
  comb() {}
  comb(int mx): f(mx+1), g(mx+1) {
    f[0] = 1;
    rrep(i,mx) f[i] = f[i-1]*i;
    g[mx] = f[mx].pow(minmod-2);
    for(int i = mx; i > 0; --i) g[i-1] = g[i]*i;
  }
  mint operator()(int a, int b) {
    if (a < b || b < 0) return 0;
    return f[a]*g[b]*g[a-b];
  }
};


mint combination(mint n, mint r){
  if (n == r || r == 0) return 1;
  else return combination(n, r-1)*(n-r+1)/r;
}

int main() {
  int n;
  cin >> n;
  map<int,int> mp;
  rep(i,n) {
    int x;
    cin >> x;
    mp[x]++;
  }
  mint si = mp.size();
  mint ans = (mint)combination(si,3);

  for(auto x : mp){
    ans *= x.se;
  }
  cout<<ans<<endl;
  return 0;
}
0