QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#55884#2576. 麻将Steven_lzx100 ✓107ms36188kbC++177.9kb2022-10-15 15:29:182022-10-15 15:29:20

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-15 15:29:20]
  • Judged
  • Verdict: 100
  • Time: 107ms
  • Memory: 36188kb
Show
  • [2022-10-15 15:29:18]
  • Submitted

answer

// P5279 [ZJOI2019]麻将
#include <bits/stdc++.h>
namespace THELOSTWEAK
{
#define MOD 998244353
#define chkmax(x, y) (x < (y) && (x = (y)))
#define add(x, y) ((x += (y)) >= MOD && (x -= MOD))
#define qinv(x) qpow(x, MOD - 2)
    using namespace std;
    int n, m, a[100 + 5], Fac[400 + 5], Inv[400 + 5];
    inline int qpow(register int x, register int y)
    {
        register int t = 1;
        while (y)
            y & 1 && (t = 1LL * t * x % MOD), x = 1LL * x * x % MOD, y >>= 1;
        return t;
    }
    class HuAutomation //胡牌自动机
    {
    private:
#define SZ 2092                                                      //实测自动机大小
#define C(x, y) (1LL * Fac[x] * Inv[y] % MOD * Inv[(x) - (y)] % MOD) //组合数
#define Pos(x) (p.count(x) ? p[x] : (O[p[x] = ++tot] = x, tot))      //求节点编号，若不存在则新建一个
#define Extend(x)           \
    for (j = 0; j ^ 5; ++j) \
        O[x].S[j] = Pos(O[x] + j); //扩展
        class Mat                  //矩阵
        {
        private:
#define CM const Mat &
#define S (i + j + k)
            int f[3][3];

        public:
            inline Mat()
            {
                for (register int i = 0, j; i ^ 3; ++i)
                {
                    for (j = 0; j ^ 3; ++j)
                    {
                        f[i][j] = -1;
                    }
                }
                return;
            }
            inline int *operator[](const int &x)
            {
                return f[x];
            }
            inline bool operator!=(Mat o) const
            {
                for (register int i = 0, j; i ^ 3; ++i)
                {
                    for (j = 0; j ^ 3; ++j)
                    {
                        if (f[i][j] ^ o[i][j])
                        {
                            return 1;
                        }
                    }
                }
                return 0;
            } //不等于
            inline bool operator<(Mat o) const
            {
                for (register int i = 0, j; i ^ 3; ++i)
                {
                    for (j = 0; j ^ 3; ++j)
                    {
                        if (f[i][j] ^ o[i][j])
                        {
                            return f[i][j] < o[i][j];
                        }
                    }
                }
                return false;
            } //比大小，用于map
            inline bool Check() const
            {
                for (register int i = 0, j; i ^ 3; ++i)
                {
                    for (j = 0; j ^ 3; ++j)
                    {
                        if (f[i][j] > 3)
                        {
                            return 1;
                        }
                    }
                }
                return 0;
            }                                   //判断是否能胡
            inline void F5(Mat o, const int &t) //更新
            {
                for (register int i = 0, j; i ^ 3; ++i)
                {
                    for (j = 0; j ^ 3; ++j)
                    {
                        if (~o[i][j])
                        {
                            for (register int k = 0; k ^ 3 && S <= t; ++k) // i,j,k分别枚举用于拼面子、用于保留(i-1,i)、用于保留i和直接拼面子的牌数
                            {
                                chkmax(f[j][k], min(i + o[i][j] + (t - S) / 3, 4)); //转移更新信息（要向4取min是因为大于4没有意义，同时提高效率）
                            }
                        }
                    }
                }
                return;
            }
#undef S
        };
        struct node //存储一个节点的信息
        {
            int t, S[5];
            Mat P[2];
            inline node()
            {
                t = S[0] = S[1] = S[2] = S[3] = S[4] = 0;
                P[0] = P[1] = Mat();
            }
            inline bool operator<(const node &o) const //用于map
            {
                return t ^ o.t ? t < o.t : (P[0] != o.P[0] ? P[0] < o.P[0] : (P[1] != o.P[1] ? P[1] < o.P[1] : 0));
            }
            inline node operator+(const int &x) const //加上x张新牌
            {
                if (IsHu())
                {
                    return Hu();
                }
                node res; //如果已经胡了直接返回
                res.P[0].F5(P[0], x);
                res.P[1].F5(P[1], x);
                x > 1 && (res.P[1].F5(P[0], x - 2), 0); //进行转移
                res.t = t + (x > 1);
                res.IsHu() && (res = Hu(), 0);
                return res; //统计对子数，然后判断是否胡
            }
            inline bool IsHu() const
            {
                return !~t || t >= 7 || P[1].Check();
            } //已经胡或者七对子或者存在4个面子和1个对子
            inline node Hu() const
            {
                node x;
                return x.t = -1, x;
            } //胡牌的特殊标记
        } O[SZ + 5];
        map<node, int> p;
        inline node Begin()
        {
            node x;
            return x.P[0][0][0] = 0, x;
        } //初始状态
        inline node Hu()
        {
            node x;
            return x.t = -1, x;
        } //胡牌的特殊标记
    public:
        int tot, f[100 + 5][400 + 5][SZ + 5];
        inline void Build() //建自动机
        {
            register int i, j;
            p[O[1] = Begin()] = 1;
            p[O[2] = Hu()] = tot = 2; //建立初始状态和胡牌状态
            Extend(1);
            for (i = 3; i <= tot; ++i)
            {
                Extend(i); //对除第2个（胡牌）以外的其他状态进行扩展
            }
            return;
        }
        inline void DP() // DP求解答案
        {
            f[0][0][1] = 1;
            for (register int i = 1, j, k, t; i <= n; ++i)
            {
                for (j = m; ~j; --j) //枚举当前是第i张牌，共摸了j张牌
                {
                    for (k = 1; k <= tot; ++k)
                    {
                        if (f[i - 1][j][k])
                        {
                            for (t = 0; t <= 4 - a[i]; ++t) //枚举在胡牌自动机哪个节点上，以及现在摸的牌数
                            {
                                add(f[i][j + t][O[k].S[a[i] + t]], 1LL * f[i - 1][j][k] * C(4 - a[i], t) % MOD); //转移，注意乘上组合数系数
                            }
                        }
                    }
                }
            }
            return;
        }
    } H;
    inline void init(const int &x) //初始化
    {
        register int i;
        for (Fac[0] = i = 1; i <= x; ++i)
        {
            Fac[i] = 1LL * Fac[i - 1] * i % MOD; //初始化阶乘
        }
        for (Inv[x] = qinv(Fac[x]), i = x - 1; ~i; --i)
        {
            Inv[i] = 1LL * Inv[i + 1] * (i + 1) % MOD; //初始化阶乘逆元
        }
        return;
    }
#define calc(x, y) add(ans, 1LL * H.f[n][x][y] * Fac[i] % MOD * Fac[m - i] % MOD) //统计答案
    int main()
    {
        register int i, j, x, y, ans = 0;
        H.Build();
        scanf("%d", &n);
        for (i = 1; i <= 13; ++i)
        {
            scanf("%d%d", &x, &y);
            a[x]++;
        }
        m = (n << 2) - 13;
        init(m);
        H.DP();
        for (i = 1; i <= m; ++i)
        {
            for (calc(i, 1), j = 3; j <= H.tot; ++j)
            {
                calc(i, j); //统计答案，注意跳过2号节点
            }
        }
        printf("%lld", 1LL * ans * Inv[m] % MOD + 1);
        return 0; //输出答案，除以总状态数然后加1
    }
}
int main()
{
    return THELOSTWEAK::main();
}
/*
 * 洛谷
 * https://www.luogu.com.cn/problem/P5279
 * C++17 -O0
 * 2022.10.15
 */
Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 10
Accepted
time: 8ms
memory: 4484kb

