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

[cf963E]Circles of Waiting

开发技术 开发技术 2周前 (04-29) 6次浏览

将与原点距离大于$R$的点缩为一个点$t$,即终点

做法1

定义$f_{i}$表示从$i$到$t$的期望步数,即$f_{i}=begin{cases}sum_{(i,j)in E}w_{(i,j)}f_{j}+1&(jne t)\0&(j=t)end{cases}$

直接对其高斯消元,时间复杂度为$o(n^{3}m^{3})$

做法2

事实上,如果将其按照顺序从上到下、从左到右依次编号,并依次消元,编号为$x$的行在(消元的)任意时刻,都仅有$[x-m,x+m]$这些列的元素非0

由此,显然在消元时,仅需要枚举其后$m$列,且每一列仅需枚举$o(m)$个元素,即做到$o(n^{2}m^{2})$的复杂度

做法3

对于所有元素,若其上方的格子不存在,即将其作为一个变量,否则通过其上方的格子的方程即可确定其的表示,最终即仅有$o(m)$个变量,以及下方不存在格子的位置未保证其成立

在$o(nm^{2})$的时间内推出此式子,并对$m$元解方程,复杂度为$o(m^{3})$

类似地,也可以从左到右去枚举,做到$o(n^{2}m)$的复杂度

综上,即可做到$o(nmmin(n,m)))$的复杂度

[cf963E]Circles of Waiting[cf963E]Circles of Waiting

 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

[cf963E]Circles of Waiting[cf963E]Circles of Waiting

 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

 


程序员灯塔
转载请注明原文链接:[cf963E]Circles of Waiting
喜欢 (0)