CF963E Circles of Waiting && loj 3080 国际象棋

三笠·阿克曼 · 2022-10-20 21:27:55 · 个人记录

两道都是主元法，最近遇到太多次了。

CF963E Circles of Waiting

设 f_{i,j} 为从 (i,j) 这个点开始走出去的期望步数。

所以容易有 f_{i,j}=\sum\limits_{k=1}\limits^{4}p_k\times f_{i+x_k,j+y_k} +1

当一个点的距离超过 R 时，显然有 f_{i,j}=0。所以我们将每行第一个 (i,j) 的 f_{i,j} 定为一个主元，然后通过关系式向右递推到 f_{i,j}=0 的情况，这样就得到了若干个方程，高斯消元一下就好了。

#include<cstdio>
#include<iostream>
#include<queue>
using namespace std;

const int N=111,mod=1e9+7;
int n,R,a0,a1,a2,a3,a4;
int b[N][N],can[N*N],ed[N*N];

int qsm(int a,int b)
{
    int res=1;
    for(;b;b>>=1)
    {
        if(b&1) res=1ll*res*a%mod;
        a=1ll*a*a%mod;
    }
    return res;
}

struct vec{int x,y;};
struct node 
{ 
    int a[N];
}f[N*N];

bool operator < (vec p,vec q){return p.x>q.x;}
priority_queue<vec>q;
node operator *(int x,node y) 
{ 
    for(int i=0;i<=2*R+1;i++) y.a[i]=1ll*y.a[i]*x%mod;
    return y;
}
node operator +(node x,node y) 
{
    for(int i=0;i<=2*R+1;i++) x.a[i]=(x.a[i]+y.a[i])%mod;
    return x;
}
node operator +(node x,int y)
{
    x.a[2*R+1]=(x.a[2*R+1]+y)%mod;
    return x;
}

int pos(int x,int y) { return (y+R+1)*n+(x+R+2); }

void Calc()
{
    for(int i=0;i<=2*R;i++)
    {
        if(!b[i][i])
        {
            int k=0;
            for(int j=i+1;j<=2*R;j++)
                if(b[j][i]){k=j;break;}
            if(!k) break ;
            swap(b[i],b[k]);
        }
        int inv=qsm(b[i][i],mod-2);
        for(int j=0;j<=2*R;j++)
        {
            if(i==j) continue;
            int p=1ll*inv*(mod-b[j][i])%mod;
            for(int k=i;k<=2*R+1;k++)
                b[j][k]=(b[j][k]+1ll*p*b[i][k]%mod)%mod;
        }
    }
    for(int i=0;i<=2*R;i++) b[i][2*R+1]=1ll*b[i][2*R+1]*qsm(b[i][i],mod-2)%mod;
}

int main()
{
    scanf("%d%d%d%d%d",&R,&a1,&a2,&a3,&a4);
    n=2*R+3;a0=qsm(a1+a2+a3+a4,mod-2);
    a1=1ll*a1*a0%mod;a2=1ll*a2*a0%mod;a3=1ll*a3*a0%mod;a4=1ll*a4*a0%mod;
    for(int i=-R;i<=R;i++)
        for(int j=-R;j<=R;j++)
            if(i*i+j*j<=R*R) can[pos(i,j)]=1;
    for(int j=-R;j<=R;j++)
    {
        for(int i=-R;i<=0;i++) 
            if(can[pos(i,j)])
            {
                q.push(vec{i,j});
                f[pos(i,j)].a[j+R]=1;
                break;
            }
        for(int i=R;i>=-R;i--) 
            if(can[pos(i,j)])
            {
                ed[pos(i,j)]=1;
                break;
            }
    }
    while(!q.empty())
    {
        int x=q.top().x,y=q.top().y;q.pop();
        f[pos(x+1,y)]=qsm(a1,mod-2)*(f[pos(x,y)]+((mod-a2)*f[pos(x,y+1)])+((mod-a3)*f[pos(x-1,y)])+((mod-a4)*f[pos(x,y-1)])+(mod-1));
        if(ed[pos(x,y)])
        {
            for(int i=0;i<=2*R+1;i++) b[y+R][i]=f[pos(x+1,y)].a[i];
            b[y+R][2*R+1]=mod-b[y+R][2*R+1];
        }
        else q.push(vec{x+1,y});
    }
    Calc();
    b[2*R+1][2*R+1]=1;
    int Ans=0;
    for(int i=0;i<=2*R+1;i++) Ans=(Ans+1ll*f[pos(0,0)].a[i]*b[i][2*R+1]%mod)%mod;
    printf("%d",Ans);
    return 0;
}

