我是靠谱客的博主 深情星月,这篇文章主要介绍(组合计数)AtCoder Grand Contest 018 E - Sightseeing Plan,现在分享给大家,希望可以做个参考。

Time limit : 8sec / Memory limit : 256MB

Score : 1600 points

Problem Statement

Joisino is planning on touring Takahashi Town. The town is divided into square sections by north-south and east-west lines. We will refer to the section that is the x-th from the west and the y-th from the north as (x,y).

Joisino thinks that a touring plan is good if it satisfies the following conditions:

  • Let (p,q) be the section where she starts the tour. Then, X1≤pX2 and Y1≤qY2 hold.

  • Let (s,t) be the section where she has lunch. Then, X3≤sX4 and Y3≤tY4 hold.

  • Let (u,v) be the section where she ends the tour. Then, X5≤uX6 and Y5≤vY6 hold.

  • By repeatedly moving to the adjacent section (sharing a side), she travels from the starting section to the ending section in the shortest distance, passing the lunch section on the way.

Two touring plans are considered different if at least one of the following is different: the starting section, the lunch section, the ending section, and the sections that are visited on the way. Joisino would like to know how many different good touring plans there are. Find the number of the different good touring plans. Since it may be extremely large, find the count modulo 109+7.

Constraints

  • 1≤X1≤X2<X3≤X4<X5≤X6≤106
  • 1≤Y1≤Y2<Y3≤Y4<Y5≤Y6≤106

Input

Input is given from Standard Input in the following format:

复制代码
1
2
X1 X2 X3 X4 X5 X6 Y1 Y2 Y3 Y4 Y5 Y6

Output

Print the number of the different good touring plans, modulo 109+7.


Sample Input 1

Copy
复制代码
1
2
1 1 2 2 3 4 1 1 2 2 3 3

Sample Output 1

Copy
复制代码
1
10

The starting section will always be (1,1), and the lunch section will always be (2,2). There are four good touring plans where (3,3) is the ending section, and six good touring plans where (4,3) is the ending section. Therefore, the answer is 6+4=10.


Sample Input 2

Copy
复制代码
1
2
1 2 3 4 5 6 1 2 3 4 5 6

Sample Output 2

Copy
复制代码
1
2346

Sample Input 3

Copy
复制代码
1
2
77523 89555 420588 604360 845669 973451 2743 188053 544330 647651 709337 988194

Sample Output 3

Copy
复制代码
1
137477680

按照官方的题解,模仿mjy0724大神的代码写的。思路与有一道求子矩形的题目非常相似。不过每一条路径都贡献了其与区域B的交的大小次,需要注意。

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
1 #include <iostream> 2 #include <string> 3 #include <algorithm> 4 #include <cstring> 5 #include <cstdio> 6 #include <cmath> 7 #include <queue> 8 #include <set> 9 #include <map> 10 #include <list> 11 #include <vector> 12 #include <stack> 13 #include <cassert> 14 #define mp make_pair 15 #define MIN(a,b) (a>b?b:a) 16 //#define MAX(a,b) (a>b?a:b) 17 typedef long long ll; 18 typedef unsigned long long ull; 19 const int MAX=2e6+5; 20 const int INF=1e9+5; 21 using namespace std; 22 const ll MOD=1000000007; 23 typedef pair<ll,int> pii; 24 typedef pair<ll,ll> pll; 25 const double eps=0.00000001; 26 ll fact[MAX],inv[MAX]; 27 ll x[10],y[10]; 28 ll pow_mod(ll a,ll b) {ll res=1;a%=MOD; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%MOD;a=a*a%MOD;}return res;} 29 ll num(ll sx,ll sy,ll ex,ll ey)//从(sx,sy)到(ex,ey)情况数 30 { 31 ex-=sx;ey-=sy; 32 return fact[(ex+ey)]*inv[ex]%MOD*inv[ey]%MOD; 33 } 34 ll cal(ll sx,ll sy,ll ex,ll ey)//从(sx,sy)到(ex,ey)过程中经过B区域的情况数 35 { 36 ll re=0,now=num(sx,sy,x[3],y[3])*num(x[3],y[3],ex,ey)%MOD; 37 re=now; 38 ll right_x,right_y,down_x,down_y;//向右、向下走的坐标 39 right_x=down_x=x[3];right_y=down_y=y[3]; 40 for(ll step=x[3]+y[3]+1;step<x[4]+y[4];step++) 41 { 42 if(right_x!=x[4]) 43 { 44 now+=num(sx,sy,right_x+1,right_y-1)*num(right_x+1,right_y,ex,ey)%MOD; 45 ++right_x; 46 } 47 else 48 { 49 now-=num(sx,sy,right_x,right_y)*num(right_x+1,right_y,ex,ey)%MOD; 50 ++right_y; 51 } 52 if(down_y!=y[4]) 53 { 54 now+=num(sx,sy,down_x-1,down_y+1)*num(down_x,down_y+1,ex,ey)%MOD; 55 ++down_y; 56 } 57 else 58 { 59 now-=num(sx,sy,down_x,down_y)*num(down_x,down_y+1,ex,ey)%MOD; 60 ++down_x; 61 } 62 now%=MOD; 63 re=(re+now)%MOD; 64 } 65 if(x[3]!=x[4]||y[3]!=y[4]) 66 re=(re+num(sx,sy,x[4],y[4])*num(x[4],y[4],ex,ey)%MOD)%MOD; 67 return re; 68 } 69 int main() 70 { 71 fact[0]=fact[1]=1; 72 for(ll i=1;i<=2e6+1;i++) 73 fact[i]=fact[i-1]*i%MOD; 74 inv[(int)2e6+1]=pow_mod(fact[(int)2e6+1],MOD-2); 75 for(ll i=2e6;i>=1;i--) 76 inv[i]=(i+1)*inv[i+1]%MOD; 77 for(ll i=1;i<=6;i++) 78 scanf("%lld",&x[i]); 79 for(ll i=1;i<=6;i++) 80 scanf("%lld",&y[i]); 81 --x[1];--y[1]; 82 ++x[6];++y[6]; 83 ll an=0; 84 for(int i=1;i<=2;i++) 85 for(int j=1;j<=2;j++) 86 for(int p=5;p<=6;p++) 87 for(int q=5;q<=6;q++) 88 an=(an+((i+j-p-q)%2?-1:1)*cal(x[i],y[j],x[p],y[q]))%MOD; 89 an%=MOD; 90 while(an<0) 91 an+=MOD; 92 printf("%lldn",an); 93 }

 

转载于:https://www.cnblogs.com/quintessence/p/7230353.html

最后

以上就是深情星月最近收集整理的关于(组合计数)AtCoder Grand Contest 018 E - Sightseeing Plan的全部内容,更多相关(组合计数)AtCoder内容请搜索靠谱客的其他文章。

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

评论列表共有 0 条评论

立即
投稿
返回
顶部