• 微信公众号：美女很有趣。 工作之余，放松一下，关注即送10G+美女照片！

# [cf963E]Circles of Waiting

2周前 (04-29) 6次浏览

##### 做法3

``` 1 #include<bits/stdc++.h>
2 using namespace std;
3 #define N 105
4 #define M 8005
5 #define mod 1000000007
6 int V,R,a,b,c,d,id[N][N],A[M][M],ans[M];
7 int pow(int n,int m){
8     int s=n,ans=1;
9     while (m){
10         if (m&1)ans=1LL*ans*s%mod;
11         s=1LL*s*s%mod;
12         m>>=1;
13     }
14     return ans;
15 }
16 void guess(){
17     for(int i=1;i<=V;i++){
18         int x=pow(A[i][i],mod-2);
19         for(int j=i;j<=V+1;j++)A[i][j]=1LL*A[i][j]*x%mod;
20         for(int j=i+1;j<=min(i+2*R,V);j++){
21             if (A[j][i]){
22                 int x=A[j][i];
23                 for(int k=i;k<=min(i+2*R,V);k++)A[j][k]=(A[j][k]-1LL*A[i][k]*x%mod+mod)%mod;
24                 A[j][V+1]=(A[j][V+1]-1LL*A[i][V+1]*x%mod+mod)%mod;
25             }
26         }
27     }
28     for(int i=V;i;i--){
29         for(int j=i+1;j<=V;j++)A[i][V+1]=(A[i][V+1]-1LL*A[i][j]*ans[j]%mod+mod)%mod;
30         ans[i]=A[i][V+1];
31     }
32 }
33 int main(){
34     scanf("%d%d%d%d%d",&R,&a,&b,&c,&d);
35     int inv=pow(a+b+c+d,mod-2);
36     a=1LL*a*inv%mod,b=1LL*b*inv%mod,c=1LL*c*inv%mod,d=1LL*d*inv%mod;
37     for(int i=-R;i<=R;i++)
38         for(int j=-R;j<=R;j++)
39             if (i*i+j*j<=R*R)id[i+R][j+R]=++V;
40     for(int i=-R;i<=R;i++)
41         for(int j=-R;j<=R;j++){
42             if (i*i+j*j<=R*R){
43                 int ii=i+R,jj=j+R;
44                 if ((i-1)*(i-1)+j*j<=R*R)A[id[ii][jj]][id[ii-1][jj]]=(A[id[ii][jj]][id[ii-1][jj]]+mod-a)%mod;
45                 if (i*i+(j-1)*(j-1)<=R*R)A[id[ii][jj]][id[ii][jj-1]]=(A[id[ii][jj]][id[ii][jj-1]]+mod-b)%mod;
46                 if ((i+1)*(i+1)+j*j<=R*R)A[id[ii][jj]][id[ii+1][jj]]=(A[id[ii][jj]][id[ii+1][jj]]+mod-c)%mod;
47                 if (i*i+(j+1)*(j+1)<=R*R)A[id[ii][jj]][id[ii][jj+1]]=(A[id[ii][jj]][id[ii][jj+1]]+mod-d)%mod;
48             }
49         }
50     for(int i=1;i<=V;i++)A[i][i]=A[i][V+1]=1;
51     guess();
52     printf("%d",ans[id[R][R]]);
53 } ```

View Code

