E - Okabe and El Psy Kongroo CodeForces - 821E

2024-04-10 03:58

本文主要是介绍E - Okabe and El Psy Kongroo CodeForces - 821E,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Okabe likes to take walks but knows that spies from the Organization could be anywhere; that’s why he wants to know how many different walks he can take in his city safely. Okabe’s city can be represented as all points (x, y) such that x and y are non-negative. Okabe starts at the origin (point (0, 0)), and needs to reach the point (k, 0). If Okabe is currently at the point (x, y), in one step he can go to (x + 1, y + 1), (x + 1, y), or (x + 1, y - 1).

Additionally, there are n horizontal line segments, the i-th of which goes from x = ai to x = bi inclusive, and is at y = ci. It is guaranteed that a1 = 0, an ≤ k ≤ bn, and ai = bi - 1 for 2 ≤ i ≤ n. The i-th line segment forces Okabe to walk with y-value in the range 0 ≤ y ≤ ci when his x value satisfies ai ≤ x ≤ bi, or else he might be spied on. This also means he is required to be under two line segments when one segment ends and another begins.

Okabe now wants to know how many walks there are from the origin to the point (k, 0) satisfying these conditions, modulo 109 + 7.

Input

The first line of input contains the integers n and k (1 ≤ n ≤ 100, 1 ≤ k ≤ 1018) — the number of segments and the destination x coordinate.

The next n lines contain three space-separated integers ai, bi, and ci (0 ≤ ai < bi ≤ 1018, 0 ≤ ci ≤ 15) — the left and right ends of a segment, and its y coordinate.

It is guaranteed that a1 = 0, an ≤ k ≤ bn, and ai = bi - 1 for 2 ≤ i ≤ n.

Output

Print the number of walks satisfying the conditions, modulo 1000000007 (109 + 7).

Example

Input
1 3
0 3 3
Output
4
Input
2 6
0 3 0
3 10 2
Output
4
Note

The graph above corresponds to sample 1. The possible walks are:

The graph above corresponds to sample 2. There is only one walk for Okabe to reach (3, 0). After this, the possible walks are:

裸的矩阵快速幂的题目,练了一练,快速幂用倍增写,不然容易萎。

using namespace std;
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define ll long longstruct matrix{ll it[21][21];
}mu;
const ll mod=1e9+7;
ll n,k;
ll a[201],b[201],c[201];
ll ans[21];
ll bef[21];
matrix st[65];
void prll(matrix xx)
{for(ll i=0;i<=20;i++){for(ll j=0;j<=20;j++){cout<<xx.it[i][j]<<" ";}puts("");}
}
matrix operator * (matrix a,matrix b)
{matrix c;for(ll i=0;i<=20;i++){for(ll j=0;j<=20;j++){c.it[i][j]=0;for(ll k=0;k<=20;k++){c.it[i][j]=(c.it[i][j]+a.it[i][k]*b.it[k][j])%mod;}}}return c;
}
matrix pow(ll x)
{matrix hh;bool flag=0;st[1]=mu;ll cnt=0;for(ll i=2;i<=64;i++)st[i]=st[i-1]*st[i-1];while(x){cnt++;if(x%2){if(!flag) hh=st[cnt];else hh=hh*st[cnt];flag=1;}x>>=1;}return hh;
}
ll tot;
int main()
{cin>>n>>k;ans[0]=1;for(ll i=1;i<=n;i++){cin>>a[i]>>b[i]>>c[i];if(b[i]>=k){b[i]=k;tot=i;break;}}n=tot;for(ll i=1;i<=n;i++){memset(mu.it,0,sizeof(mu.it));for(ll j=0;j<=c[i];j++){if(j==0){mu.it[j][0]=mu.it[j][1]=1;}elseif(j==c[i]){mu.it[j][c[i]]=mu.it[j][c[i]-1]=1;}elsemu.it[j][j-1]=mu.it[j][j]=mu.it[j][j+1]=1;}matrix hh=pow(b[i]-a[i]);for(ll j=0;j<=20;j++){bef[j]=0;for(ll k=0;k<=20;k++){   bef[j]=(bef[j]+ans[k]*hh.it[k][j])%mod;}}for(ll j=0;j<=20;j++) ans[j]=bef[j];for(ll j=c[i]+1;j<=20;j++) ans[j]=0;}cout<<ans[0]<<endl;
}

