QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#589885 | #6425. Harmonious Rectangle | ji_114514 | WA | 813ms | 3660kb | C++20 | 1.4kb | 2024-09-25 20:30:16 | 2024-09-25 20:30:16 |
Judging History
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'