結果

問題 No.829 成長関数インフレ中
ユーザー beetbeet
提出日時 2019-05-03 22:51:38
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 8,769 bytes
コンパイル時間 3,218 ms
コンパイル使用メモリ 226,512 KB
実行使用メモリ 130,604 KB
最終ジャッジ日時 2023-08-30 06:33:25
合計ジャッジ時間 17,439 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 102 ms
96,776 KB
testcase_01 AC 101 ms
96,880 KB
testcase_02 AC 102 ms
96,848 KB
testcase_03 AC 104 ms
96,712 KB
testcase_04 AC 101 ms
96,808 KB
testcase_05 AC 102 ms
96,860 KB
testcase_06 AC 102 ms
96,772 KB
testcase_07 AC 102 ms
96,916 KB
testcase_08 AC 103 ms
96,760 KB
testcase_09 AC 102 ms
96,756 KB
testcase_10 AC 102 ms
96,720 KB
testcase_11 AC 103 ms
96,832 KB
testcase_12 AC 132 ms
99,716 KB
testcase_13 AC 104 ms
97,056 KB
testcase_14 AC 123 ms
98,900 KB
testcase_15 AC 640 ms
104,472 KB
testcase_16 AC 1,210 ms
113,700 KB
testcase_17 AC 1,997 ms
116,680 KB
testcase_18 TLE -
testcase_19 TLE -
testcase_20 TLE -
testcase_21 AC 117 ms
98,664 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}


template<typename T,T MOD = 1000000007>
struct Mint{
  T v;
  Mint():v(0){}
  Mint(signed v):v(v){}
  Mint(long long t){v=t%MOD;if(v<0) v+=MOD;}

  Mint pow(long long k){
    Mint res(1),tmp(v);
    while(k){
      if(k&1) res*=tmp;
      tmp*=tmp;
      k>>=1;
    }
    return res;
  }
  
  static Mint add_identity(){return Mint(0);}
  static Mint mul_identity(){return Mint(1);}
  
  Mint inv(){return pow(MOD-2);}
  
  Mint& operator+=(Mint a){v+=a.v;if(v>=MOD)v-=MOD;return *this;}
  Mint& operator-=(Mint a){v+=MOD-a.v;if(v>=MOD)v-=MOD;return *this;}
  Mint& operator*=(Mint a){v=1LL*v*a.v%MOD;return *this;}
  Mint& operator/=(Mint a){return (*this)*=a.inv();}
  
  Mint operator+(Mint a) const{return Mint(v)+=a;};
  Mint operator-(Mint a) const{return Mint(v)-=a;};
  Mint operator*(Mint a) const{return Mint(v)*=a;};
  Mint operator/(Mint a) const{return Mint(v)/=a;};

  Mint operator-() const{return v?Mint(MOD-v):Mint(v);}

  bool operator==(const Mint a)const{return v==a.v;}
  bool operator!=(const Mint a)const{return v!=a.v;}
  bool operator <(const Mint a)const{return v <a.v;}

  // find x s.t. a^x = b
  static T log(Mint a,Mint b){
    const T sq=40000;
    unordered_map<T, T> dp;
    dp.reserve(sq);
    Mint res(1);
    for(Int r=0;r<sq;r++){
      if(!dp.count(res)) dp[res]=r;
      res*=a;
    }
    Mint p=pow(a.inv(),sq);
    res=b;
    for(Int q=0;q<=MOD/sq+1;q++){
      if(dp.count(res)){
        T idx=q*sq+dp[res];
        if(idx>0) return idx;
      }
      res*=p;
    }    
    return T(-1);
  }

  static vector<Mint> fact,finv,invs;
  
  static void init(Int n){
    Int m=fact.size();
    if(n<m) return;
    
    fact.resize(n+1,1);
    finv.resize(n+1,1);
    invs.resize(n+1,1);
    
    if(m==0) m=1;
    for(Int i=m;i<=n;i++) fact[i]=fact[i-1]*Mint(i);
    finv[n]=Mint(1)/fact[n];
    for(Int i=n;i>=m;i--) finv[i-1]=finv[i]*Mint(i);
    for(Int i=m;i<=n;i++) invs[i]=finv[i]*fact[i-1];
  }

  static Mint comb(long long n,Int k){
    Mint res(1);
    for(Int i=0;i<k;i++){
      res*=Mint(n-i);
      res/=Mint(i+1);
    }
    return res;
  }
  
  static Mint C(Int n,Int k){
    if(n<k||k<0) return Mint(0);
    init(n);
    return fact[n]*finv[n-k]*finv[k];
  }

