自动搬运

查看原文

来自洛谷，原作者为

	皎月半洒花 在那之前，你要多想。

搬运于2025-08-24 22:10:06，当前版本为作者最后更新于2019-12-25 17:32:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

upd:题解区的 $\LaTeX$ 好像有 bug，改完之后如果还是gg请移步 $Link$

---

$\rm SNOI2019$ 纸牌

首先我觉得出题人肯定打过 CF Global Round 1 并且很可能在那场掉分了，可以戳这里 去康一下。

$\rm Algorithm · 1$

首先定义状态，$f_{i,j,k}$ 表示考虑了前 $i$ 大的，其中 $[i-1,i,i+1]$ 类型有 $j$ 个， $[i,i+1,i+2]$ 类型有 $k$ 个的方案数。发现这两类还是最多只会各有 $2$ 个。

然后就是考虑转移。发现还是要转移到 $[i+1,i+2,i+3]$ 去，那换言之就是枚举 $i+3$ 的个数。但是题目里面有限制 $k_i$ 至少要拿 $a_i$ 个，所以考虑这么转移，令 $s=j+k+l$，即顺子里面 $i+1$ 的个数 ：

$$f_{i+1,k,l} = \begin{cases}f_{i,j,k}\cdot (\lfloor \frac{c-s}{3}\rfloor + 1) , s\geq a_{i+1} \\ f_{i,j,k}\cdot (\lfloor \frac{c -(s+3\cdot \lceil \frac{a_{i+1}-s}{3}\rceil )}{3}\rfloor+1) , s< a_{i+1}\end{cases} $$

其中 $+1$ 代表题目中的 “空也算是一种方案”。第二个转移中，由于枚举的顺子个数小于必选的，那么就要把剩下的也选成刻子才行，所以就是 $3\cdot \lceil \frac{a_{i+1}-s}{3}\rceil$ ，即如果不足还要多选点。

写出代码来大概是这样：

inline int get_v(int x){
	x %= 3 ; 
	if (x == 2) return 1 ; 
	else if (x == 1) return 2 ; return 0 ; 
}
signed main(){
    cin >> N >> M >> T, dp[0][0][0] = 1 ;
    for (i = 1 ; i <= T ; ++ i) scanf("%lld%lld", &j, &k), Num[j] = k ;
    for (i = 1 ; i <= N ; ++ i)
        for (j = 0 ; j < 3 ; ++ j)
            for (k = 0 ; k < 3 ; ++ k)
                for (l = 0 ; l < 3 ; ++ l){
                    int now = j + k + l, dis ;
					if (M < now) continue ;
					if (Num[i] > now) dis = Num[i] + get_v(Num[i] - now) ; else dis = now ;
      				if (dis <= M) dp[i][k][l] = (dp[i][k][l] + dp[i - 1][j][k] * ((M - dis) / 3 + 1)) % Mod ;
				}
    cout << dp[N][0][0] << endl ; return 0 ;
}

可以过 $\rm Subtask~1,2,5$，共计 $55$ 分。

$\rm Algorithm ·2$

发现这东西转移只跟后两维有关，并且从 $i$ 转移到 $i+1$ 并没有什么障碍，于是考虑矩乘。

发现由于是 $i,j$ 转移到 $j,k$ ，故需要 $9\times 9$ 的矩阵来转移。然后对于每个状态考虑直接按行按列编号，转移就很简单了。

但问题在于要考虑约束，即每一位至少要选多少。这东西特判一下就可了。复杂度 $m\cdot 9^3+9^3\cdot \log n$.

然而似乎这东西可以一开始倍增出来转移矩阵……$\rm Anyhow$，并不会快多少，毕竟最后压力就在 $m$ 这边了。

LL n, m, c, x, y, lx, ly ;
struct matrix{
    int b[12][12] ;
    void clear(){ memset(b, 0, sizeof(b)) ; }
    void reset(){
        clear() ;
        for (int i = 0 ; i < 10 ; ++ i)
            b[i][i] = 1 ;
    }
    matrix friend operator * (const matrix &a, const matrix &b){
        matrix c ; c.clear() ;
        for (int i = 0 ; i < 10 ; ++ i)
            for (int j = 0 ; j < 10 ; ++ j)
                for (int k = 0 ; k < 10 ; ++ k)
                    c.b[i][j] = (c.b[i][j] + 1ll * a.b[i][k] * b.b[k][j] % Mod) % Mod ;
        return c ;
    }
}ans, unit, tmp ;

matrix expow(matrix a, LL b){
    matrix res ; res.reset() ;
    while (b){
        if (b & 1)
            res = res * a ;
        a = a * a ; b >>= 1 ;
    }
    return res ;
}
signed main(){
    cin >> n >> c >> m ; LL q ; //cout << n << endl ;
    ans.b[0][0] = 1 ; int i, j, k, l ;
    for (i = 0 ; i < 3 ; ++ i)
        for (j = 0 ; j < 3 ; ++ j)
            for (k = 0 ; k < 3 ; ++ k)
                if (i + j + k <= c)
                    unit.b[i * 3 + j][j * 3 + k] = (c - (i + j + k)) / 3ll + 1ll ;
    for (i = 1 ; i <= m ; ++ i){
        scanf("%lld%lld", &x, &y), tmp.clear() ;
        ans = ans * expow(unit, x - lx - 1) ;
        for (j = 0 ; j < 3 ; ++ j)
            for (k = 0 ; k < 3 ; ++ k)
                for (l = 0 ; l < 3 ; ++ l){
                    int s = j + k + l ;
                    if (s < y) s = y + ((s - y) % 3 + 3) % 3 ;
                    if (s <= c) tmp.b[j * 3 + k][k * 3 + l] = (c - s) / 3ll + 1ll ;
                }
        lx = x, ly = y, ans = ans * tmp ;
    }
    ans = ans * expow(unit, n - (LL)lx), cout << ans.b[0][0] << endl ; return 0 ;
}