``` 1 #include<bits/stdc++.h>
2 using namespace std;
3 #define N 105
4 #define M 8005
5 #define mod 1000000007
6 int V,VV,R,a,b,c,d,sum,id[N][N],g[M][N<<1],A[M][N<<1],ans[M];
7 int pow(int n,int m){
8     int s=n,ans=1;
9     while (m){
10         if (m&1)ans=1LL*ans*s%mod;
11         s=1LL*s*s%mod;
12         m>>=1;
13     }
14     return ans;
15 }
16 void guess(){
17     for(int i=1;i<=V;i++){
18         int k=-1;
19         for(int j=i;j<=V;j++)
20             if (A[j][i]){
21                 k=j;
22                 break;
23             }
24         if (k!=i){
25             for(int j=i;j<=V+1;j++)swap(A[i][j],A[k][j]);
26         }
27         int x=pow(A[i][i],mod-2);
28         for(int j=i;j<=V+1;j++)A[i][j]=1LL*A[i][j]*x%mod;
29         for(int j=i+1;j<=V;j++)
30             if (A[j][i]){
31                 int x=A[j][i];
32                 for(int k=i;k<=V+1;k++)A[j][k]=(A[j][k]-1LL*A[i][k]*x%mod+mod)%mod;
33             }
34     }
35     for(int i=V;i;i--){
36         for(int j=i+1;j<=V;j++)A[i][V+1]=(A[i][V+1]-1LL*A[i][j]*ans[j]%mod+mod)%mod;
37         ans[i]=A[i][V+1];
38     }
39 }
40 int main(){
41     scanf("%d%d%d%d%d",&R,&a,&b,&c,&d);
42     int inv=pow(a+b+c+d,mod-2);
43     a=1LL*a*inv%mod,b=1LL*b*inv%mod,c=1LL*c*inv%mod,d=1LL*d*inv%mod;
44     for(int i=-R;i<=R;i++)
45         for(int j=-R;j<=R;j++)
46             if (i*i+j*j<=R*R)id[i+R][j+R]=++V;
47     V=0;
48     for(int i=-R;i<=R;i++)
49         for(int j=-R;j<=R;j++)
50             if ((i*i+j*j<=R*R)&&((i-1)*(i-1)+j*j>R*R))g[id[i+R][j+R]][++V]=1;
51     for(int i=-R;i<=R;i++)
52         for(int j=-R;j<=R;j++)
53             if ((i*i+j*j<=R*R)&&((i-1)*(i-1)+j*j<=R*R)){
54                 int ii=i+R,jj=j+R;
55                 memcpy(g[id[ii][jj]],g[id[ii-1][jj]],sizeof(g[id[ii][jj]]));
56                 g[id[ii][jj]][V+1]=(g[id[ii][jj]][V+1]+mod-1)%mod;
57                 if ((i-2)*(i-2)+j*j<=R*R){
58                     for(int k=1;k<=V+1;k++)g[id[ii][jj]][k]=(g[id[ii][jj]][k]-1LL*a*g[id[ii-2][jj]][k]%mod+mod)%mod;
59                 }
60                 if ((i-1)*(i-1)+(j-1)*(j-1)<=R*R){
61                     for(int k=1;k<=V+1;k++)g[id[ii][jj]][k]=(g[id[ii][jj]][k]-1LL*b*g[id[ii-1][jj-1]][k]%mod+mod)%mod;
62                 }
63                 if ((i-1)*(i-1)+(j+1)*(j+1)<=R*R){
64                     for(int k=1;k<=V+1;k++)g[id[ii][jj]][k]=(g[id[ii][jj]][k]-1LL*d*g[id[ii-1][jj+1]][k]%mod+mod)%mod;
65                 }
66                 int x=pow(c,mod-2);
67                 for(int k=1;k<=V+1;k++)g[id[ii][jj]][k]=1LL*g[id[ii][jj]][k]*x%mod;
68             }
69     for(int i=-R;i<=R;i++)
70         for(int j=-R;j<=R;j++)
71             if ((i*i+j*j<=R*R)&&((i+1)*(i+1)+j*j>R*R)){
72                 int ii=i+R,jj=j+R;
73                 memcpy(A[++VV],g[id[ii][jj]],sizeof(g[id[ii][jj]]));
74                 if ((i-1)*(i-1)+j*j<=R*R){
75                     for(int k=1;k<=V+1;k++)A[VV][k]=(A[VV][k]-1LL*a*g[id[ii-1][jj]][k]%mod+mod)%mod;
76                 }
77                 if (i*i+(j-1)*(j-1)<=R*R){
78                     for(int k=1;k<=V+1;k++)A[VV][k]=(A[VV][k]-1LL*b*g[id[ii][jj-1]][k]%mod+mod)%mod;
79                 }
80                 if ((i+1)*(i+1)+j*j<=R*R){
81                     for(int k=1;k<=V+1;k++)A[VV][k]=(A[VV][k]-1LL*c*g[id[ii+1][jj]][k]%mod+mod)%mod;
82                 }
83                 if (i*i+(j+1)*(j+1)<=R*R){
84                     for(int k=1;k<=V+1;k++)A[VV][k]=(A[VV][k]-1LL*d*g[id[ii][jj+1]][k]%mod+mod)%mod;
85                 }
86                 A[VV][V+1]=mod+1-A[VV][V+1];
87             }
88     guess();
89     sum=g[id[R][R]][V+1];
90     for(int i=1;i<=V;i++)sum=(sum+1LL*g[id[R][R]][i]*ans[i])%mod;
91     printf("%d",sum);
92 } ```

View Code