  static Mint P(Int n,Int k){
    if(n<k||k<0) return Mint(0);
    init(n);
    return fact[n]*finv[n-k];
  }
  
  static Mint H(Int n,Int k){
    if(n<0||k<0) return Mint(0);
    if(!n&&!k) return Mint(1);
    init(n+k-1);
    return C(n+k-1,k);
  }

  static Mint S(Int n,Int k){
    Mint res;
    init(k);
    for(Int i=1;i<=k;i++){
      Mint tmp=C(k,i)*Mint(i).pow(n);
      if((k-i)&1) res-=tmp;
      else res+=tmp;
    }    
    return res*=finv[k];
  }

  static vector<vector<Mint> > D(Int n,Int m){
    vector<vector<Mint> > dp(n+1,vector<Mint>(m+1,0));
    dp[0][0]=Mint(1);
    for(Int i=0;i<=n;i++){
      for(Int j=1;j<=m;j++){
        if(i-j>=0) dp[i][j]=dp[i][j-1]+dp[i-j][j];
        else dp[i][j]=dp[i][j-1];
      }
    }
    return dp;
  }

  static Mint B(Int n,Int k){
    if(n==0) return Mint(1);
    k=min(k,n);
    init(k);    
    vector<Mint> dp(k+1);
    dp[0]=Mint(1);
    for(Int i=1;i<=k;i++)
      dp[i]=dp[i-1]+((i&1)?-finv[i]:finv[i]);    
    Mint res;
    for(Int i=1;i<=k;i++)
      res+=Mint(i).pow(n)*finv[i]*dp[k-i];    
    return res;
  }

  static Mint montmort(Int n){
    Mint res;
    init(n);
    for(Int k=2;k<=n;k++){
      if(k&1) res-=finv[k];
      else res+=finv[k];
    }
    return res*=fact[n];
  }

  static Mint LagrangePolynomial(vector<Mint> &y,Mint t){
    Int n=y.size()-1;    
    if(t.v<=n) return y[t.v];
    init(n+1);
    Mint num(1);
    for(Int i=0;i<=n;i++) num*=t-Mint(i);
    Mint res;
    for(Int i=0;i<=n;i++){
      Mint tmp=y[i]*num/(t-Mint(i))*finv[i]*finv[n-i];
      if((n-i)&1) res-=tmp;
      else res+=tmp;
    }
    return res;
  }
};
template<typename T,T MOD>
vector<Mint<T, MOD> > Mint<T, MOD>::fact = vector<Mint<T, MOD> >();
template<typename T,T MOD>
vector<Mint<T, MOD> > Mint<T, MOD>::finv = vector<Mint<T, MOD> >();
template<typename T,T MOD>
vector<Mint<T, MOD> > Mint<T, MOD>::invs = vector<Mint<T, MOD> >();

using ll = long long;
namespace NTT {
  std::vector<Int> tmp;
  size_t sz = 1;
 
  inline Int powMod(Int n, Int p, Int m) {
    Int res = 1;
    while (p) {
      if (p & 1) res = (ll)res * n % m;
      n = (ll)n * n % m;
      p >>= 1;
    }
    return (Int)res;
  }
  inline Int invMod(Int n, Int m) {
    return powMod(n, m - 2, m);
  }
 
  template <Int Mod, Int PrimitiveRoot>
  struct NTTPart {
    static std::vector<Int> ntt(std::vector<Int> a, bool inv = false) {
      size_t mask = sz - 1;
      size_t p = 0;
      for (size_t i = sz >> 1; i >= 1; i >>= 1) {
        auto& cur = (p & 1) ? tmp : a;
        auto& nex = (p & 1) ? a : tmp;
        Int e = powMod(PrimitiveRoot, (Mod - 1) / sz * i, Mod);
        if (inv) e = invMod(e, Mod);
        Int w = 1;
        for (size_t j = 0; j < sz; j += i) {
          for (size_t k = 0; k < i; ++k) {
            nex[j + k] = (cur[((j << 1) & mask) + k] + (ll)w * cur[(((j << 1) + i) & mask) + k]) % Mod;
          }
          w = (ll)w * e % Mod;
        }
        ++p;
      }
      if (p & 1) std::swap(a, tmp);
      if (inv) {
        Int invSz = invMod(sz, Mod);
        for (size_t i = 0; i < sz; ++i) a[i] = (ll)a[i] * invSz % Mod;
      }
      return a;
    }
    static std::vector<Int> mul(std::vector<Int> a, std::vector<Int> b) {
      a = ntt(a);
      b = ntt(b);
      for (size_t i = 0; i < sz; ++i) a[i] = (ll)a[i] * b[i] % Mod;
      a = ntt(a, true);
      return a;
    }
  };
 
