結果
問題 | No.829 成長関数インフレ中 |
ユーザー |
|
提出日時 | 2018-12-06 22:10:29 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,637 bytes |
コンパイル時間 | 2,376 ms |
コンパイル使用メモリ | 170,780 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-09-15 13:18:42 |
合計ジャッジ時間 | 3,244 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 WA * 2 |
ソースコード
#include <bits/stdc++.h> #pragma GCC optimize("O3") #pragma GCC target("avx") #define ll long long #define INF 1000000005 #define MOD 1000000007 #define EPS 1e-10 #define rep(i,n) for(int i=0;i<(int)(n);++i) #define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i) #define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i) #define each(a,b) for(auto& (a): (b)) #define all(v) (v).begin(),(v).end() #define len(v) (int)(v).size() #define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end()) #define cmx(x,y) x=max(x,y) #define cmn(x,y) x=min(x,y) #define fi first #define se second #define pb push_back #define show(x) cout<<#x<<" = "<<(x)<<endl #define spair(p) cout<<#p<<": "<<p.fi<<" "<<p.se<<endl #define sar(a,n) cout<<#a<<":";rep(pachico,n)cout<<" "<<a[pachico];cout<<endl #define svec(v) cout<<#v<<":";rep(pachico,v.size())cout<<" "<<v[pachico];cout<<endl #define svecp(v) cout<<#v<<":";each(pachico,v)cout<<" {"<<pachico.first<<":"<<pachico.second<<"}";cout<<endl #define sset(s) cout<<#s<<":";each(pachico,s)cout<<" "<<pachico;cout<<endl #define smap(m) cout<<#m<<":";each(pachico,m)cout<<" {"<<pachico.first<<":"<<pachico.second<<"}";cout<<endl using namespace std; typedef pair<int,int> P; typedef pair<ll,ll> pll; typedef vector<int> vi; typedef vector<vi> vvi; typedef vector<ll> vl; typedef vector<vl> vvl; typedef vector<double> vd; typedef vector<P> vp; typedef vector<string> vs; const int MAX_N = 200000; #define getchar getchar_unlocked inline int in() { int n = 0; short c; while ((c = getchar()) >= '0') n = n * 10 + c - '0'; return n; } int inv[MAX_N],fac[MAX_N],finv[MAX_N]; void make() { fac[0] = fac[1] = 1; finv[0] = finv[1] = 1; inv[1] = 1; for(int i=2;i<MAX_N;i++){ inv[i] = MOD - (ll)inv[MOD%i] * (MOD/i) % MOD; fac[i] = (ll)fac[i-1] * i % MOD; finv[i] = (ll)finv[i-1] * inv[i] % MOD; } } inline int prod(int a, int b) { return (a < b) ? 0 : ((ll)fac[a] * finv[a-b] % MOD); } void extgcd(int a,int b, int& x,int& y) { if(b){ extgcd(b, a%b, y, x); y -= (a/b)*x; }else{ x = 1, y = 0; } } int mod_inverse(int a, int m) { int x, y; extgcd(a,m,x,y); return (m + x % m) % m; } int cnt[MAX_N]; int main() { int n = in(), B = in(); rep(i,n){ cnt[in()]++; } make(); int id = 0, ad = 0, ans = B, s = 0, t = 0; rrep(i,MAX_N){ if(!cnt[i]) continue; s = (ll)prod(id+cnt[i]-1, cnt[i]-1) * cnt[i] % MOD; t = ((ll)s * B + prod(id+cnt[i]-1, cnt[i])) % MOD; ad = (ad + (ll)s * mod_inverse(t, MOD) % MOD) % MOD; ans = (ll)ans * t % MOD; id += cnt[i]; } cout << (ll)ans * ad % MOD << "\n"; return 0; }