結果

問題 No.907 Continuous Kadomatu
ユーザー NyaanNyaanNyaanNyaan
提出日時 2019-10-11 23:05:23
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 938 ms / 2,000 ms
コード長 10,976 bytes
コンパイル時間 2,214 ms
コンパイル使用メモリ 192,664 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-08-16 19:29:25
合計ジャッジ時間 5,634 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 2 ms
4,384 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 6 ms
4,376 KB
testcase_06 AC 2 ms
4,380 KB
testcase_07 AC 4 ms
4,380 KB
testcase_08 AC 6 ms
4,380 KB
testcase_09 AC 4 ms
4,380 KB
testcase_10 AC 9 ms
4,380 KB
testcase_11 AC 11 ms
4,380 KB
testcase_12 AC 20 ms
4,376 KB
testcase_13 AC 22 ms
4,376 KB
testcase_14 AC 21 ms
4,380 KB
testcase_15 AC 22 ms
4,380 KB
testcase_16 AC 24 ms
4,376 KB
testcase_17 AC 24 ms
4,376 KB
testcase_18 AC 22 ms
4,376 KB
testcase_19 AC 25 ms
4,376 KB
testcase_20 AC 7 ms
4,384 KB
testcase_21 AC 2 ms
4,376 KB
testcase_22 AC 2 ms
4,376 KB
testcase_23 AC 925 ms
4,376 KB
testcase_24 AC 938 ms
4,376 KB
testcase_25 AC 2 ms
4,376 KB
testcase_26 AC 1 ms
4,380 KB
testcase_27 AC 1 ms
4,380 KB
testcase_28 AC 1 ms
4,376 KB
testcase_29 AC 1 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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();}
#endif

using 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];
  }
};

// BIT

template< 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以上となる最小のi
  int 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より大きくなる最小のi
  int 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 combination 
inline 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 permutation
inline 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 polynomial
inline 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);
  //*/
}
0