結果

問題 No.1214 Market
ユーザー LayCurse
提出日時 2020-08-30 17:33:23
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 150 ms / 2,000 ms
コード長 14,431 bytes
コンパイル時間 3,432 ms
コンパイル使用メモリ 224,012 KB
最終ジャッジ日時 2025-01-14 01:22:27
ジャッジサーバーID
(参考情報)
judge3 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 39
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define MD (1000000007U)
void *wmem;
char memarr[96000000];
template<class S, class T> inline S max_L(S a,T b){
return a>=b?a:b;
}
template<class T> inline void walloc1d(T **arr, int x, void **mem = &wmem){
static int skip[16] = {0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
(*mem) = (void*)( ((char*)(*mem)) + skip[((unsigned long long)(*mem)) & 15] );
(*arr)=(T*)(*mem);
(*mem)=((*arr)+x);
}
template<class T1> void sortA_L(int N, T1 a[], void *mem = wmem){
sort(a, a+N);
}
template<class T1, class T2> void sortA_L(int N, T1 a[], T2 b[], void *mem = wmem){
int i;
pair<T1, T2> *arr;
walloc1d(&arr, N, &mem);
for(i=(0);i<(N);i++){
arr[i].first = a[i];
arr[i].second = b[i];
}
sort(arr, arr+N);
for(i=(0);i<(N);i++){
a[i] = arr[i].first;
b[i] = arr[i].second;
}
}
template<class T1> void rsortA_L(int N, T1 a[], void *mem = wmem){
sortA_L(N, a, mem);
reverse(a, a+N);
}
template<class T1, class T2> void rsortA_L(int N, T1 a[], T2 b[], void *mem = wmem){
sortA_L(N, a, b, mem);
reverse(a, a+N);
reverse(b, b+N);
}
struct Modint{
unsigned val;
Modint(){
val=0;
}
Modint(int a){
val = ord(a);
}
Modint(unsigned a){
val = ord(a);
}
Modint(long long a){
val = ord(a);
}
Modint(unsigned long long a){
val = ord(a);
}
inline unsigned ord(unsigned a){
return a%MD;
}
inline unsigned ord(int a){
a %= (int)MD;
if(a < 0){
a += MD;
}
return a;
}
inline unsigned ord(unsigned long long a){
return a%MD;
}
inline unsigned ord(long long a){
a %= (int)MD;
if(a < 0){
a += MD;
}
return a;
}
inline unsigned get(){
return val;
}
inline Modint &operator+=(Modint a){
val += a.val;
if(val >= MD){
val -= MD;
}
return *this;
}
inline Modint &operator-=(Modint a){
if(val < a.val){
val = val + MD - a.val;
}
else{
val -= a.val;
}
return *this;
}
inline Modint &operator*=(Modint a){
val = ((unsigned long long)val*a.val)%MD;
return *this;
}
inline Modint &operator/=(Modint a){
return *this *= a.inverse();
}
inline Modint operator+(Modint a){
return Modint(*this)+=a;
}
inline Modint operator-(Modint a){
return Modint(*this)-=a;
}
inline Modint operator*(Modint a){
return Modint(*this)*=a;
}
inline Modint operator/(Modint a){
return Modint(*this)/=a;
}
inline Modint operator+(int a){
return Modint(*this)+=Modint(a);
}
inline Modint operator-(int a){
return Modint(*this)-=Modint(a);
}
inline Modint operator*(int a){
return Modint(*this)*=Modint(a);
}
inline Modint operator/(int a){
return Modint(*this)/=Modint(a);
}
inline Modint operator+(long long a){
return Modint(*this)+=Modint(a);
}
inline Modint operator-(long long a){
return Modint(*this)-=Modint(a);
}
inline Modint operator*(long long a){
return Modint(*this)*=Modint(a);
}
inline Modint operator/(long long a){
return Modint(*this)/=Modint(a);
}
inline Modint operator-(void){
Modint res;
if(val){
res.val=MD-val;
}
else{
res.val=0;
}
return res;
}
inline operator bool(void){
return val!=0;
}
inline operator int(void){
return get();
}
inline operator long long(void){
return get();
}
inline Modint inverse(){
int a = val;
int b = MD;
int u = 1;
int v = 0;
int t;
Modint res;
while(b){
t = a / b;
a -= t * b;
swap(a, b);
u -= t * v;
swap(u, v);
}
if(u < 0){
u += MD;
}
res.val = u;
return res;
}
inline Modint pw(unsigned long long b){
Modint a(*this);
Modint res;
res.val = 1;
while(b){
if(b&1){
res *= a;
}
b >>= 1;
a *= a;
}
return res;
}
inline bool operator==(int a){
return ord(a)==val;
}
inline bool operator!=(int a){
return ord(a)!=val;
}
}
;
inline Modint operator+(int a, Modint b){
return Modint(a)+=b;
}
inline Modint operator-(int a, Modint b){
return Modint(a)-=b;
}
inline Modint operator*(int a, Modint b){
return Modint(a)*=b;
}
inline Modint operator/(int a, Modint b){
return Modint(a)/=b;
}
inline Modint operator+(long long a, Modint b){
return Modint(a)+=b;
}
inline Modint operator-(long long a, Modint b){
return Modint(a)-=b;
}
inline Modint operator*(long long a, Modint b){
return Modint(a)*=b;
}
inline Modint operator/(long long a, Modint b){
return Modint(a)/=b;
}
inline int my_getchar_unlocked(){
static char buf[1048576];
static int s = 1048576;
static int e = 1048576;
if(s == e && e == 1048576){
e = fread_unlocked(buf, 1, 1048576, stdin);
s = 0;
}
if(s == e){
return EOF;
}
return buf[s++];
}
inline void rd(int &x){
int k;
int m=0;
x=0;
for(;;){
k = my_getchar_unlocked();
if(k=='-'){
m=1;
break;
}
if('0'<=k&&k<='9'){
x=k-'0';
break;
}
}
for(;;){
k = my_getchar_unlocked();
if(k<'0'||k>'9'){
break;
}
x=x*10+k-'0';
}
if(m){
x=-x;
}
}
struct MY_WRITER{
char buf[1048576];
int s;
int e;
MY_WRITER(){
s = 0;
e = 1048576;
}
~MY_WRITER(){
if(s){
fwrite_unlocked(buf, 1, s, stdout);
}
}
}
;
MY_WRITER MY_WRITER_VAR;
void my_putchar_unlocked(int a){
if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){
fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);
MY_WRITER_VAR.s = 0;
}
MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;
}
inline void wt_L(char a){
my_putchar_unlocked(a);
}
inline void wt_L(int x){
int s=0;
int m=0;
char f[10];
if(x<0){
m=1;
x=-x;
}
while(x){
f[s++]=x%10;
x/=10;
}
if(!s){
f[s++]=0;
}
if(m){
my_putchar_unlocked('-');
}
while(s--){
my_putchar_unlocked(f[s]+'0');
}
}
inline void wt_L(Modint x){
int i;
i = (int)x;
wt_L(i);
}
template<class T, class S> inline T pow_L(T a, S b){
T res = 1;
res = 1;
for(;;){
if(b&1){
res *= a;
}
b >>= 1;
if(b==0){
break;
}
a *= a;
}
return res;
}
inline double pow_L(double a, double b){
return pow(a,b);
}
template<class S> inline void arrInsert(const int k, int &sz, S a[], const S aval){
int i;
sz++;
for(i=sz-1;i>k;i--){
a[i] = a[i-1];
}
a[k] = aval;
}
template<class S, class T> inline void arrInsert(const int k, int &sz, S a[], const S aval, T b[], const T bval){
int i;
sz++;
for(i=sz-1;i>k;i--){
a[i] = a[i-1];
}
for(i=sz-1;i>k;i--){
b[i] = b[i-1];
}
a[k] = aval;
b[k] = bval;
}
template<class S, class T, class U> inline void arrInsert(const int k, int &sz, S a[], const S aval, T b[], const T bval, U c[], const U cval){
int i;
sz++;
for(i=sz-1;i>k;i--){
a[i] = a[i-1];
}
for(i=sz-1;i>k;i--){
b[i] = b[i-1];
}
for(i=sz-1;i>k;i--){
c[i] = c[i-1];
}
a[k] = aval;
b[k] = bval;
c[k] = cval;
}
template<class S, class T, class U, class V> inline void arrInsert(const int k, int &sz, S a[], const S aval, T b[], const T bval, U c[], const U
    cval, V d[], const V dval){
int i;
sz++;
for(i=sz-1;i>k;i--){
a[i] = a[i-1];
}
for(i=sz-1;i>k;i--){
b[i] = b[i-1];
}
for(i=sz-1;i>k;i--){
c[i] = c[i-1];
}
for(i=sz-1;i>k;i--){
d[i] = d[i-1];
}
a[k] = aval;
b[k] = bval;
c[k] = cval;
d[k] = dval;
}
template<class S, class T> inline S chmax(S &a, T b){
if(a<b){
a=b;
}
return a;
}
template<class T> struct Comb{
int mem_fact;
T *factri;
T *ifactri;
Comb(){
mem_fact = 0;
}
inline void expand_fact(int k){
if(k <= mem_fact){
return;
}
chmax(k, 2* mem_fact);
if(mem_fact == 0){
int i;
factri = (T*)malloc(k * sizeof(T));
ifactri = (T*)malloc(k * sizeof(T));
factri[0] = 1;
for(i=(1);i<(k);i++){
factri[i] = i * factri[i-1];
}
ifactri[k-1] = 1 / factri[k-1];
for(i=(k-1)-1;i>=(0);i--){
ifactri[i] = (i+1) * ifactri[i+1];
}
}
else{
int i;
factri = (T*)realloc(factri, k * sizeof(T));
ifactri = (T*)realloc(ifactri, k * sizeof(T));
for(i=(mem_fact);i<(k);i++){
factri[i] = i * factri[i-1];
}
ifactri[k-1] = 1 / factri[k-1];
for(i=(k-1)-1;i>=(mem_fact);i--){
ifactri[i] = (i+1) * ifactri[i+1];
}
}
mem_fact = k;
}
inline T fac(int k){
if(mem_fact < k+1){
expand_fact(k+1);
}
return factri[k];
}
inline T ifac(int k){
if(mem_fact < k+1){
expand_fact(k+1);
}
return ifactri[k];
}
inline T C(int a, int b){
if(b < 0 || b > a){
return 0;
}
if(mem_fact < a+1){
expand_fact(a+1);
}
return factri[a] * ifactri[b] * ifactri[a-b];
}
inline T P(int a, int b){
if(b < 0 || b > a){
return 0;
}
if(mem_fact < a+1){
expand_fact(a+1);
}
return factri[a] * ifactri[a-b];
}
inline T H(int a, int b){
if(a==0 && b==0){
return 1;
}
if(a <= 0 || b < 0){
return 0;
}
if(mem_fact < a+b){
expand_fact(a+b);
}
return C(a+b-1, b);
}
inline T Multinomial(int sz, int a[]){
int i;
int s = 0;
T res;
for(i=(0);i<(sz);i++){
s += a[i];
}
if(mem_fact < s+1){
expand_fact(s+1);
}
res = factri[s];
for(i=(0);i<(sz);i++){
res *= ifactri[a[i]];
}
return 1;
}
inline T Multinomial(int a){
return 1;
}
inline T Multinomial(int a, int b){
if(mem_fact < a+b+1){
expand_fact(a+b+1);
}
return factri[a+b] * ifactri[a] * ifactri[b];
}
inline T Multinomial(int a, int b, int c){
if(mem_fact < a+b+c+1){
expand_fact(a+b+c+1);
}
return factri[a+b+c] * ifactri[a] * ifactri[b] * ifactri[c];
}
inline T Multinomial(int a, int b, int c, int d){
if(mem_fact < a+b+c+d+1){
expand_fact(a+b+c+d+1);
}
return factri[a+b+c+d] * ifactri[a] * ifactri[b] * ifactri[c] * ifactri[d];
}
inline T Catalan(int n){
if(n < 0){
return 0;
}
if(mem_fact < 2*n+1){
expand_fact(2*n+1);
}
return factri[2*n] * ifactri[n] * ifactri[n+1];
}
inline T C_s(long long a, long long b){
long long i;
T res;
if(b < 0 || b > a){
return 0;
}
if(b > a - b){
b = a - b;
}
res = 1;
for(i=(0);i<(b);i++){
res *= a - i;
res /= i + 1;
}
return res;
}
inline T P_s(long long a, long long b){
long long i;
T res;
if(b < 0 || b > a){
return 0;
}
res = 1;
for(i=(0);i<(b);i++){
res *= a - i;
}
return res;
}
inline T per_s(long long n, long long k){
T d;
int m;
if(n < 0 || k < 0){
return 0;
}
if(n == k && k == 0){
return 1;
}
if(n == 0 || k == 0){
return 0;
}
if(k==1){
return 1;
}
if(k==2){
d = n / 2;
return d;
}
if(k==3){
d = (n-1) / 6;
m = (n-1) % 6;
if(m==0){
return 3 * d * d + d;
}
if(m==1){
return 3 * d * d + 2 * d;
}
if(m==2){
return 3 * d * d + 3 * d + 1;
}
if(m==3){
return 3 * d * d + 4 * d + 1;
}
if(m==4){
return 3 * d * d + 5 * d + 2;
}
if(m==5){
return 3 * d * d + 6 * d + 3;
}
}
assert(0 && "per_s should be k <= 3");
return -1;
}
}
;
int N;
int M;
int K;
int A[40];
int B[40];
Modint dp[41][41];
Modint nx[41][41];
Comb<Modint> c;
Modint solve(int N, int M, int A[], int tar[]){
int i, k;
int f = 0;
Modint res = 0;
Modint p;
rsortA_L(M, A, tar);
for(i=(0);i<(N+1);i++){
int j;
for(j=(0);j<(N+1);j++){
dp[i][j] = 0;
}
}
dp[N][0] = 1;
for(k=(0);k<(M);k++){
f += tar[k];
if(k==0){
p = Modint(K - A[k] + 1) / (K+1);
}
else{
p = Modint(A[k-1] - A[k]) / A[k-1];
}
for(i=(0);i<(N+1);i++){
int j;
for(j=(0);j<(N+1);j++){
nx[i][j] = 0;
}
}
for(i=(0);i<(N+1);i++){
int j;
for(j=(0);j<(N+1);j++){
if((int)dp[i][j] != 0){
int x;
for(x=(0);x<(i+1);x++){
if(f && j+x-1 < 0){
continue;
}
nx[i-x][max_L(0, j+x-1)] += dp[i][j] * c.C(i,x) * ((pow_L(p,x))) * ((pow_L((1-p),(i-x))));
}
}
}
}
for(i=(0);i<(N+1);i++){
int j;
for(j=(0);j<(N+1);j++){
dp[i][j] = nx[i][j];
}
}
}
for(i=(0);i<(N+1);i++){
int j;
for(j=(0);j<(N+1);j++){
res += dp[i][j];
}
}
return res;
}
int main(){
int i;
wmem = memarr;
int nn;
int a[40];
int t[40];
Modint res = 0;
rd(N);
rd(M);
rd(K);
{
int BUotOFBp;
for(BUotOFBp=(0);BUotOFBp<(M);BUotOFBp++){
rd(A[BUotOFBp]);
rd(B[BUotOFBp]);
}
}
for(i=(0);i<(M);i++){
int j;
nn = 0;
for(j=(0);j<(M);j++){
if(B[j] > B[i]){
arrInsert(nn, nn, a, A[j], t, 0);
}
}
arrInsert(nn, nn, a, A[i], t, 1);
res += solve(N, nn, a, t) * B[i];
}
wt_L(res);
wt_L('\n');
return 0;
}
// cLay varsion 20200813-1 [beta]
// --- original code ---
// int N, M, K, A[40], B[40];
//
// Modint dp[41][41], nx[41][41];
// Comb<Modint> c;
//
// Modint solve(int N, int M, int A[], int tar[]){
// int f = 0;
// Modint res = 0, p;
//
// rsortA(M, A, tar);
// rep(i,N+1) rep(j,N+1) dp[i][j] = 0;
// dp[N][0] = 1;
//
// rep(k,M){
// f += tar[k];
//
// if(k==0) p = Modint(K - A[k] + 1) / (K+1);
// else p = Modint(A[k-1] - A[k]) / A[k-1];
//
// rep(i,N+1) rep(j,N+1) nx[i][j] = 0;
//
// rep(i,N+1) rep(j,N+1) if((int)dp[i][j] != 0){
// rep(x,i+1){
// if(f && j+x-1 < 0) continue;
// nx[i-x][max(0,j+x-1)] += dp[i][j] * c.C(i,x) * (p ** x) * ((1-p) ** (i-x));
// }
// }
//
// rep(i,N+1) rep(j,N+1) dp[i][j] = nx[i][j];
// }
//
// rep(i,N+1) rep(j,N+1) res += dp[i][j];
// return res;
// }
//
// {
// int nn, a[40], t[40];
// Modint res = 0;
// rd(N,M,K,(A,B)(M));
// rep(i,M){
// nn = 0;
// rep(j,M) if(B[j] > B[i]) arrInsert(nn, nn, a, A[j], t, 0);
// arrInsert(nn, nn, a, A[i], t, 1);
// res += solve(N, nn, a, t) * B[i];
// }
// wt(res);
// }
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0