fork download
copy 
  1. /******************************
  2. *    author : @marvinthang    *
  3. *    date : 07 / 02 / 2022    *
  4. ******************************/
  5.  
  6. #include <bits/stdc++.h>
  7.  
  8. using namespace std;
  9.  
  10. #define  superspeed  ios_base::sync_with_stdio(false); cin.tie(nullptr); // cout.tie(nullptr);
  11. #define  file(name)  if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }
  12.  
  13. template <class U, class V> ostream & operator << (ostream& out, const pair<U, V> &p) { return out << '(' << p.first << ", " << p.second << ')'; }
  14. template <class T> ostream & operator << (ostream &out, const vector<T> &vt) { out << '{'; for (size_t i = 0; i + 1 < vt.size(); i++) out << vt[i] << ", "; if (!vt.empty()) out << vt.back(); return out << '}'; }
  15.  
  16. const 		int MOD = 1e9 + 7;
  17. const     double PI = 3.1415926535897932384626433832795; // acos(-1.0); atan(-1.0);
  18. const     int dir[] = {0, 1, 0, -1, 0}; // {0, 1, 1, -1, -1, 1, 0, -1, 0};
  19. const  long long oo = 1e18;
  20. const       int MAX = 303;
  21.  
  22. namespace Mod {
  23.  
  24.     const int MOD = 1e9 + 7;
  25.     int sum(const int &x, const int &y){
  26.         int res = x + y;
  27.         if (res >= MOD) res -= MOD;
  28.         return res;
  29.     }
  30.  
  31.     int diff(const int &x, const int &y){
  32.         int res = x - y;
  33.         if (res < 0) res += MOD;
  34.         return res;
  35.     }
  36.  
  37.     void add(int &x, const int &y){
  38.         x += y;
  39.         if (x >= MOD) x -= MOD;
  40.     }
  41.  
  42.     void sub(int &x, const int &y){
  43.         x -= y;
  44.         if (x < 0) x += MOD;
  45.     }
  46.  
  47.     void mul(int &x, const int &y){
  48.         x = 1LL * x * y % MOD; 
  49.     }
  50.  
  51.     int MUL(int x, int y){
  52.         return 1LL * x * y % MOD;
  53.     }
  54.  
  55.     int Pow(int a, int n){
  56.         if (n == 0) return 1;
  57.         if (n == 1) return a;
  58.         int Res = Pow(a, n >> 1);
  59.         mul(Res, Res);
  60.         if (n & 1) return MUL(Res, a);
  61.         return Res;
  62.     }
  63.  
  64.     void Div(int &a, const int &b){
  65.         mul(a, Pow(b, MOD - 2));
  66.     }
  67.  
  68.     int DIV(int a, int b){
  69.         return MUL(a, Pow(b, MOD - 2));
  70.     }
  71.  
  72.     inline void fasterLLDivMod(unsigned long long x, unsigned y, unsigned &out_d, unsigned &out_m) {
  73.         unsigned xh = (unsigned)(x >> 32), xl = (unsigned)x, d, m;
  74.         #ifdef __GNUC__
  75.         asm(
  76.             "divl %4 \n\t"
  77.             : "=a" (d), "=d" (m)
  78.             : "d" (xh), "a" (xl), "r" (y)
  79.         );
  80.         #else
  81.         __asm {
  82.             mov edx, dword ptr[xh];
  83.             mov eax, dword ptr[xl];
  84.             div dword ptr[y];
  85.             mov dword ptr[d], eax;
  86.             mov dword ptr[m], edx;
  87.         };
  88.         #endif
  89.         out_d = d; out_m = m;
  90.     }
  91.  
  92.     template <int MOD>
  93.     struct ModInt {
  94.  
  95.         unsigned int val;
  96.  
  97.         ModInt(): val(0) { }
  98.         ModInt(const long long &x) { *this = x; }
  99.  
  100.         ModInt & normalize(const unsigned int &v) {
  101.             val = v >= MOD ? v - MOD : v;
  102.             return *this;
  103.         }
  104.  
  105.         bool operator ! () { return !val; }
  106.  
  107.         ModInt & operator = (const ModInt &x) { val = x.val; return *this; }
  108.         ModInt & operator = (const long long &x) { return normalize(x % MOD + MOD); }
  109.  
  110.         ModInt operator - () const { return normalize(MOD - val); }
  111.  
  112.         ModInt & operator += (const ModInt &other) { return normalize(val + other.val); }
  113.         ModInt & operator -= (const ModInt &other) { return normalize(val + MOD - other.val); }
  114.         ModInt & operator /= (const ModInt &other) { return *this *= other.inv(); }
  115.         ModInt & operator ^= (const ModInt &n) { return *this = *this ^ n; }
  116.         ModInt & operator ^= (const long long &n) { return *this = *this ^ n; }
  117.  
  118.         ModInt & operator *= (const ModInt &other) {
  119.             unsigned dummy;
  120.             fasterLLDivMod((unsigned long long) val * other.val, MOD, dummy, val);
  121.             return *this;
  122.         }
  123.  
  124.         ModInt operator + (const ModInt &other) const { return ModInt(*this) += other; }
  125.         ModInt operator - (const ModInt &other) const { return ModInt(*this) -= other; }
  126.         ModInt operator * (const ModInt &other) const { return ModInt(*this) *= other; }
  127.         ModInt operator / (const ModInt &other) const { return ModInt(*this) /= other; }
  128.  
  129.         ModInt pow(const ModInt &Exp) const {
  130.             ModInt res = 1, a = *this;
  131.             int n = Exp.val;
  132.             while (n) {
  133.                 if (n & 1) res = res * a;
  134.                 a = a * a;
  135.                 n >>= 1;
  136.             }
  137.             return res;
  138.         }
  139.  
  140.         ModInt pow(long long Exp) const {
  141.             assert(Exp >= 0);
  142.             ModInt res = 1, a = *this;
  143.             while (Exp) {
  144.                 if (Exp & 1) res = res * a;
  145.                 a = a * a;
  146.                 Exp >>= 1;
  147.             }
  148.             return res;
  149.         }
  150.  
  151.         ModInt inv() const { return pow(MOD - 2); }
  152.  
  153.         ModInt & operator ++() { return *this += 1; }
  154.         ModInt & operator --() { return *this -= 1; }
  155.         ModInt operator ++(int) { ModInt old = *this; operator ++(); return old; }
  156.         ModInt operator --(int) { ModInt old = *this; operator --(); return old; }
  157.  
  158.         friend ModInt operator + (const long long &x, const ModInt &y) { return ModInt(x) + y; }
  159.         friend ModInt operator - (const long long &x, const ModInt &y) { return ModInt(x) - y; }
  160.         friend ModInt operator * (const long long &x, const ModInt &y) { return ModInt(x) * y; }
  161.         friend ModInt operator / (const long long &x, const ModInt &y) { return ModInt(x) / y; }
  162.         friend ostream & operator << (ostream &out, const ModInt &x) { return out << x.val; }
  163.         friend istream & operator >> (istream &in, ModInt &x) { long long a; in >> a; x = a; return in; }
  164.  
  165.         bool operator < (const ModInt &other) const { return val < other.val; }
  166.         bool operator > (const ModInt &other) const { return val > other.val; }
  167.         bool operator <= (const ModInt &other) const { return val <= other.val; }
  168.         bool operator >= (const ModInt &other) const { return val >= other.val; }
  169.         bool operator == (const ModInt &other) const { return val == other.val; }
  170.         bool operator != (const ModInt &other) const { return val != other.val; }
  171.         explicit operator bool() const{ return val; }
  172.  
  173.         ModInt operator >>= (const int &x) const { return normalize((int) val >> x); }
  174.         ModInt operator >> (const int &x) const { return ModInt(*this) >>= x; }
  175.         ModInt operator <<= (const int &x) const { return ModInt((long long) val << x); }
  176.         ModInt operator << (const int &x) const { return ModInt(*this) <<= x; }
  177.         ModInt operator &= (const int &x) const { return normalize((int) val & x); }
  178.         ModInt operator & (const int &x) const { return ModInt(*this) &= x; }
  179.         ModInt operator |= (const int &x) const { return ModInt((int) val | x); }
  180.         ModInt operator | (const int &x) const { return ModInt(*this) |= x; }
  181.         ModInt operator ^= (const int &x) const { return ModInt((int) val ^ x); }
  182.         ModInt operator ^ (const int &x) const { return ModInt(*this) ^= x; }
  183.         ModInt operator ~ () const { return ModInt(~val); }
  184.  
  185.         // operator int() { return val; }
  186.  
  187.     };  
  188.  
  189.     using Modular = ModInt <MOD>;
  190.  
  191. }
  192.  
  193. using namespace Mod;
  194.  
  195. int N, L[MAX], R[MAX], K;
  196. Modular f[MAX][MAX * MAX + MAX + 1];
  197. #define F(i, j) f[i][j + MAX + 1]
  198.  
  199. Modular countWay(int maxSum) {
  200. 	for (int i = 0; i <= N; ++i) 
  201. 		for (int j = -MAX; j <= maxSum; ++j) 
  202. 			F(i, j) = 0;
  203. 	F(0, 0) = 1;
  204. 	F(0, 1) = -1;
  205. 	for (int i = 0; i < N; ++i) {
  206. 		for (int j = -MAX; j <= min(maxSum, 0); ++j) {
  207. 			F(i, j) += F(i, j - 1);
  208. 			if (!F(i, j)) continue;
  209. 			F(i + 1, L[i + 1]) += F(i, j);
  210. 			F(i + 1, R[i + 1] + 1) -= F(i, j);
  211. 		}
  212. 		for (int j = 1; j <= maxSum; ++j) {
  213. 			F(i, j) += F(i, j - 1);
  214. 			if (!F(i, j)) continue;
  215. 			F(i + 1, j + L[i + 1]) += F(i, j);
  216. 			F(i + 1, j + R[i + 1] + 1) -= F(i, j);
  217. 		}
  218. 	}
  219. 	Modular res = 0;
  220. 	for (int i = -MAX; i <= maxSum; ++i) res += (F(N, i) += F(N, i - 1));
  221. 	return res;
  222. }
  223.  
  224. int main(void) {
  225.     file("hsgso20_gift");
  226. 	scanf("%d%d", &N, &K);    
  227.     for (int i = 1; i <= N; ++i) scanf("%d%d", L + i, R + i);
  228.     if (K <= -MAX) return !(printf("0\n"));
  229.     cout << countWay(K) - countWay(K - 1) << '\n';
  230.     return 0;
  231. }
  232.  
Success #stdin #stdout 0.04s 112680KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/G17TH8
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!