QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#663780 | #3686. 麻将 | The_cosmos | 100 ✓ | 594ms | 4032kb | C++14 | 5.6kb | 2024-10-21 17:19:47 | 2024-10-21 17:19:48 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using db = double;
using lb = long double;
using ull = unsigned long long;
using uint = unsigned int;
using ll = long long;
// using i128 = __int128;
// using ui128 = unsigned __int128;
#define REP(i, first, last) for (int i = (first); i <= (last); ++i)
#define DOW(i, first, last) for (int i = (first); i >= (last); --i)
#define int long long
#define pb emplace_back
#define ob pop_back
#define pii pair<int, int>
#define MPR make_pair
#define fi first
#define se second
#define tpl tuple<int, int, int>
#define MTP make_tuple
#define poly vector<int>
#define polyp vector<pii>
#define polyt vector<tpl>
#define all(x) x.begin(), x.end()
#define CVR(a, q) memset(a, q, sizeof a)
#define CLR(a) memset(a, 0, sizeof a)
#define CPY(a, q) memcpy(a, q, sizeof a)
#define PCT __builtin_popcount
const int N = 1e6 + 5, M = 1e6 + 5;
const int mod1 = 1e9 + 7, mod2 = 998244353, mod = 1e9 + 7;
const long long inf = 1e18;
const int dx[] = {-1, -1, -1, 0, 0, 0, 1, 1, 1};
const int dy[] = {-1, 0, 1, -1, 0, 1, -1, 0, 1};
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
int n, cnt[50];
unordered_map<string, int> id;
int C[140][140];
void init() {
id["1m"] = 1;
id["2m"] = 2;
id["3m"] = 3;
id["4m"] = 4;
id["5m"] = 5;
id["6m"] = 6;
id["7m"] = 7;
id["8m"] = 8;
id["9m"] = 9;
id["1s"] = 10;
id["2s"] = 11;
id["3s"] = 12;
id["4s"] = 13;
id["5s"] = 14;
id["6s"] = 15;
id["7s"] = 16;
id["8s"] = 17;
id["9s"] = 18;
id["1p"] = 19;
id["2p"] = 20;
id["3p"] = 21;
id["4p"] = 22;
id["5p"] = 23;
id["6p"] = 24;
id["7p"] = 25;
id["8p"] = 26;
id["9p"] = 27;
id["1c"] = 28;
id["2c"] = 29;
id["3c"] = 30;
id["4c"] = 31;
id["5c"] = 32;
id["6c"] = 33;
id["7c"] = 34;
REP(i, 0, 136) {
C[i][0] = 1;
REP(j, 1, min(i, 14ll))
C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
}
}
int sev[40][10];
int calc_seven() {
sev[0][0] = 1;
REP(i, 1, 34)
REP(j, 0, 7) sev[i][j] = sev[i - 1][j] + sev[i - 1][j - 1] * C[cnt[i]][2];
return sev[34][7];
}
const int one_nine[] = {1, 9, 10, 18, 19, 27, 28, 29, 30, 31, 32, 33, 34};
int calc_one_nine() {
int ans = 0;
REP(i, 0, 12) {
int pri = 1;
REP(j, 0, 12) {
if (i == j)
pri = pri * C[cnt[one_nine[j]]][2];
else
pri = pri * C[cnt[one_nine[j]]][1];
}
ans += pri;
}
return ans;
}
int b[150], c[150];
int dp[10][10][10];
bool check(int x) {
if (x == 3) {
REP(j, 1, 9) if (b[x * 9 + j] % 3) return 0;
return 1;
}
REP(j, 1, 9) c[x * 9 + j] = b[x * 9 + j];
REP(j, 1, 9) {
if (c[x * 9 + j] < 0) return 0;
c[x * 9 + j] %= 3;
if (j > 7 && c[x * 9 + j]) return 0;
c[x * 9 + j + 1] -= c[x * 9 + j];
c[x * 9 + j + 2] -= c[x * 9 + j];
}
return 1;
}
void calc(int x, int s, int res) {
if (s % 3 == 2) {
bool findp = 0;
REP(j, 1, 9) {
if (b[x * 9 + j] >= 2) {
b[x * 9 + j] -= 2;
if (check(x)) dp[x][s / 3][1] += res, findp = 1;
b[x * 9 + j] += 2;
if (findp) break;
}
}
} else if (check(x))
dp[x][s / 3][0] += res;
}
void dfs(int x, int y, int s, int binom) {
if (y > 9) {
if (s % 3 != 1) calc(x, s, binom);
return;
}
for (int k = 0; k + s <= 14 && k <= cnt[x * 9 + y]; k++) {
b[x * 9 + y] = k;
dfs(x, y + 1, s + k, binom * C[cnt[x * 9 + y]][k]);
}
}
int calc_rong() {
REP(i, 0, 3) dfs(i, 1, 0, 1);
// REP(i, 0, 3) REP(j, 0, 4) REP(k, 0, 1) cerr << dp[i][j][k] << '\n';
int ans = 0;
REP(s1, 0, 4)
REP(s2, 0, 4) REP(s3, 0, 4) REP(s4, 0, 4) // 面子
REP(i, 0, 1) REP(j, 0, 1) REP(k, 0, 1) REP(l, 0, 1) // 带/不带雀头
if (s1 + s2 + s3 + s4 == 4 && i + j + k + l == 1) ans +=
dp[0][s1][i] * dp[1][s2][j] * dp[2][s3][k] * dp[3][s4][l];
return ans;
}
int two_cup(int x, int y) {
int ans = 0;
REP(i, 0, 2) REP(j, 1, 7) REP(k, j + 3, 7) {
if (x == i && (y >= j - 1 && y <= j + 2 || y >= k - 1 && y <= k + 2))
continue;
ans += C[cnt[x * 9 + y]][2] * C[cnt[i * 9 + j]][2] *
C[cnt[i * 9 + j + 1]][2] * C[cnt[i * 9 + j + 2]][2] *
C[cnt[i * 9 + k]][2] * C[cnt[i * 9 + k + 1]][2] *
C[cnt[i * 9 + k + 2]][2];
}
// 同一花色,不能有重叠
REP(i, 0, 2) REP(j, 1, 7) {
if (x == i && (y >= j - 1 && y <= j + 2)) continue;
REP(ii, i + 1, 2) REP(k, 1, 7) {
if (x == ii && (y >= k - 1 && y <= k + 2)) continue;
ans += C[cnt[x * 9 + y]][2] * C[cnt[i * 9 + j]][2] *
C[cnt[i * 9 + j + 1]][2] * C[cnt[i * 9 + j + 2]][2] *
C[cnt[ii * 9 + k]][2] * C[cnt[ii * 9 + k + 1]][2] *
C[cnt[ii * 9 + k + 2]][2];
}
}
return ans;
}
int calc_two_cup() {
int ans = 0;
REP(i, 0, 3) REP(j, 1, 9) if (cnt[i * 9 + j] >= 2) ans += two_cup(i, j);
return ans;
}
void Solve() {
cin >> n;
// cerr << n << ' ' << C[n][14] << '\n';
CLR(cnt), CLR(dp), CLR(sev);
REP(i, 1, n) {
string s;
cin >> s;
cnt[id[s]]++;
}
// cerr << calc_seven() + calc_one_nine() - calc_two_cup() + calc_rong() <<
// '\n';
int ans = calc_seven() + calc_one_nine() + calc_rong() - calc_two_cup();
int gd = __gcd(ans, C[n][14]);
cout << ans / gd << '/' << C[n][14] / gd << '\n';
}
signed main() {
// freopen("z.in", "r", stdin);
// freopen("z.out", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int T = 1;
init();
cin >> T;
while (T--) {
Solve();
}
return 0;
}
詳細信息
Pretests
Final Tests
Test #1:
score: 10
Accepted
time: 1ms
memory: 3828kb
input:
10 20 4s 4p 3s 5s 1c 9p 2m 6s 2p 9m 8p 8m 7m 1p 6s 6m 5m 5p 4m 7p 17 1c 8m 3m 6s 1c 6c 6c 8m 3c 8p 7p 6c 4p 2m 5s 7p 7s 18 3p 6s 4s 3m 2p 7c 7p 7p 6s 2m 5c 8m 1p 2s 8s 3c 2c 4p 16 8p 2c 7m 4s 3p 7m 3s 3m 7s 2m 5c 4m 3c 5p 1m 1m 19 3c 6s 9m 7c 4c 8p 5s 3m 4c 1c 8m 1s 8p 4s 6s 8p 5s 3c 9m 18 2m 4m 7c ...
output:
1/38760 0/1 0/1 0/1 0/1 0/1 0/1 0/1 0/1 1/1
result:
ok 10 lines
Test #2:
score: 10
Accepted
time: 1ms
memory: 3828kb
input:
10 20 9m 3c 7c 5s 2p 9p 1s 9s 8p 6p 3s 6c 2p 1s 5p 2c 2m 2m 8p 9s 19 1p 6p 5s 6s 1c 2m 1p 8m 5s 4s 3c 2c 3p 3p 7c 7s 4c 6s 1m 22 7c 8m 5m 2m 7m 2p 5p 8m 1c 3s 6m 8p 5c 3p 5s 9s 7m 8s 9m 6s 4c 3p 25 3m 8m 9p 7p 4s 6p 4m 2p 2m 7m 2p 4c 6m 8s 7c 4s 7s 6s 4p 9m 7s 6p 5p 3p 5c 23 5m 7s 9m 8m 6c 5c 3p 7c ...
output:
0/1 0/1 0/1 1/44574 0/1 4/159885 0/1 0/1 0/1 0/1
result:
ok 10 lines
Test #3:
score: 10
Accepted
time: 1ms
memory: 3824kb
input:
10 23 7c 4c 7s 8p 3s 5c 1s 4m 4s 4s 5c 1p 7c 4p 8s 6p 7s 1p 1m 2m 6m 9p 2s 22 4c 7p 3m 6m 5m 3m 1m 5c 8m 9p 5c 1p 1p 5m 6s 3p 8m 7p 1c 2c 4p 5m 25 7s 2m 1m 3p 9s 5s 8p 4s 4s 4m 8s 2p 8m 5m 1c 1m 9p 2s 1s 1p 3m 2c 2c 4c 8s 20 9p 6c 1p 3c 6p 8p 3s 5m 4s 1c 1s 3s 4m 2m 2s 6p 8p 2c 4s 7p 22 5p 5s 4m 6m ...
output:
0/1 0/1 0/1 0/1 1/319770 0/1 0/1 0/1 0/1 0/1
result:
ok 10 lines
Test #4:
score: 10
Accepted
time: 1ms
memory: 3828kb
input:
10 19 6m 3c 8p 5s 1m 8m 7c 1m 3s 6p 1s 5c 9m 4p 7p 4p 2p 3c 6s 24 7s 6m 4m 8s 3s 1s 1s 2m 1m 5m 5p 6s 4c 5m 3m 7p 1c 4c 7s 4s 2m 8p 9p 5p 25 8m 1s 3c 4m 4m 6p 8p 2p 8p 9m 9p 3p 1p 9s 6s 4c 4p 5p 7m 7p 4p 7s 6c 2m 6p 25 6s 2p 3p 5m 4s 7m 9p 8s 4p 9m 7s 3c 1m 5p 2c 2s 8p 7p 3s 3m 2m 7p 4c 5m 4p 20 3c ...
output:
0/1 1/81719 3/742900 3/371450 0/1 0/1 0/1 0/1 0/1 0/1
result:
ok 10 lines
Test #5:
score: 10
Accepted
time: 224ms
memory: 3880kb
input:
10 109 5c 3p 4c 8s 3s 6s 7s 1s 3c 7p 4p 6s 3s 5s 1c 5s 7m 3c 6c 3m 9p 7c 9p 7c 3s 2c 4m 2s 1c 1m 6m 1m 2s 1s 1p 2p 7c 4s 3p 9m 2m 8p 5c 8p 1p 3p 5m 4m 6c 7s 3m 2p 4s 8p 6m 6p 6s 7p 9s 7m 6c 4s 4c 3c 4p 3c 8m 7p 8m 7s 3m 3s 2c 9m 8m 2c 3m 9p 6m 1s 8s 6s 7m 1m 6c 4p 5m 8m 2s 8s 2m 1p 7s 5p 5c 5p 2p 1p...
output:
438517325999/160330885263858960 5519303885/1767477707092944 315803459/210200461893180 1113059528533/404822104630406520 100726669633/44186942677323600 1800166337/584725152763800 247005179741/91748617512913200 40299842873/12428282928826440 118862116391/59458448728028700 2580573199/868119825121065
result:
ok 10 lines
Test #6:
score: 10
Accepted
time: 299ms
memory: 3828kb
input:
10 103 1c 3p 6m 1s 2m 7m 1c 9s 2s 3c 6p 7m 3c 9s 5p 1p 8p 1s 4c 8s 1m 1p 7s 6p 3c 2c 8m 3p 4s 3m 7p 6p 7p 1c 2s 8m 7s 7c 5p 1m 2p 6c 7m 5c 7p 4c 2s 6c 3m 3m 5s 9p 9s 1s 4p 7m 6s 3s 7s 9m 8p 4c 1m 8m 8s 8p 5s 6s 4p 3m 3s 7c 6c 8s 5c 2p 7c 4s 5m 4m 9p 7s 3p 4c 6c 5m 7p 9m 7c 8m 1s 2c 9s 5m 1p 5c 3s 6s...
output:
4357204237/2023866562784850 923931927481/347808183330273600 57714372151/17427686431277403 300638747/144154304891880 120055658171/38320539030548190 300343959787/118654754805463980 412046647693/189250121876392170 517695872597/137118194912492700 18873223157/5997113535284730 316898500244/83676706780057695
result:
ok 10 lines
Test #7:
score: 10
Accepted
time: 476ms
memory: 3824kb
input:
10 133 1s 1s 7p 4s 1p 9s 7m 3p 6s 8s 2s 9p 3s 7s 8s 2m 4p 6m 7c 9s 7m 1c 6p 5p 5m 5p 1c 3p 1m 3s 9s 5c 2m 5s 9s 4p 4m 6c 6s 3s 3m 5s 8s 6m 2c 6p 4p 5p 6c 8m 4c 4p 8p 7c 1s 9p 1p 2c 4c 9m 1m 5c 2m 7c 8p 3p 2p 2s 4m 1m 1p 7p 8m 3c 2p 6m 1m 6s 9m 7m 5m 6p 7m 5m 1c 3m 3p 7p 3c 5s 8s 1c 7s 2s 2p 2m 4m 9m...
output:
49330101751/15939248518584875 544160045501/192992682900247428 4944118051151/1708687441192298600 14272852777/4980266365168215 244079458745/104349775513954302 1178845800113/347808183330273600 409704617233/124463414269524000 790856287777/260874438784885755 16282623809/5848263118189316 2143179701279/708...
result:
ok 10 lines
Test #8:
score: 10
Accepted
time: 480ms
memory: 4032kb
input:
10 126 5p 5c 3c 1p 3m 8m 4p 5p 3s 7p 3s 5p 6p 7p 4p 4s 3p 8p 8m 2m 1p 4m 1c 2s 9p 5c 4m 1s 8p 6s 9s 6c 5p 3s 7c 1m 4s 5c 7p 7c 5s 5m 2m 6s 7m 4s 8s 9m 2p 7m 5s 3c 9m 4p 4c 2s 9p 4p 6m 2s 3p 6m 1p 3m 5m 2c 2p 1s 1p 8p 3s 4c 1s 6s 6p 9m 9m 1c 4s 8s 9p 4m 7c 6c 5m 6s 7m 1m 2m 3p 1m 6c 3m 7s 1c 5s 9s 8s...
output:
1769364720488/459365261817235125 132486320564/47520544325920875 95007114903/33735175385867210 3834820426178/1378095785451705375 4207030689371/1378095785451705375 1995823601647/684548778482382000 10045994464373/3060335715568296000 3901375737747/1223890240316986000 145058089283/63083373958797390 49271...
result:
ok 10 lines
Test #9:
score: 10
Accepted
time: 504ms
memory: 3892kb
input:
10 125 4m 6s 3c 5m 1p 3s 1c 8s 1s 4c 5m 9s 8s 1s 3s 1m 6m 3m 9m 5s 1p 9p 6c 7m 3c 2p 3p 6c 2m 2m 2c 8p 3p 6p 9s 7s 1s 4m 7m 7p 2s 5s 3m 4s 5c 9s 3s 6c 2c 9m 7s 4p 5m 6s 1m 7p 6p 2p 3s 5p 2p 7m 6p 8p 2c 8s 5s 7p 6c 2s 8m 1s 8s 4s 6s 6s 2c 8p 8m 5p 1p 3c 3c 5c 3p 4p 1p 7m 5s 8p 6m 1c 2p 5c 6p 4p 5p 7s...
output:
3994538145151/1224974031512627000 164912958069/72057295971331000 4513127238533/1378095785451705375 36762818149/12709245430355940 5058554068093/1708687441192298600 8187159059951/2447780480633972000 105676567673/30597256007924650 1511235978388/516277772130874875 172118211457/55123831418068215 96726780...
result:
ok 10 lines
Test #10:
score: 10
Accepted
time: 594ms
memory: 4032kb
input:
10 136 7s 2p 1s 8m 9m 2c 9s 6p 7s 9s 4p 3p 4m 4p 7p 5p 4p 2c 3s 4m 1m 9p 4c 6c 2m 8s 3s 6s 6m 5m 1p 5s 8m 9p 2m 6p 6m 3s 1m 8s 4c 4m 7c 3c 3m 2p 5m 3p 1s 8p 6p 6m 2p 6s 7m 2p 3c 5s 3m 2s 6c 9m 8s 7c 2s 4p 8m 1s 6c 3m 2c 1p 1s 7c 5p 9m 3p 7s 4s 3m 9s 7p 9p 5m 6c 4s 5c 6s 1m 6m 1c 7m 8p 9s 1p 2m 3s 7s...
output:
2143179701279/708384171528036000 98667734899/31773113575889850 2268378791823/683474976476919440 1427183516417/476596703638347750 2143179701279/708384171528036000 1369334608447/423641514345198000 1427183516417/476596703638347750 98667734899/31773113575889850 2143179701279/708384171528036000 214317970...
result:
ok 10 lines