結果
| 問題 | No.907 Continuous Kadomatu |
| ユーザー |
 NyaanNyaan
|
| 提出日時 | 2019-10-11 23:05:23 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 892 ms / 2,000 ms |
| コード長 | 10,976 bytes |
| コンパイル時間 | 2,012 ms |
| コンパイル使用メモリ | 196,228 KB |
| 実行使用メモリ | 6,820 KB |
| 最終ジャッジ日時 | 2024-11-25 09:15:33 |
| 合計ジャッジ時間 | 4,870 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 5 |
| other | AC * 25 |
ソースコード
#include <bits/stdc++.h>#define whlie while#define pb push_back#define eb emplace_back#define fi first#define se second#define rep(i,N) for(int i = 0; i < (N); i++)#define repr(i,N) for(int i = (N) - 1; i >= 0; i--)#define rep1(i,N) for(int i = 1; i <= (N) ; i++)#define repr1(i,N) for(int i = (N) ; i > 0 ; i--)#define each(x,v) for(auto& x : v)#define all(v) (v).begin(),(v).end()#define sz(v) ((int)(v).size())#define vrep(v,it) for(auto it = v.begin(); it != v.end(); it++)#define vrepr(v,it) for(auto it = v.rbegin(); it != v.rend(); it++)#define ini(...) int __VA_ARGS__; in(__VA_ARGS__)#define inl(...) ll __VA_ARGS__; in(__VA_ARGS__)#define ins(...) string __VA_ARGS__; in(__VA_ARGS__)using namespace std; void solve();using ll = long long; using vl = vector<ll>;using vi = vector<int>; using vvi = vector< vector<int> >;constexpr int inf = 1001001001;constexpr ll infLL = (1LL << 61) - 1;struct IoSetupNya {IoSetupNya() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); cerr << fixed << setprecision(7);} } iosetupnya;template<typename T, typename U> inline bool amin(T &x, U y) { return (y < x) ? (x = y, true) : false; }template<typename T, typename U> inline bool amax(T &x, U y) { return (x < y) ? (x = y, true) : false; }template<typename T, typename U> ostream& operator <<(ostream& os, const pair<T, U> &p) { os << p.first << " " << p.second; return os; }template<typename T, typename U> istream& operator >>(istream& is, pair<T, U> &p) { is >> p.first >> p.second; return is; }template<typename T> ostream& operator <<(ostream& os, const vector<T> &v) { int s = (int)v.size(); rep(i,s) os << (i ? " " : "") << v[i]; return os;}template<typename T> istream& operator >>(istream& is, vector<T> &v) { for(auto &x : v) is >> x; return is; }void in(){} template <typename T,class... U> void in(T &t,U &...u){ cin >> t; in(u...);}void out(){cout << "\n";} template <typename T,class... U> void out(const T &t,const U &...u){ cout << t; if(sizeof...(u)) cout << " "; out(u...);}template<typename T>void die(T x){out(x); exit(0);}#ifdef NyaanDebug#include "NyaanDebug.h"#define trc(...) do { cerr << #__VA_ARGS__ << " = "; dbg_out(__VA_ARGS__);} while(0)#define trca(v,N) do { cerr << #v << " = "; array_out(v , N);cout << endl;} while(0)#else#define trc(...)#define trca(...)int main(){solve();}#endifusing P = pair<int,int>; using vp = vector<P>;constexpr int MOD = /**/ 1000000007; //*/ 998244353;////////////////template< int mod >struct ModInt {int x;ModInt() : x(0) {}ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}ModInt &operator+=(const ModInt &p) {if((x += p.x) >= mod) x -= mod;return *this;}ModInt &operator-=(const ModInt &p) {if((x += mod - p.x) >= mod) x -= mod;return *this;}ModInt &operator*=(const ModInt &p) {x = (int) (1LL * x * p.x % mod);return *this;}ModInt &operator/=(const ModInt &p) {*this *= p.inverse();return *this;}ModInt operator-() const { return ModInt(-x); }ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }bool operator==(const ModInt &p) const { return x == p.x; }bool operator!=(const ModInt &p) const { return x != p.x; }ModInt inverse() const {int a = x, b = mod, u = 1, v = 0, t;while(b > 0) {t = a / b;swap(a -= t * b, b);swap(u -= t * v, v);}return ModInt(u);}ModInt pow(int64_t n) const {ModInt ret(1), mul(x);while(n > 0) {if(n & 1) ret *= mul;mul *= mul;n >>= 1;}return ret;}friend ostream &operator<<(ostream &os, const ModInt &p) {return os << p.x;}friend istream &operator>>(istream &is, ModInt &a) {int64_t t;is >> t;a = ModInt< mod >(t);return (is);}static int get_mod() { return mod; }};using modint = ModInt< MOD >;template<class T>struct compress{vector<T> xs;compress(const vector<T>& v){xs.reserve(v.size());for(T x : v) xs.push_back(x);sort(xs.begin(),xs.end());xs.erase(unique(xs.begin(),xs.end()) , xs.end());}int get(const T& x){return lower_bound(xs.begin(),xs.end(),x) - xs.begin();}int size(){return xs.size();}T& operator[](int i){return xs[i];}};// BITtemplate< typename T >struct BIT {int N; int max_2beki;vector< T > data;// 初期化 1-indexedでデータを管理する 0で初期化BIT(int size){N = ++size;data.assign(N, 0);max_2beki = 1;while(max_2beki * 2 <= N) max_2beki *= 2;}// [0,k](閉区間)の総和 閉区間に注意！T sum(int k) {if(k < 0) return 0; // k<0のとき0を返すT ret = 0;for(++k; k > 0; k -= k & -k) ret += data[k];return (ret);}// [l,r](閉区間)の総和inline T sum(int l,int r){return sum(r) - sum(l-1);}// 一点取得 更新はできないことに注意inline T operator[](int k){return sum(k) - sum(k-1);}// data[k] += x;void add(int k, T x) {for(++k; k < N; k += k & -k) data[k] += x;}// imos法 [l,r]にxを加算void imos(int l,int r,T x){add(l , x); add(r + 1 , -x);}// lower_bound sum(i)がval以上となる最小のiint lower_bound(T w){if(w <= 0) return 0;int x = 0;for(int k = max_2beki; k > 0; k /= 2){if(x+k <= N - 1 && data[x + k] < w){w -= data[x + k];x += k;}}return x;}// upper_bound sum(i)がvalより大きくなる最小のiint upper_bound(T w){if(w < 0) return 0;int x = 0;for(int k = max_2beki; k > 0; k /= 2){if(x+k <= N - 1 && data[x + k] <= w){w -= data[x + k];x += k;}}return x;}};modint ume_list[] = {0,1,1,2,5,16,61,272,1385,7936,50521,353792,2702765,22368256,199360981,903757305,391512012,865341513,879658613,884909216,185644928,18463610,907695790,398885199,955348527,757634389,616527580,752102598,437003601,659646373,446171710,278798431,339890119,778831298,595888523,250748685,312030296,717149364,260387681,605905908,89434740,824092703,981825866,999288437,860527213,814956207,803806388,68280442,486231764,752033767,376213479,200684441,269721275,303036225,434494262,277061441,725762301,175754891,197414470,480791678,433302643,179476197,900506713,88618454,634392057,690746113,702885516,912518442,228146884,39880972,569787174,774160419,22006719,233702287,834899748,241573864,428915130,672467393,216227893,114856640,399447831,61141729,279493330,817775454,508835028,558065528,321034908,384291120,277791859,450315787,623030117,105648435,65220308,955684959,383909961,916746845,443314666,36412558,259420858,858778549,526743537,70455532,290130288,514024747,573245806,190340669,672274684,715158268,857951714,474580162,234632272,219885682,399956945,587387257,75873532,339137376,405624954,298585426,207680858,106414762,176718394,809762763,77981714,238863427,556490092,821130815,411878453,909019958,617068074,917911821,48886392,808816315,316065110,107703770,123308041,794991292,638992554,820014954,56027216,38942270,429595636,736577747,234410779,319599713,466783253,991592712,931593562,98114360,709259974,843468581,501678911,939184815,221492430,171878963,393718138,736947782,878206316,314574973,586837472,975431081,525300170,600366179,977768616,270571454,315609022,999695529,568247191,50647628,813144444,330607637,724943311,679525382,265089472,500061061,462933212,151599325,1574760,778073008,172389390,602410222,501932829,563814612,231720934,365009707,245757736,574627061,754343207,447652458,214933637,453937124,851974883,562321946,65170568,573948740,19925103,157006495,492696516,38412688,374145341,59083779,56414484};vector<ll> fac,finv,inv;void COMinit(int MAX) {MAX++;fac.resize(MAX , 0);finv.resize(MAX , 0);inv.resize(MAX , 0);fac[0] = fac[1] = finv[0] = finv[1] = inv[1] = 1;for (int i = 2; i < MAX; i++){fac[i] = fac[i - 1] * i % MOD;inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;finv[i] = finv[i - 1] * inv[i] % MOD;}}// nCk combinationinline long long COM(int n,int k){if(n < k || k < 0 || n < 0) return 0;else return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;}// nPk permutationinline long long PER(int n,int k){if (n < k || k < 0 || n < 0) return 0;else return (fac[n] * finv[n - k]) % MOD;}// nHk homogeneous polynomialinline long long HGP(int n,int k){if(n == 0 && k == 0) return 1; //問題依存?else if(n < 1 || k < 0) return 0;else return fac[n + k - 1] * (finv[k] * finv[n - 1] % MOD) % MOD;}void solve(){/**/ini(N); vi A(N) , B(N); rep(i,N) in(A[i],B[i]);COMinit(N + 1);vi unzip;rep(i,N) {unzip.pb(A[i]); unzip.pb(B[i]); }compress<int> zip(unzip);// dp[a][i] i <= x <= jである確率vector<BIT<modint> >dp(N , BIT<modint>(zip.size())) ,ep(N , BIT<modint>(zip.size()));// 初期化{int l = zip.get(A[0]) , r = zip.get(B[0]);for(int i = l; i <= r - 1; i++){//dp[0].add(i , modint(1) * (zip[i+1] - zip[i]) / (B[0] - A[0]));dp[0].add(i , modint(1) * (zip[i+1] - zip[i]) / (B[0] - A[0]));}}rep1(i,N-1){trc(i);int l = zip.get(A[i]) , r = zip.get(B[i]);trc(l,r);for(int idx = l; idx <= r - 1; idx++){trc(idx);modint per_d = (i % 2) ?dp[i-1].sum(0,idx-1) + ep[i-1].sum(0,idx-1) :dp[i-1].sum(idx+1,zip.size()-1) + ep[i-1].sum(idx+1,zip.size()-1);modint per_e = 0 , cur_per = 1;for(int xx = i - 1; xx >= 0; xx--){int cl = zip.get(A[xx + 1]) , cr = zip.get(B[xx + 1]);cl = max(idx , cl) , cr = min(idx + 1 , cr);if(cl >= cr) break;cur_per *= (zip[cr] - zip[cl]);cur_per /= (B[xx + 1] - A[xx + 1]);trc(cl , cr , ume_list[i-xx+1] , fac[i-xx+1] , cur_per);per_e += dp[xx][idx] * cur_per * ume_list[i-xx+1] / fac[i - xx + 1];}trc(per_e);dp[i].add(idx , per_d * (zip[idx+1] - zip[idx]) / (B[i]-A[i]) );ep[i].add(idx , per_e );}}rep(h,N) rep(i,zip.size()) trc(h,i,dp[h][i],ep[h][i]);//cerr << h<<" "<<i<<" "<<dp[h][i] << " " << ep[h][i] << endl;trc("hoge");modint ans = dp[N-1].sum(0 , zip.size()-1) + ep[N-1].sum(zip.size()-1);out(ans);//*/}