2859_矩阵变换_模拟

lzusa 发布于 2017-12-09 0 次阅读

题目描述

给定一个 m*n 的矩阵，每个格子里面有一颗不同颜色的宝石。再给出一些关键点，并定义两个矩阵类似为：每种颜色的宝石到各个关键点的距离和原矩阵都相同。 
问有多少个矩阵和给定的矩阵类似。当然，自己和自己是类似的。 
距离定义为 max{|x1-x2|,|y1-y2|}

思路

对于两个和任意关键点距离相等的位置是可以相互交换的，那么答案就是全排列的乘积

有两种写法，一个是用hash的方法，另外是通过暴力排序的方法

#include 
#include 
#include 
using namespace std;
#define maxn 206
#define ll long long
#define LL long long
#define mo 1000000009
int a[maxn][maxn][56],n,m,key,l,l1;
bool f[maxn][maxn];
ll p[40006],b[maxn*maxn],ans=1;
long long s = 1;

int max(int a,int b)
{
    return a>b?a:b;
}

int abs(int a)
{
    return a>=0?a:-a;
}
int cmp(int a, int b)
{
    return a < b;
}
LL pow(LL x, LL y)
{
    LL b = 1;
    while (y)
    {
        if (y & 1) b = b * x % mo;
        y >>= 1;
        x = x * x % mo;
    }
    return b;
}
int main()
{
    scanf("%d%d%d",&n,&m,&key);
    p[0] = 1;
    for (int i=1;i<=40001;i++)
    {
        s=(s*i) % mo;
        p[i]=s;
    }
    int x,y;
    for (int k=1;k<=key;k++)
    {
        scanf("%d%d",&x,&y);
        f[x][y] = 1;
        for (int i=1;i<=n;i++)
            for (int j=1;j<=m;j++)
                a[i][j][k]=max(abs(i-x),abs(j-y));
    }
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
        if (!f[i][j])
        {
            s=1;
            for (int k=1;k<=key;k++)
            {
                s += a[i][j][k] * pow(7, k) * pow(17, k) * pow (107, k) * pow(1007, k);
                s %= mo;
            }
            b[++l]=s;
        }
    sort(b+1,b+l+1,cmp);
    x = 1;
    for (int i = 2; i <= l; i++)
    {
        if (b[i] != b[i - 1])
        {
            ans *= p[x];
            ans %= mo;
            x = 1;
        }
        else x++;
    }
    ans *= p[x];
    ans %= mo;
    cout << ans;
}

 

#include 
#include 
#include 
using namespace std;
#define N 201
#define p 1000000009
#define LL long long
#define max(x, y) ((x) > (y) ? (x) : (y))
bool f[N][N];
LL jc[N * N];
struct arr1
{
    int r[51];
}ans[N * N];
struct arr
{
    int x, y;
}b[N];
int cmp(arr1 a, arr1 b)
{
    for (int i = 1; i <= 50; i++)
        if (a.r[i] < b.r[i]) return 1;
        else if (a.r[i] > b.r[i]) return 0;
    return 0; 
}
int abs(int x)
{
    if (x < 0) return -x;
    return x;
}
int check(int x)
{
    for (int i = 1; i <= 50; i++)
    {
        if (ans[x].r[i] != ans[x - 1].r[i])
            return 0;
    }
    return 1;
}
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    int t;
    scanf("%d", &t);
    jc[1] = 1;
    jc[0] = 1;
    for (int i = 2; i <= n * m; i++)
    {
        jc[i] = jc[i - 1] * i;
        jc[i] %= p;
    }
    for (int i = 1; i <= t; i++)
    {
        int x, y;
        scanf("%d%d", &b[i].x, &b[i].y);
        f[b[i].x][b[i].y] = 1;  
    }
    int l = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (!f[i][j])
            {
                l++;
                for (int k = 1; k <= t; k++)
                    ans[l].r[k] = max(abs(i - b[k].x), abs(j - b[k].y));
            }
    sort(ans + 1, ans + l + 1, cmp);
    int x = 1;
    LL tot = 1;
    for (int i = 2; i <= l; i++)
    {
        if (!check(i))
        {
            tot *= jc[x];
            tot %= p;
            x = 1;
        }
        else x++;
    }
    tot *= jc[x];
    tot %= p;
    cout << tot;
}

 

]]>