题目链接

Atcoder 的题目就是好 思维难度高到我都不会

题目描述

在网格图上,给 $X_1 \leq X_2 < X_3 \leq X_4 < X_5 \leq X_6$和$Y_1 \leq Y_2 < Y_3 \leq Y_4 < Y_5 \leq Y_6$,需要选择 $(p,q) \in [X_1,X_2]\times[Y_1,Y_2],(s,t) \in [X_3,X_4]\times[Y_3,Y_4],(u,v)\in [X_5,X_6]\times[Y_5,Y_6]$,以及一条从 $(p,q)$ 经过 $(s,t)$ 到达 $(u,v)$ 的只能向上或向右的路径。两个方案不同当且仅当 $(p,q),(s,t),(u,v)$ 选择不同或者路径不同。求方案数

$X,Y \leq 10^6$

题解

我们先分成几个小问题解决:

点到点的方案数

$(0,0) \to (x,y)$:方案数显然是$\binom {x+y}{x}$ 。

点到面的方案数

先看最简单的情形:$(0,0) \to [0,X]\times [0,Y]$

我们先注意到对于组合数的上下指标求和 有这两种形式:

$$ \sum_{i=0}^n \binom{x+i}{x} = \binom{x+n+1}{x+1} $$

$$ \sum_{i=1}^n \binom{x+i}{i} = \binom{x+n+1}{n+1}-1 $$

大概都是用组合数的简单递推形式搞。

$$ \begin{align*}&\sum_{i=0}^X\sum_{j=0}^Y \binom{i+j}{i}\\&= \sum_{i=0}^X \binom{i+Y+1}{i+1}\\&= \binom{X+Y+2}{X+1}-1\end{align*} $$

如果是 $(0,0) \to [X_1,X_2]\times[Y_1,Y_2]$呢?只需要用二维前缀和的思想就好了。

面到面

考虑点到面的情况实际上可以拆成点到四个点的方案数(带权)。所以面到面可以转化为 $16$ 对点到点。

这个题

暴力的想法是把第一个和第三个面化为 $4$ 个点 那么枚举 $16$ 种可能 再枚举中间的点 就可以计算。

考虑我们先随便确定一条经过中间面的路径 发现这个路径对答案的贡献就是和中间面交的长度。

考虑进入的点是 $(x,y)$ 出去的点是 $(a,b)$ 那么贡献 $a-x+b-y+1$ 所以就可以变成枚举每一个入点 考虑这个入点方案会被计算多少次(强制路径经过这个点的方案) 然后有个系数 $-x-y$ 出点类似 系数是 $a+b+1$

不理解可以看看代码

#include<bits/stdc++.h>

#define fi first
#define se second
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 5e6 + 5;
const int ha = 1e9 + 7;

inline int qpow(int a,int n=ha-2){
    int res = 1;
    while(n){
        if(n & 1) res = 1ll*res*a%ha;
        a = 1ll*a*a%ha;
        n >>= 1;
    }
    return res;
}

int fac[MAXN],inv[MAXN];

inline void prework(){
    fac[0] = 1;FOR(i,1,MAXN-1) fac[i] = 1ll*fac[i-1]*i%ha;
    inv[MAXN-1] = qpow(fac[MAXN-1]);
    ROF(i,MAXN-2,0) inv[i] = 1ll*inv[i+1]*(i+1)%ha;
}

inline int C(int n,int m){
    if(n < m) return 0;
    if(!m) return 1;
    return 1ll*fac[n]*inv[m]%ha*inv[n-m]%ha;
}

inline int calc1(int x,int y){// (0,0) 到 (x,y)
    if(x < 0 || y < 0) return 0;
    return C(x+y,x);
}

inline int calc2(int x,int y){ // (0,0) 到 ([0,x],[0,y])
    return (calc1(x+1,y+1)+ha-1)%ha;
}

inline int calc3(int x1,int x2,int y1,int y2){// (0,0) 到 ([x1,x2],[y1,y2])
    int res = calc1(x2+1,y2+1);
    (res += ha-calc1(x2+1,y1)) %= ha;
    (res += ha-calc1(x1,y2+1)) %= ha;
    (res += calc1(x1,y1)) %= ha;
    return res;
}

inline int calc4(int x,int y,int x1,int x2,int y1,int y2){// (x,y) 到 ([x1,x2],[y1,y2])
    return std::min(x1,x2) >= x && std::min(y1,y2) >= y ? calc3(x1-x,x2-x,y1-y,y2-y) : calc3(x-x2,x-x1,y-y2,y-y1);
    // 实际应用是要判包含的 但是这个题不会
}
int x[233],y[233];
int main(){
    prework();
    FOR(i,1,6) scanf("%d",x+i);
    FOR(i,1,6) scanf("%d",y+i);
    int ans = 0;
    FOR(i,x[3],x[4]){
        (ans += 1ll*(ha-(i+y[3])%ha)*calc4(i,y[3]-1,x[1],x[2],y[1],y[2])%ha*calc4(i,y[3],x[5],x[6],y[5],y[6])%ha) %= ha;
        (ans += 1ll*(i+y[4]+1)%ha*calc4(i,y[4],x[1],x[2],y[1],y[2])%ha*calc4(i,y[4]+1,x[5],x[6],y[5],y[6])%ha) %= ha;
    }
    FOR(i,y[3],y[4]){
        (ans += 1ll*(ha-(i+x[3])%ha)*calc4(x[3]-1,i,x[1],x[2],y[1],y[2])%ha*calc4(x[3],i,x[5],x[6],y[5],y[6])%ha) %= ha;
        (ans += 1ll*(x[4]+i+1)%ha*calc4(x[4],i,x[1],x[2],y[1],y[2])%ha*calc4(x[4]+1,i,x[5],x[6],y[5],y[6])%ha) %= ha;
    }
    printf("%d\n",ans);
    return 0;
}
Last modification:May 19th, 2020 at 02:06 pm
如果觉得我的文章对你有用,请随意赞赏