题目大意
给出一张 (ncdot m) 的图,图上有 (k) 个特殊点,在初始点有一个贡献 (t) 每经过一个特殊点会导致贡献变为 (lceilfrac{t}{2} ceil).求到 ((n,m)) 时的期望贡献.
分析
(n,m) 的范围都有 (10^5) 显然不能 (mathcal{O}(nm)) 的 dp,考虑只会在特殊点时贡献才会改变,所以用 (f_{i,j}) 表示终点在第 (i) 个点,总共经过了 (j) 个点的方案数.这个东西看起来是 (k^2) 的,而且转移也需要 (mathcal{O}(k)),时间复杂度 (mathcal{O}(k^3)) 不能过.但是一个数经过了 (log) 次除二向上取整后就会变成 (1),所以对于 (f_{i,j}(log_2t<j)) 的方案是没有用的,所以时间复杂度就变成了 (mathcal{k^2log_2t}) 可以通过本题.
下面考虑如何转移 (f_{i,j}),因为在计算 (x_i,y_i) 这个点时需要把所以 (x_jleq x_iland y_jleq y_i) 的点全部计算出来,所以要先对所有点按 (x) 的大小((y) 的大小)排序.但是这个 (f_{i,j}) 的转移好像还是很麻烦,不如把 (f_{i,j}) 所代表的意义改成到第 (i) 个点时至少经过 (j) 个特殊点的方案数.那么转移方程就是:
对于第 (i) 个特殊点经过恰好 (j) 次的方案数就是 (f_{i,j}-f_{i,j+1}).
然后会发现第一个样例就过不去.
在最后的贡献中 ((1,1) o(2,1) o(2,2) o(2,3) o(3,3)) 会计算两次,但是如果 (f_{k,j}) 表示的是第 (k) 个点时恰好经过 (j) 个特殊点的方案数,那么是对的.所以需要在每次计算出至少的方案数后直接计算出恰好的方案数.
代码
#include<bits/stdc++.h>
#define REP(i,first,last) for(int i=first;i<=last;++i)
#define DOW(i,first,last) for(int i=first;i>=last;--i)
using namespace std;
const int MAXN=2005;
const int MAXNUM=1e6+5;
const long long MOD=1e9+7;
long long Pow(long long a,long long b,long long mod=MOD)
{
long long result=1;
while(b)
{
if(b&1)
{
result*=a;
result%=mod;
}
a*=a;
a%=mod;
b/=2;
}
return result;
}
#define INV(a) Pow(a,MOD-2)
long long fac[MAXNUM],inv[MAXNUM];
void PreCom()
{
fac[0]=1;
REP(i,1,MAXNUM-1)
{
fac[i]=fac[i-1]*i%MOD;
}
inv[MAXNUM-1]=INV(fac[MAXNUM-1]);
DOW(i,MAXNUM-2,0)
{
inv[i]=inv[i+1]*(i+1)%MOD;
}
}
long long C(int n,int m)
{
if(n<m)
{
return 0;
}
return fac[n]*inv[m]%MOD*inv[n-m]%MOD;
}
int n,m,k,s;
struct Point
{
int x,y;
}point[MAXN];
bool Cmp(Point a,Point b)
{
if(a.x==b.x)
{
return a.y<b.y;
}
return a.x<b.x;
}
long long f[MAXN][23];
int arr[23];
int main()
{
scanf("%d%d%d%d",&n,&m,&k,&s);
PreCom();//预处理组合数
point[0].x=1;
point[0].y=1;
REP(i,1,k)
{
scanf("%d%d",&point[i].x,&point[i].y);
}
point[k+1].x=n;
point[k+1].y=m;
sort(point+1,point+1+k,Cmp);//按 x 排序
f[0][0]=1;
REP(i,1,k+1)
{
REP(j,0,i-1)
{
if(point[j].x<=point[i].x&&point[j].y<=point[i].y)//找到可以转移过来的点
{
int len=point[i].x-point[j].x+1;
int wide=point[i].y-point[j].y+1;
long long c=C(len+wide-2,len-1);//计算两点间的路径条数
REP(p,1,22)
{
f[i][p]+=f[j][p-1]*c%MOD;//dp 至少经过 p 个特殊点的方案数
f[i][p]%=MOD;
}
}
}
REP(p,1,22)
{
f[i][p]-=f[i][p+1];//将至少经过 p 个特殊点的方案数变为恰好经过 p 个特殊点的方案数
f[i][p]+=MOD;
f[i][p]%=MOD;
}
}
arr[1]=s;
REP(i,2,21)
{
arr[i]=(arr[i-1]+1)/2;
}
long long all=C(n+m-2,n-1);
long long answer=0;
REP(i,1,21)//计算经过小于等于 log 次的方案数的贡献
{
answer+=f[k+1][i]*arr[i];
all-=f[k+1][i];
all%=MOD;
all+=MOD;
all%=MOD;
answer%=MOD;
}
answer+=all;
answer%=MOD;
printf("%lld
",answer*INV(C(n+m-2,n-1))%MOD);//计算期望并输出
return 0;
}