Submission #35309

#	Time	Username	Problem	Language	Result	Execution time	Memory
35309		itsjustwinds	마스코트 (JOI13_mascots)	C++11	0 / 100	9 ms	29556 KiB

mascots

#include<bits/stdc++.h>
#define ll long long
#define maxn 1005
#define mod 1000000007
using namespace std;
ll gt[1000005];
int a[maxn][maxn],n,r,c;
ll g[maxn][maxn],f[maxn][maxn];
int topx,topy,downx,downy;
template<typename T> inline void read(T &x)
{
        char c;
        bool neg = false;
        while (!isdigit(c = getchar()) && c != '-');
        x = 0;
        if (c == '-')
        {
                neg = true;
                c = getchar();
        }
        do
        {
                x = x * 10 + c - '0';
        }
        while (isdigit(c = getchar()));
        if (neg) x = -x;
}
template<typename T> inline void write(T x)
{
        if (x < 0)
        {
                putchar('-');
                write(-x);
                return;
        }
        if (x < 10)
        {
                putchar(char(x + 48));
        }
        else
        {
                write(x/10);
                putchar(char(48 + x%10));
        }
}
template<typename T> inline void writeln(T x)
{
        write(x);
        putchar('\n');
}
ll cal1(int x,int y)
{
        if (x==downx&&y==downy) return 1;
        if (f[x][y]!=-1) return f[x][y];
        ll res=0;
        if (x>downx)res+=1ll*cal1(x-1,y)*gt[y];
        if (y>downy)res+=1ll*cal1(x,y-1)*gt[x];
        f[x][y]=res;
        return res;
}
ll cal2(int x,int y)
{
        if (x==topx&&y==topy) return 1;
        if (g[x][y]!=-1) return g[x][y];
        ll res=0;
        if (x<topx) res+=1ll*cal2(x+1,y)*gt[topx-y+1];
        if (y<topy) res+=1ll*cal2(x,y+1)*gt[topy-x+1];
        f[x][y]=res;
        return res;
}
int main()
{
        //freopen("Mascots.inp","r",stdin);
        cin.tie(0);
        cout.tie(0);
        read(r);
        read(c);
        read(n);
        topx=1e9,topy=1e9;
        for (int i=1; i<=n; ++i)
        {
                int u,v;
                read(u);
                read(v);
                topx=min(topx,u);
                topy=min(topy,v);
                downx=max(downx,u);
                downy=max(downy,v);
                a[u][v]=1;
        }
        for  (int i=1; i<=r; ++i)
                for (int j=1; j<=c; ++j)
                {
                        f[i][j]=-1;
                        g[i][j]=-1;
                }
        gt[0]=1;
        for (int i=1; i<=r*c; ++i)
                gt[i]=(gt[i-1]*i)%mod;
        ll res=(1ll*cal1(r,c)*cal2(1,1))%mod;
        if ((topx!=1||topy!=1)&&(downx!=r||downy!=c))
                res=(1ll*res*2)%mod;
        res=(1ll*res*gt[(downx-topx+1)*(downy-topy+1)-n])%mod;
        cout<<res;
        return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 30
• Subtask 3: 0 / 60