input:

5
1 1
1 2
1 3
1 4
2 1
3 1
3 2
3 3
3 4
5 1
5 2
5 3
5 4

output:

570425346

result:

ok single line: '570425346'

Test #2:

score: 10
Accepted
time: 7ms
memory: 4488kb

input:

5
1 3
2 4
4 3
5 3
3 1
5 4
4 2
1 4
4 4
3 3
3 2
1 1
2 2

output:

713031682

result:

ok single line: '713031682'

Test #3:

score: 10
Accepted
time: 9ms
memory: 5288kb

input:

13
1 3
12 1
12 2
1 4
13 3
13 2
3 2
13 1
1 1
3 4
3 3
1 2
12 3

output:

868236068

result:

ok single line: '868236068'

Test #4:

score: 10
Accepted
time: 4ms
memory: 5196kb

input:

13
1 1
13 1
2 3
1 3
3 1
3 4
2 1
13 4
1 4
12 2
13 3
12 3
3 2

output:

234399821

result:

ok single line: '234399821'

Test #5:

score: 10
Accepted
time: 5ms
memory: 5252kb

input:

13
2 3
2 1
12 2
13 2
2 2
1 2
13 3
12 4
13 4
3 4
3 1
12 3
1 3

output:

892522858

result:

ok single line: '892522858'

Test #6:

score: 10
Accepted
time: 43ms
memory: 21704kb

input:

81
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

output:

152635587

result:

ok single line: '152635587'

Test #7:

score: 10
Accepted
time: 51ms
memory: 28080kb

input:

94
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

output:

339459976

result:

ok single line: '339459976'

Test #8:

score: 10
Accepted
time: 52ms
memory: 26720kb

input:

96
1 2
1 3
1 4
1 1
2 2
2 3
2 4
2 1
3 2
3 3
3 4
3 1
4 2

output:

230028597

result:

ok single line: '230028597'

Test #9:

score: 10
Accepted
time: 46ms
memory: 21116kb

input:

83
1 2
1 3
1 4
1 1
2 2
2 3
2 4
2 1
3 2
3 3
3 4
3 1
4 2

output:

967250236

result:

ok single line: '967250236'

Test #10:

score: 10
Accepted
time: 107ms
memory: 36188kb

input:

100
67 1
26 4
12 4
11 4
30 4
29 1
1 4
13 3
30 1
64 2
63 1
20 2
32 4

output:

345132636

result:

ok single line: '345132636'

Extra Test:

score: 0
Extra Test Passed
English 繁體中文 简体中文

Server Time: 2025-02-08 16:33:43 | OpenSource Project