相关链接
题目传送门：http://codeforces.com/contest/722/problem/E
官方题解：http://codeforces.com/blog/entry/47497
中文题面：http://blog.csdn.net/aufeas/article/details/52939314
解题报告
这题在考虑如何去重的方面真的是好神啊！
定义：
$ h(i,j)$ 表示点i走到点j的方案数
$ f(i)$ 表示从起点，不经过特殊点，走到点i的方案数
$ g(i,j)$ 表示从点i出发，经过j个特殊点走到终点的方案数
$ val(i)$ 表示经过i个特殊点后剩余的值
现在考虑如何计算这四个量：
1. $ h(i,j) = C_{\Delta (x) + \Delta (y)}^{\Delta (x)}$
2. $ f(i) = h(start,i) – \sum {f(j) \cdot h(j,i)}$
3. $ g(i,j) = h(i,end) – \sum\limits_p {g(p,j) \cdot h(p,i)} – \sum\limits_{p = 1}^{j – 1} {g(i,p)}$
4. $ val(i)$ 随便预处理就好
现在考虑如何使用这四个量计算答案：
$ ans = \sum\limits_{i = 1}^k {f(i) \cdot \sum\limits_{j = 0}^{{{\log }_{2(s)}}} {g(i,j) \cdot val(j)} }$
于是我们就可以在 $ O({n^2}lo{g_2}(s))$ 的时间复杂度内解决这个问题啦！
Code
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 2000+9;
const int M = 200000+9;
const int MOD = 1000000007;
const int L = 25;
int n,m,tot,cnt,K,S,tag,POW[M],REV[M];
int ans,val[L],vout[L],g[N][L],f[N];
struct Point{
int x,y;
inline bool operator < (const Point &B) const {
return x < B.x || (x == B.x && y < B.y);
}
inline bool operator <= (const Point &B) {
return x <= B.x && y <= B.y;
}
}p[N];
inline int read() {
char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}
inline int Pow(int w, int t) {
int ret = 1;
while (t) {
if (t & 1) ret = (LL)ret * w % MOD;
w = (LL)w * w % MOD; t >>= 1;
}
return ret;
}
inline void prework() {
for (int w=S;w>1;w=ceil(w*0.5))
val[tot++] = w;
val[tot] = 1;
POW[0] = REV[0] = 1;
for (int i=1;i<M;i++)
POW[i] = (LL)POW[i-1] * i % MOD;
REV[M-1] = Pow(POW[M-1], MOD-2);
for (int i=M-2;i;i--)
REV[i] = (LL)REV[i+1] * (i+1) % MOD;
}
inline int Path(int a, int b) {
if (p[a].x > p[b].x || p[a].y > p[b].y) return 0;
else {
int x = p[b].x - p[a].x;
int y = p[b].y - p[a].y + x;
return ((LL)POW[y] * REV[x] % MOD) * REV[y-x] % MOD;
}
}
int main() {
n = read(); m = read();
K = read(); S = read();
prework();
for (int i=1,x,y;i<=K;i++) {
x = read(); y = read();
if (x == 1 && y == 1) tag++;
else if (x == n && y == m) tag++;
else p[++cnt] = (Point){x, y};
}
sort(p+1, p+1+cnt);
p[cnt+1] = (Point){n,m};
p[0] = (Point){1,1};
for (int i=cnt;i;i--) {
for (int j=0;j<=tot;j++) {
g[i][j] = Path(i, cnt+1);
for (int k=i+1;k<=cnt&&j<tot;k++) {
if (p[i] <= p[k]) {
(g[i][j] -= (LL)g[k][j] * Path(i, k) % MOD) %= MOD;
}
}
for (int k=0;k<j;k++)
(g[i][j] -= g[i][k]) %= MOD;
}
}
for (int i=1;i<=cnt;i++) {
f[i] = Path(0, i);
for (int j=1;j<i;j++) {
if (p[j] <= p[i]) {
(f[i] -= (LL)f[j] * Path(j, i) % MOD) %= MOD;
}
}
for (int j=0;j<=tot;j++)
(vout[min(tot,j+1)] += (LL)f[i] * g[i][j] % MOD) %= MOD;
}
vout[0] = Path(0, cnt+1);
for (int j=1;j<=tot;j++)
(vout[0] -= vout[j]) %= MOD;
for (int j=tag,tmp;j;j--) {
tmp = vout[tot];
for (int i=tot;i;i--)
vout[i] = vout[i-1];
vout[0] = 0;
vout[tot] = (vout[tot] + tmp) % MOD;
}
for (int i=0;i<=tot;i++)
(ans += (LL)vout[i] * val[i] % MOD) %= MOD;
ans = (LL)ans * Pow(Path(0, cnt+1), MOD-2) % MOD;
printf("%d\n",(ans+MOD)%MOD);
return 0;
}
121051 303292Yay google is my king helped me to locate this wonderful web web site ! . 465042
290502 519705Youre so cool! I dont suppose Ive read anything in this way before. So nice to uncover somebody with some original ideas on this topic. realy appreciate starting this up. this superb internet site is something that is needed over the internet, a person if we do originality. valuable work for bringing something new towards the internet! 823063
344418 114620Yay google is my world beater assisted me to locate this great web website ! . 975923
304382 205258How significantly of an significant content, keep on penning significant other 302901
457929 969211I got what you intend,bookmarked , really decent internet internet site . 830276
620816 963595hello!,I genuinely like your writing very a great deal! percentage we maintain up a correspondence extra about your write-up on AOL? I want an expert on this area to unravel my difficulty. May possibly be that is you! Taking a appear forward to peer you. 55270
393661 594909Aw, this was an exceptionally nice post. In concept I would like to place in writing such as this moreover – spending time and actual effort to create a superb article but so what can I say I procrastinate alot by means of no indicates uncover a way to go completed. 589258
559480 14415Hmm is anyone else experiencing issues with the images on this blog loading? Im trying to uncover out if its a difficulty on my end or if it is the weblog. Any responses would be greatly appreciated. 401463
426194 549113The the next occasion Someone said a weblog, Hopefully so it doesnt disappoint me approximately this. What im saying is, I know it was my choice to read, but I really thought youd have something interesting to express. All I hear is often numerous whining about something which you could fix in the event you werent too busy looking for attention. 515541
671148 273725As I website owner I conceive the content material here is rattling excellent , thanks for your efforts. 9491
709399 720885You could certainly see your skills within the work you write. The world hopes for far more passionate writers like you who arent afraid to say how they believe. At all times follow your heart 913892
419362 619886Does your weblog have a contact page? Im having a tough time locating it but, Id like to send you an e-mail. Ive got some suggestions for your blog you may be interested in hearing. Either way, fantastic site and I appear forward to seeing it expand over time. 161675
924834 798638Its difficult to get knowledgeable folks with this topic, but the truth is could be seen as do you know what youre referring to! Thanks 696541