  constexpr Int M[] = {1224736769, 469762049, 167772161};
  constexpr Int PR[] = {3, 3, 3};
  constexpr Int NTT_CONVOLUTION_TIME = 3;
  /*
    X := max(a)*max(b)*min(|a|, |b|) のとき,
    NTT_CONVOLUTION_TIME <- 1: X <         1224736769 = 1.2*10^ 9 ~ 2^30
    NTT_CONVOLUTION_TIME <- 2: X < 575334854091079681 = 5.8*10^17 ~ 2^59
    NTT_CONVOLUTION_TIME <- 3: X < 2^86 (32bit * 32bit * 10^7くらいまで)
  */
 
  inline void garner(std::vector<Int> *c, Int mod) {
    if (NTT_CONVOLUTION_TIME == 1) {
      for(auto& x : c[0]) x %= mod;
    }
    else if (NTT_CONVOLUTION_TIME == 2) {
      const Int r01 = invMod(M[0], M[1]);
      for (size_t i = 0; i < sz; ++i) {
        c[1][i] = (c[1][i] - c[0][i]) * (ll)r01 % M[1];
        if (c[1][i] < 0) c[1][i] += M[1];
        c[0][i] = (c[0][i] + (ll)c[1][i] * M[0]) % mod;
      }
    }
    else if (NTT_CONVOLUTION_TIME == 3) {
      const Int R01 = invMod(M[0], M[1]);
      const Int R02 = invMod(M[0], M[2]);
      const Int R12 = invMod(M[1], M[2]);
      const Int M01 = (ll)M[0] * M[1] % mod;
      for (size_t i = 0; i < sz; ++i) {
        c[1][i] = (c[1][i] - c[0][i]) * (ll)R01 % M[1];
        if (c[1][i] < 0) c[1][i] += M[1];
        c[2][i] = ((c[2][i] - c[0][i]) * (ll)R02 % M[2] - c[1][i]) * R12 % M[2];
        if (c[2][i] < 0) c[2][i] += M[2];
        c[0][i] = (c[0][i] + (ll)c[1][i] * M[0] + (ll)c[2][i] * M01) % mod;
      }
    }
  }
  std::vector<Int> mul(std::vector<Int> a, std::vector<Int> b, Int mod) {
    for (auto& x : a) x %= mod;
    for (auto& x : b) x %= mod;
 
    size_t m = a.size() + b.size() - 1;
    sz = 1;
    while (m > sz) sz <<= 1;
    tmp.resize(sz);
    a.resize(sz, 0);
    b.resize(sz, 0);
 
    std::vector<Int> c[NTT_CONVOLUTION_TIME];
    if (NTT_CONVOLUTION_TIME >= 1) c[0] = NTTPart<M[0], PR[0]>::mul(a, b);
    if (NTT_CONVOLUTION_TIME >= 2) c[1] = NTTPart<M[1], PR[1]>::mul(a, b);
    if (NTT_CONVOLUTION_TIME >= 3) c[2] = NTTPart<M[2], PR[2]>::mul(a, b);
    for (auto& v : c) v.resize(m);
    garner(c, mod);
    return c[0];
  }
}; 

//INSERT ABOVE HERE
signed main(){
  Int n,b;
  cin>>n>>b;
  vector<Int> s(n);
  for(Int i=0;i<n;i++) cin>>s[i];
  using M = Mint<Int>;
  M::init(4e6);

  vector<Int> cnt(n,0);
  for(Int i=0;i<n;i++) cnt[s[i]]++;


  using P = pair<Int, vector<Int> > ;
  priority_queue<P> pq;
  pq.emplace(-1,vector<Int>(1,1));
  
  Int sum=0;
  for(Int i=n-1;i>=0;i--){    
    if(cnt[i]==0) continue;
    M x=M::H(sum,cnt[i]);
    M y=M::H(sum+1,cnt[i])-x;
    x*=M::fact[cnt[i]];
    y*=M::fact[cnt[i]];

    pq.emplace(-2,vector<Int>({x.v,y.v}));
    sum+=cnt[i];   
  }
  
  const Int MOD = 1e9+7;
  while(pq.size()>1u){
    auto a=pq.top().second;pq.pop();
    auto b=pq.top().second;pq.pop();    
    auto c=NTT::mul(a,b,MOD);
    pq.emplace(-(Int)c.size(),c);
  }
  
  auto dp=pq.top().second;
  M ans(0),res(1);
  for(Int j=0;j<(Int)dp.size();j++){
    ans+=M(j*dp[j])*res;
    res*=M(b);
  }
  cout<<ans.v<<endl;
  return 0;
}
0