Time Limit: 20 Sec Memory Limit: 64 MB

Submit: 2244 Solved: 1144

[Submit][Status][Discuss]

Description

HH有个一成不变的习惯，喜欢饭后百步走。所谓百步走，就是散步，就是在一定的时间 内，走过一定的距离。 但

是同时HH又是个喜欢变化的人，所以他不会立刻沿着刚刚走来的路走回。 又因为HH是个喜欢变化的人，所以他每

天走过的路径都不完全一样，他想知道他究竟有多 少种散步的方法。 现在给你学校的地图（假设每条路的长度都

是一样的都是1），问长度为t，从给定地 点A走到给定地点B共有多少条符合条件的路径

Input

第一行：五个整数N，M，t，A，B。

N表示学校里的路口的个数

M表示学校里的 路的条数

t表示HH想要散步的距离

A表示散步的出发点

B则表示散步的终点。

接下来M行

每行一组Ai，Bi，表示从路口Ai到路口Bi有一条路。

数据保证Ai ！= Bi,但不保证任意两个路口之间至多只有一条路相连接。

路口编号从0到N -1。

同一行内所有数据均由一个空格隔开，行首行尾没有多余空格。没有多余空行。

答案模45989。

N ≤ 20，M ≤ 60，t ≤ 2^30，0 ≤ A,B

Output

一行，表示答案。

Sample Input

4 5 3 0 0

0 1

0 2

0 3

2 1

3 2

Sample Output

4

解题思路

树状数组+离线，如果将询问按照l排序，那么后面出现的与前面相同的可以替代前面的，所以记录一个nxt[i]数组，表示i这个位置往后第一个与i元素相同的元素的下标，然后将询问按照l排序，每次将此时扫到的元素的nxt在树状数组里+1。

代码

#include
    
     #include
     
      #include
      
       using namespace std;const int MAXN = 1000005;inline int rd(){    int x=0,f=1;char ch=getchar();    while(!isdigit(ch)) {
   if(ch=='-') f=-1;ch=getchar();}    while(isdigit(ch))  {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}    return x*f;}int n,m,a[MAXN],nxt[MAXN],p[MAXN],mx,f[MAXN];struct Data{    int l,r,id,ans;}data[MAXN];inline bool cmp(Data A,Data B){    if(A.l==B.l) return A.r