这篇关于E - Okabe and El Psy Kongroo CodeForces - 821E的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/890009

相关文章

Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E  http://codeforces.com/contest/415/problem/E 2^n个数,每次操作将其分成2^q份,对于每一份内部的数进行翻转(逆序),每次操作完后输出操作后新序列的逆序对数。 图一:  划分子问题。 图二: 分而治之,=>  合并 。 图三: 回溯:

Codeforces Round #261 (Div. 2)小记

A  XX注意最后输出满足条件,我也不知道为什么写的这么长。 #define X first#define Y secondvector<pair<int , int> > a ;int can(pair<int , int> c){return -1000 <= c.X && c.X <= 1000&& -1000 <= c.Y && c.Y <= 1000 ;}int m

Codeforces Beta Round #47 C凸包 (最终写法)

题意慢慢看。 typedef long long LL ;int cmp(double x){if(fabs(x) < 1e-8) return 0 ;return x > 0 ? 1 : -1 ;}struct point{double x , y ;point(){}point(double _x , double _y):x(_x) , y(_y){}point op

Codeforces Round #113 (Div. 2) B 判断多边形是否在凸包内

题目点击打开链接 凸多边形A, 多边形B, 判断B是否严格在A内。  注意AB有重点 。  将A,B上的点合在一起求凸包,如果凸包上的点是B的某个点,则B肯定不在A内。 或者说B上的某点在凸包的边上则也说明B不严格在A里面。 这个处理有个巧妙的方法,只需在求凸包的时候, <=  改成< 也就是说凸包一条边上的所有点都重复点都记录在凸包里面了。 另外不能去重点。 int

Codeforces 482B 线段树

求是否存在这样的n个数; m次操作,每次操作就是三个数 l ,r,val          a[l] & a[l+1] &......&a[r] = val 就是区间l---r上的与的值为val 。 也就是意味着区间[L , R] 每个数要执行 | val 操作  最后判断  a[l] & a[l+1] &......&a[r] 是否= val import ja

vue2实践:el-table实现由用户自己控制行数的动态表格

需求 项目中需要提供一个动态表单,如图: 当我点击添加时,便添加一行;点击右边的删除时,便删除这一行。 至少要有一行数据,但是没有上限。 思路 这种每一行的数据固定,但是不定行数的,很容易想到使用el-table来实现,它可以循环读取:data所绑定的数组,来生成行数据,不同的是: 1、table里面的每一个cell,需要放置一个input来支持用户编辑。 2、最后一列放置两个b

Codeforces Round 971 (Div. 4) (A~G1)

A、B题太简单,不做解释 C 对于 x y 两个方向,每一个方向至少需要 x / k 向上取整的步数,取最大值。 由于 x 方向先移动,假如 x 方向需要的步数多于 y 方向的步数,那么最后 y 方向的那一步就不需要了,答案减 1 代码 #include <iostream>#include <algorithm>#include <vector>#include <string>

Codeforces#295(Div.2)A、B(模拟+BFS)

解题报告链接:点击打开链接 C. 题目链接:点击打开链接 解题思路: 对于给定的字符串,取出现次数最多的字母(可以同时有多个)。由这些字母组成长度为n的字符串,求有多少种组合。最后用数学知识即可。 完整代码: #include <algorithm>#include <iostream>#include <cstring>#include <climits>

Codeforces Round #281 (Div. 2)A(构造+暴力模拟)

题目链接:http://codeforces.com/problemset/problem/493/A 解题思路: 暴力的判断,分三种情况去判断即可。注意如果之前已经被罚下场后,那么在后面的罚下情况不应该算在输出结果内。 完整代码: #include <algorithm>#include <iostream>#include <cstring>#include <co

Codeforces Round #182 (Div. 2)A(水题)

题目链接:http://codeforces.com/contest/302/problem/A 解题思路: 只要通过重新排列使区间内和为0即是1,否则是0. 完整代码: #include <algorithm>#include <iostream>#include <cstring>#include <complex>#include <cstdio>#inc