我是靠谱客的博主 落后高山,最近开发中收集的这篇文章主要介绍AtCoder Grand Contest 018 E - Sightseeing Plan 数学题意分析代码,觉得挺不错的,现在分享给大家,希望可以做个参考。

概述

题意

给出三个不相交的矩形区域,现在可以从每个矩形内选出一个点,求有多少条只能向上或向右走的路径满足以第一个点为起点,第三个点为终点且必然经过第二个点。
坐标范围是1000000

分析

如果直接大力推式子的话,会发现不管怎样都会有六个循环,且都不好化简。
那么接下来先给出一些结论:
C(x,y)=(x+y)!x!y! C ( x , y ) = ( x + y ) ! x ! y !

结论1:

i=0nC(i,m)=C(n,m+1) ∑ i = 0 n C ( i , m ) = C ( n , m + 1 )

证明的话可以考虑当我们要走到 (n,m+1) ( n , m + 1 ) 时,可以枚举从第m列的哪个位置走到第m+1列。

结论2

i=0nj=0mC(i,j)=C(n+1,m+1)1 ∑ i = 0 n ∑ j = 0 m C ( i , j ) = C ( n + 1 , m + 1 ) − 1

证明的话只要用两次结论1就好了。

结论3

i=x1y1j=x2y2C(i,j)=C(x2+1,y2+1)C(x2+1,y1)C(x1,y2+1)+C(x1,y1) ∑ i = x 1 y 1 ∑ j = x 2 y 2 C ( i , j ) = C ( x 2 + 1 , y 2 + 1 ) − C ( x 2 + 1 , y 1 ) − C ( x 1 , y 2 + 1 ) + C ( x 1 , y 1 )

证明的话,只要二维查分一下然后用结论2就好了。

有了结论3,现在我们就可以把第一个矩形拆成 (x2,y2),(x2,y11),(x11,y2),(x11,y11) ( x 2 , y 2 ) , ( x 2 , y 1 − 1 ) , ( x 1 − 1 , y 2 ) , ( x 1 − 1 , y 1 − 1 ) 四个点来做,系数分别为 1,1,1,1 1 , − 1 , − 1 , 1 ,第三个矩形同理也可以拆成四个点。
枚举其中的两个点,问题就变成了给出起点和终点和一个矩形,问有多少种在矩形内选一个点然后从起点走到终点且经过选择的点的方案。
考虑起点到终点的每一条经过矩形内部的路径,设经过了s个点,那么这条路径的贡献就是s。现在问题就转化成了求每条路径的和。
对于起点,我们可以枚举从哪个位置进入矩形。
对于所有 x3xx4 x 3 ≤ x ≤ x 4 ,假设我们从 (x,y31) ( x , y 3 − 1 ) 走到 (x,y3) ( x , y 3 ) ,那么我们就算出从起点走到 (x,y31) ( x , y 3 − 1 ) 再从 (x,y3) ( x , y 3 ) 走到终点的路径数,然后把每条路径的系数乘上 (x+y3) − ( x + y 3 )
对于另外三条边同理我们也这么做,这样做完之后你会发现每条路径的系数恰好就是它经过的矩形内部的点数。
时间复杂度 O(Max(x,y)) O ( M a x ( x , y ) )

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long LL;

const int N=2000005;
const int MOD=1000000007;

int x1,x2,x3,x4,x5,x6,y1,y2,y3,y4,y5,y6,jc[N],ny[N];
struct data{int x,y,c;}a[4],b[4];

int C(int x1,int y1,int x2,int y2)
{
    return (LL)jc[x2-x1+y2-y1]*ny[x2-x1]%MOD*ny[y2-y1]%MOD;
}

int solve(data a,data b)
{
    int x1=a.x,y1=a.y,x2=b.x,y2=b.y,ans=0;
    for (int i=x3;i<=x4;i++) (ans+=(LL)C(x1,y1,i,y3-1)*C(i,y3,x2,y2)%MOD*(-i-y3)%MOD)%=MOD;
    for (int i=y3;i<=y4;i++) (ans+=(LL)C(x1,y1,x3-1,i)*C(x3,i,x2,y2)%MOD*(-i-x3)%MOD)%=MOD;
    for (int i=x3;i<=x4;i++) (ans+=(LL)C(i,y4+1,x2,y2)*C(x1,y1,i,y4)%MOD*(i+y4+1)%MOD)%=MOD;
    for (int i=y3;i<=y4;i++) (ans+=(LL)C(x4+1,i,x2,y2)*C(x1,y1,x4,i)%MOD*(i+x4+1)%MOD)%=MOD;
    return ans;
}

int main()
{
    scanf("%d%d%d%d%d%d",&x1,&x2,&x3,&x4,&x5,&x6);
    scanf("%d%d%d%d%d%d",&y1,&y2,&y3,&y4,&y5,&y6);
    jc[0]=jc[1]=ny[0]=ny[1]=1;
    for (int i=2;i<=x6+y6;i++) jc[i]=(LL)jc[i-1]*i%MOD,ny[i]=(LL)(MOD-MOD/i)*ny[MOD%i]%MOD;
    for (int i=2;i<=x6+y6;i++) ny[i]=(LL)ny[i-1]*ny[i]%MOD;
    a[0]=(data){x2,y2,1};a[1]=(data){x2,y1-1,-1};a[2]=(data){x1-1,y2,-1};a[3]=(data){x1-1,y1-1,1};
    b[0]=(data){x6+1,y6+1,1};b[1]=(data){x6+1,y5,-1};b[2]=(data){x5,y6+1,-1};b[3]=(data){x5,y5,1};
    int ans=0;
    for (int i=0;i<4;i++)
        for (int j=0;j<4;j++)
            (ans+=a[i].c*b[j].c*solve(a[i],b[j]))%=MOD;
    printf("%d",(ans+MOD)%MOD);
    return 0;
}

最后

以上就是落后高山为你收集整理的AtCoder Grand Contest 018 E - Sightseeing Plan 数学题意分析代码的全部内容,希望文章能够帮你解决AtCoder Grand Contest 018 E - Sightseeing Plan 数学题意分析代码所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(53)

评论列表共有 0 条评论

立即
投稿
返回
顶部