Research Rover

Time Limit: 25 Sec  Memory Limit: 256 MB

Description

　　

Input

　　

Output

　　仅一行一个整数表示答案。

Sample Input

　　3 3 2 11

　　2 1

　　2 3

Sample Output

　　333333342

　　

HINT

　　

Main idea

　　从(1,1)走到(n,m)，每次可以向右或向下走一步，有K个特殊点，初始有一个权S，每经过一个特殊点S=(S+1)/2，询问到(n,m)的S的期望。

Solution

　　我们显然想到了DP，研究一下题目，发现可以按照到达目标之后S的值分类，显然S的取值只和经过特殊点的个数相关。并且由于每经过一个特殊点，S的值就会/2，那么显然只有log2(S)种取值，所以我们可以去考虑一个O(K^2log(S))的做法。

　　首先，从起点走到终点的总方案数是：，我们可以将终点也当做特殊点，那么就可以令 f[i][j] 表示到了第 i 个目标点，经过 j 个目标点的方案数。

　　那么我们可以考虑容斥：。

　　那么写成表达式也就是：

　　其中：，计算方法显然和计算总方案一样，运用组合数。（组合数计算的时候求一下乘法逆元和阶乘逆元即可）

　　这样的话就可以算出到终点经过 i 个特殊点的方案、乘上对应的S的值、然后计算一下、再乘上总方案的乘法逆元就是答案了。

　　效率就是O(k^2 * log(S))，就可以解决这道题啦。\(≧▽≦)/

Code

1 #include
      
           2 #include
       
            3 #include
        
             4 #include
         
              5 #include
          
               6 #include
           
             7 using namespace std; 8 typedef long long s64; 9 const int ONE = 200005; 10 const int INF = 214783640; 11 const int MOD = 1e9+7; 12 13 int Mod = MOD; 14 int n,m,K,S; 15 int f[ONE][30]; 16 int Jc[ONE],inv[ONE]; 17 int A[30],a_num; 18 int Up; 19 20 struct power 21 { 22 int x,y; 23 }a[ONE]; 24 25 int cmp(const power &a,const power &b) 26 { 27 return a.x+a.y < b.x+b.y; 28 } 29 30 int get() 31 { 32 int res,Q=1; char c; 33 while( (c=getchar())<48 || c>57) 34 if(c=='-')Q=-1; 35 if(Q) res=c-48; 36 while((c=getchar())>=48 && c<=57) 37 res=res*10+c-48; 38 return res*Q; 39 } 40 41 namespace D 42 { 43 int Quickpow(int a,int b) 44 { 45 int res=1; 46 while(b) 47 { 48 if(b&1) res=(s64)res*a%MOD; 49 a=(s64)a*a%MOD; 50 b>>=1; 51 } 52 return res; 53 } 54 55 void Deal_Jc(int k) 56 { 57 Jc[0]=1; 58 for(int i=1;i<=k;i++) Jc[i] = (s64)Jc[i-1]*i%MOD; 59 } 60 61 void Deal_inv(int k) 62 { 63 inv[0]=1; inv[k] = Quickpow(Jc[k],MOD-2); 64 for(int i=k-1;i>=1;i--) inv[i] = (s64)inv[i+1]*(i+1)%MOD; 65 } 66 67 void pre(int k) 68 { 69 Deal_Jc(k); Deal_inv(k); 70 } 71 } 72 int C(int n,int m) 73 { 74 return (s64)Jc[n]*inv[m]%MOD*inv[n-m]%MOD; 75 } 76 77 int ways(int i,int j) 78 { 79 return C(a[j].x+a[j].y-a[i].x-a[i].y, a[j].x-a[i].x); 80 } 81 82 void Moit(int &a) 83 { 84 if(a<0) a+=MOD; 85 if(a>MOD) a-=MOD; 86 } 87 88 int main() 89 { 90 n=get(); m=get(); K=get(); S=get(); 91 92 A[0]=S; for(a_num=1;a_num<=24;a_num++) S=(S+1)/2, A[a_num]=S; 93 D::pre(n+m); 94 95 for(int i=1;i<=K;i++) 96 { 97 a[i].x=get(); a[i].y=get(); 98 } 99 a[++K].x = n; a[K].y = m;100 sort(a+1,a+K+1,cmp);101 102 for(int i=1;i<=K;i++)103 {104 for(int j=0;j