結果
問題 | No.1214 Market |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#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 Ucval, 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);// }