QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#589885#6425. Harmonious Rectangleji_114514WA 813ms3660kbC++201.4kb2024-09-25 20:30:162024-09-25 20:30:16

Judging History

你现在查看的是最新测评结果

  • [2024-09-25 20:30:16]
  • 评测
  • 测评结果:WA
  • 用时:813ms
  • 内存:3660kb
  • [2024-09-25 20:30:16]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long

using namespace std;

const int N = 2e3 + 10, mod = 1e9 + 7;

ll dp[20][20];
ll qmi(ll a, ll k)
{
    ll res = 1;
    while (k)
    {
        if (k & 1)res = res * a;
        k >>= 1;
        a = a * a;
    }
    return res;
}
int n, m, c[20][20];

bool check(int x, int y)
{
    for (int i = 1; i < x; i++)
    {
        for (int j = 1; j < y; j++)
        {
            if ((c[i][j] == c[i][y]) && (c[x][j] == c[x][y]))return 0;
            if ((c[i][j] == c[x][j]) && (c[i][y] == c[x][y]))return 0;
        }
    }
    return 1;
}

void dfs(int x, int y)
{
    if (y == m + 1) {
        y = 1, x++;
        if (x > n) {
            dp[n][m]++;
            return;
        }
    }
    for (int i = 0; i < 3; i++) {
        c[x][y] = i;
        if (check(x, y))dfs(x, y + 1);
    }
}

void solve()
{
    int n, m; cin >> n >> m;
    if (n > m)swap(n, m);
    if (m < 10)cout << dp[n][m] << '\n';
    else if (n >= 2)cout << qmi(3, n * m) << '\n';
    else cout << 0 << '\n';
}

int main()
{
    for (int i = 1; i < 10; i++)
    {
        for (int j = i; j < 10; j++)
        {
            n = i, m = j;
            dfs(1, 1);
            dp[i][j] = (qmi(3, i * j) - dp[i][j]) % mod;
        }
    }
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1; cin >> t;
    while (t--)solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 810ms
memory: 3652kb

input:

3
1 4
2 2
3 3

output:

0
15
16485

result:

ok 3 number(s): "0 15 16485"

Test #2:

score: -100
Wrong Answer
time: 813ms
memory: 3660kb

input:

10000
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
1 58
1 59
1 60
1 6...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
15
339
4761
52929
517761
4767849
43046721
387420489
3486784401
31381059609
282429536481
2541865828...

result:

wrong answer 110th numbers differ - expected: '486784380', found: '3486784401'