loj 3080. 「2019 集训队互测 Day 5」国际象棋

这题走日字其实也是一样的，我们只需要把第一二行和第一列的点设为主元转移就好了。

#include<cstdio>
#include<iostream>
using namespace std;

const int N=222,mod=998244353;

int read()
{
    int res=0;
    char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9')
        res=(res<<1)+(res<<3)+(ch^48),ch=getchar();
    return res;
}

void print(int x)
{
    if(x>=10) print(x/10);
    putchar((x%10)^48);
}

int qsm(int a,int b)
{
    int res=1;
    for(;b;b>>=1)
    {
        if(b&1) res=1ll*res*a%mod;
        a=1ll*a*a%mod;
    }
    return res;
}

int n,m,cnt,tot,p[10],mat[N*N][N*3],b[N*3][N*3];
int xx[10]={0,-2,-1,1,2,2,1,-1,-2};
int yy[10]={0,-1,-2,-2,-1,1,2,2,1};

int pos(int x,int y){return (x-1)*(m+1)+y;}
void Add(int &x,int y)
{
    x+=y;
    if(x>=mod) x-=mod;
}

void calc()
{
    for(int i=1;i<cnt;i++)
    {
        if(!b[i][i])
        {
            for(int j=i+1;j<cnt;j++)
                if(b[j][i]) { swap(b[i],b[j]);break;}
            if(!b[i][i]) break;
        }
        int inv=qsm(b[i][i],mod-2);
        for(int k=1;k<=cnt;k++) b[i][k]=1ll*b[i][k]*inv%mod;
        for(int j=1;j<cnt;j++)
        {
            if(i==j) continue;
            int p=mod-b[j][i]%mod;
            for(int k=i;k<=cnt;k++) Add(b[j][k],1ll*p*b[i][k]%mod);
        }
    }
}

int main()
{
    n=read();m=read();
    for(int i=1;i<=8;i++) p[i]=read(),p[0]+=p[i];
    p[0]=qsm(p[0],mod-2);
    for(int i=1;i<=8;i++) p[i]=1ll*p[i]*p[0]%mod;
    for(int i=1;i<=2;i++)
        for(int j=1;j<=m;j++) mat[pos(i,j)][++cnt]=1;
    for(int i=3;i<=n;i++) mat[pos(i,1)][++cnt]=1;
    cnt++;
    int inv=qsm(p[5],mod-2);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            int x=i+2,y=j+1; 
            int u=pos(x,y);
            for(int k=1;k<=cnt;k++) mat[u][k]=mat[pos(i,j)][k];
            mat[u][cnt]=mat[u][cnt]+1;
            for(int k=1;k<=8;k++)
            {
                if(k==5||i+xx[k]<1||i+xx[k]>n||j+yy[k]<1||j+yy[k]>m) continue;
                for(int l=1;l<=cnt;l++)
                    Add(mat[u][l],1ll*(mod-p[k])*mat[pos(i+xx[k],j+yy[k])][l]%mod);
            }
            for(int k=1;k<=cnt;k++) mat[u][k]=1ll*mat[u][k]*inv%mod;
            if(x>n||y>m)
            {
                tot++;
                for(int k=1;k<=cnt;k++) b[tot][k]=mat[u][k];
            }
        }
    calc();
    int T,x,y,ans;
    scanf("%d",&T);
    while(T--)
    {
        x=read();y=read();
        ans=mod-mat[pos(x,y)][cnt];
        for(int i=1;i<cnt;i++) Add(ans,1ll*mat[pos(x,y)][i]*b[i][cnt]%mod);
        print(ans);
        puts("");
    }
    return 0;
}