結果
問題 | No.1214 Market |
ユーザー | kaage |
提出日時 | 2020-08-21 18:40:35 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 6,064 bytes |
コンパイル時間 | 1,700 ms |
コンパイル使用メモリ | 136,540 KB |
実行使用メモリ | 17,600 KB |
最終ジャッジ日時 | 2024-11-14 15:03:09 |
合計ジャッジ時間 | 43,220 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | WA | - |
testcase_01 | WA | - |
testcase_02 | WA | - |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | TLE | - |
testcase_09 | TLE | - |
testcase_10 | TLE | - |
testcase_11 | TLE | - |
testcase_12 | TLE | - |
testcase_13 | TLE | - |
testcase_14 | TLE | - |
testcase_15 | TLE | - |
testcase_16 | TLE | - |
testcase_17 | TLE | - |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | WA | - |
testcase_21 | WA | - |
testcase_22 | WA | - |
testcase_23 | TLE | - |
testcase_24 | WA | - |
testcase_25 | WA | - |
testcase_26 | WA | - |
testcase_27 | WA | - |
testcase_28 | TLE | - |
testcase_29 | WA | - |
testcase_30 | WA | - |
testcase_31 | WA | - |
testcase_32 | WA | - |
testcase_33 | WA | - |
testcase_34 | WA | - |
testcase_35 | WA | - |
testcase_36 | WA | - |
testcase_37 | WA | - |
testcase_38 | WA | - |
testcase_39 | WA | - |
testcase_40 | WA | - |
testcase_41 | WA | - |
ソースコード
#line 2 "/Users/kaage/Desktop/ProgrammingWorkspace/library/other/template.hpp"#define _CRT_SECURE_NO_WARNINGS#pragma target("avx2")#pragma optimize("O3")#pragma optimize("unroll-loops")#include <algorithm>#include <bitset>#include <cassert>#include <cfloat>#include <climits>#include <cmath>#include <complex>#include <ctime>#include <deque>#include <fstream>#include <functional>#include <iomanip>#include <iostream>#include <iterator>#include <list>#include <map>#include <memory>#include <queue>#include <random>#include <set>#include <stack>#include <string>#include <string.h>#include <unordered_map>#include <unordered_set>#include <utility>#include <vector>#define rep(i,n) for(int i=0;i<(n);i++)#define REP(i,n) for(int i=1;i<=(n);i++)#define all(V) V.begin(),V.end()typedef unsigned int uint;typedef long long lint;typedef unsigned long long ulint;typedef std::pair<int, int> P;typedef std::pair<lint, lint> LP;constexpr int INF = INT_MAX/2;constexpr lint LINF = LLONG_MAX/2;constexpr double eps = DBL_EPSILON;constexpr double PI=3.141592653589793238462643383279;template<class T>class prique :public std::priority_queue<T, std::vector<T>, std::greater<T>> {};template <class T, class U>inline bool chmax(T& lhs, const U& rhs) {if (lhs < rhs) {lhs = rhs;return 1;}return 0;}template <class T, class U>inline bool chmin(T& lhs, const U& rhs) {if (lhs > rhs) {lhs = rhs;return 1;}return 0;}inline lint gcd(lint a, lint b) {while (b) {lint c = a;a = b; b = c % b;}return a;}inline lint lcm(lint a, lint b) {return a / gcd(a, b) * b;}bool isprime(lint n) {if (n == 1)return false;for (int i = 2; i * i <= n; i++) {if (n % i == 0)return false;}return true;}template<typename T>T mypow(T a, lint b) {T res(1);while(b){if(b&1)res*=a;a*=a;b>>=1;}return res;}lint modpow(lint a, lint b, lint m) {lint res(1);while(b){if(b&1){res*=a;res%=m;}a*=a;a%=m;b>>=1;}return res;}template<typename T>void printArray(std::vector<T>& vec) {rep(i, vec.size()){std::cout << vec[i];std::cout<<(i==(int)vec.size()-1?"\n":" ");}}template<typename T>void printArray(T l, T r) {T rprev = std::prev(r);for (T i = l; i != rprev; i++) {std::cout << *i << " ";}std::cout << *rprev << std::endl;}LP extGcd(lint a,lint b) {if(b==0)return {1,0};LP s=extGcd(b,a%b);std::swap(s.first,s.second);s.second-=a/b*s.first;return s;}LP ChineseRem(const lint& b1,const lint& m1,const lint& b2,const lint& m2) {lint p=extGcd(m1,m2).first;lint tmp=(b2-b1)*p%m2;lint r=(b1+m1*tmp+m1*m2)%(m1*m2);return std::make_pair(r,m1*m2);}template<typename F>inline constexpr decltype(auto) lambda_fix(F&& f){return [f=std::forward<F>(f)](auto&&... args){return f(f,std::forward<decltype(args)>(args)...);};}#line 3 "/Users/kaage/Desktop/ProgrammingWorkspace/library/algebraic/ModInt.hpp"class ModInt {lint value;public:static unsigned int modulo;ModInt() : value(0) {}template<typename T>ModInt(T value = 0) : value(value) {if (value < 0)value = -(lint)(-value % modulo) + modulo;this->value = value % modulo;}static inline void setMod(const unsigned int& mod){modulo=mod;}inline ModInt inv()const{return mypow(*this,modulo-2);}inline operator int()const { return value; }inline ModInt& operator+=(const ModInt& x) {value += x.value;if (value >= modulo)value -= modulo;return *this;}inline ModInt& operator++() {if (value == modulo - 1)value = 0;else value++;return *this;}inline ModInt operator-()const {return ModInt(0) -= *this;}inline ModInt& operator-=(const ModInt& x) {value -= x.value;if (value < 0)value += modulo;return *this;}inline ModInt& operator--() {if (value == 0)value = modulo - 1;else value--;return *this;}inline ModInt& operator*=(const ModInt& x) {value = value * x.value % modulo;return *this;}inline ModInt& operator/=(const ModInt& rhs) {return *this*=rhs.inv();}template<typename T> ModInt operator+(const T& rhs)const { return ModInt(*this) += rhs; }template<typename T> ModInt& operator+=(const T& rhs) { return operator+=(ModInt(rhs)); }template<typename T> ModInt operator-(const T& rhs)const { return ModInt(*this) -= rhs; }template<typename T> ModInt& operator-=(const T& rhs) { return operator-=(ModInt(rhs)); }template<typename T> ModInt operator*(const T& rhs)const { return ModInt(*this) *= rhs; }template<typename T> ModInt& operator*=(const T& rhs) { return operator*=(ModInt(rhs)); }template<typename T> ModInt operator/(const T& rhs)const { return ModInt(*this) /= rhs; }template<typename T> ModInt& operator/=(const T& rhs) { return operator/=(ModInt(rhs)); }};unsigned int ModInt::modulo=1000000007;std::istream& operator>>(std::istream& ist, ModInt& x) {lint a;ist >> a;x = a;return ist;}#line 3 "main.cpp"int n,m,k,a[45],b[45];ModInt dp[45][45][45],fact[45],inv[45];ModInt comb(int a,int b){return fact[a]*inv[b]*inv[a-b];}int main(){ModInt::setMod(1000000007);std::cin>>n>>m>>k;REP(i,m)std::cin>>a[i]>>b[i];ModInt ans=0;REP(i,m)ans+=b[i];ans*=mypow(ModInt(k+1),n);fact[0]=1;rep(i,44)fact[i+1]=fact[i]*(i+1);inv[44]=ModInt(1)/fact[44];for(int i=43;i>=0;i--)inv[i]=inv[i+1]*(i+1);REP(i,m){std::vector<int> vec={0,k+1};std::unordered_map<int,int> mp;REP(j,m){if(b[j]>=b[i]){vec.emplace_back(a[j]);mp[a[j]]++;}}std::sort(all(vec));vec.erase(std::unique(all(vec)),vec.end());rep(j,vec.size()){rep(k,n+1){rep(l,n+1)dp[j][k][l]=0;}}dp[0][0][n]=1;rep(j,vec.size()-1){rep(k,n+1){rep(l,n+1){rep(o,l+1){if(a[i]<=vec[j]&&k-o+mp[vec[j]]<=0)break;dp[j+1][std::max(0,k-o+mp[vec[j]])][l-o]+=dp[j][k][l]*comb(l,o)*mypow(ModInt(vec[j+1]-vec[j]),o);}}}}ModInt sum=0;REP(j,n)sum+=dp[vec.size()-1][j][0];std::cout<<sum<<std::endl;ans-=sum*b[i];}std::cout<<ans/mypow(ModInt(k+1),n)<<std::endl;}