CF1225E Rock Is Push （计数）

观察性质计数题orz小贺

考场上跟榜才切

我们只能往下和往右走，那么只有连续的往下和往右可能会造成不合法的情况！如果当前这一步是向右，那么只有它前面连续的一段向右可能影响到它。

考虑把连续的向右/下一起处理，使得只有右和下之间相互转移。

假设向下走到达当前点\((i,j)\)，接下来向右走若干段，那么能走的格数只和它右面的箱子数有关。而且能到达的位置是连续的一段

向右走到达当前点同理

点数是\(O(n^{2})\)的，每个方向可能转移到\(O(n)\)个位置，暴力转移是\(O(n^{3})\)的。因此需要前缀和打差分优化，时间优化成\(O(n^{2})\)

#include <cstdio>

#include <cstring>

#include <algorithm>

#define ull unsigned long long

#define ll long long

#define dd long double

using namespace std;

const int N1=2e3+5, p=1e9+7;

template <typename _T> void read(_T &ret)

{

    ret=0; _T fh=1; char c=getchar();

    while(c<'0'||c>'9'){ if(c=='-') fh=-1; c=getchar(); }

    while(c>='0'&&c<='9'){ ret=ret*10+c-'0'; c=getchar(); }

    ret=ret*fh;

}

int n,m;

char str[N1][N1];

int a[N1][N1];

int qa(int ax,int ay,int bx,int by)

{

    return a[bx][by]-a[ax-1][by]-a[bx][ay-1]+a[ax-1][ay-1];

}

ll f[N1][N1][2],g[N1][N1][2],ysum[N1];

int main()

{

    // freopen("a.in","r",stdin);

    // freopen("e0.out","w",stdout);

    read(n); read(m);

    if(n==1&&m==1){ puts("1"); return 0; }

    for(int i=1;i<=n;i++) scanf("%s",str[i]+1);

    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)

    {

        a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1];

        a[i][j]+=(str[i][j]=='R');

    }

    g[1][1][0]=1; g[1][2][0]=p-1;

    g[1][1][1]=1; g[2][1][1]=p-1;

    for(int i=1;i<=n;i++)

    {

        //1->0

        for(int j=1;j<=m;j++)

        {

            (ysum[j]+=g[i][j][1])%=p;

            f[i][j][1]=ysum[j];

            if(j==m) continue;

            int r=m-qa(i,j+1,i,m);

            (g[i][j+1][0]+=f[i][j][1])%=p;

            (g[i][r+1][0]+=-f[i][j][1]+p)%=p;

        }

        //0->1

        ll xsum=0;

        for(int j=1;j<=m;j++)

        {

            (xsum+=g[i][j][0])%=p;

            f[i][j][0]=xsum;

            if(i==n) continue;

            int r=n-qa(i+1,j,n,j);

            (g[i+1][j][1]+=f[i][j][0])%=p;

            (g[r+1][j][1]+=-f[i][j][0]+p)%=p;

        }

    }

    // for(int i=1;i<=n;i++,puts("")) for(int j=1;j<=m;j++) printf("%d ",a[i][j]);

    // puts("");

    // for(int i=1;i<=n;i++,puts("")) for(int j=1;j<=m;j++) printf("%lld ",f[i][j][0]);

    // puts("");

    // for(int i=1;i<=n;i++,puts("")) for(int j=1;j<=m;j++) printf("%lld ",f[i][j][1]);

    // puts("");

    ll ans=(f[n][m][0]+f[n][m][1])%p;

    printf("%lld\n",ans);

    return 0;

}

`

巴特西

CF1225E Rock Is Push （计数）

最新文章

热门文章