P7794 [COCI2014-2015#7] JANJE

· · 题解

Content

有 8 张没有颜色的图片，给你两个正整数 n 和 k，表示有 k 种互不相同染料，涂在第 n 张图上有几种上色方式。当然，是有一些格式要求的：

以下区域不是要涂色的区域，也不会被算作一个涂色的区域：

Solution

很明显这些图都可以用 3 种颜色来涂色，都不可以用 1 种颜色来涂色，但在 1、3、4、8 中可以用两种颜色，因为它的每个区域都只与另外一个区域相邻。

一：

这幅图总共有 20 个区域可涂色。

三种颜色：

设头部有 3 种涂色方式，则剩下的每个区域都会有 2 种涂色方式，也就是 3 \times 2^{19} \times C_k^3 种方式。

两种颜色：

设头部有 2 种涂色方式，则剩下的每个区域都会有 1 种涂色方式，也就是 2 \times C_k^2 种方式。

总的公式也就是 3 \times 2^{19} \times C_k^3 + 2 \times C_k^2，但可能抽取的两种颜色跟抽取的三种颜色中的其中两个一样就要减去 A_3^2。

公式：

(3 \times 2^{19} - A_3^2) \times C_k^3 + 2 \times C_k^2

二：

这幅图总共有 8 个区域可涂色。

设房子顶部有 3 种涂色方式，则下面的主体和顶上的窗户有 2 种涂色方式，门和两个窗户的一半也有 2 种涂色方式，两个窗户的另外一半就只有 1 种涂色方式。

公式：

3 \times 2^5 \times C_k^3

三：

这幅图总共有 4 个区域可涂色。

三种颜色：

设外部有 3 种涂色方式，则下面的圆和圆里面的两个圆都有 2 种涂色方式。

二种颜色：

设外部有 2 种涂色方式，则下面的圆和圆里面的两个小圆都有 1 种涂色方式。

公式：

(3 \times 2^3 - A_3^2) \times C_k^3 + 2 \times C_k^2

四：

这幅图总共有 14 个区域可涂色。

三种颜色：

设头部有 3 种涂色方式，则下面的每个圆和圆里面的每个小圆都有 2 种涂色方式。

二种颜色：

设头部有 2 种涂色方式，则下面的每个圆和圆里面的每个小圆都有 1 种涂色方式。

公式：

(3 \times 2^{13} - A_3^2) \times C_k^3 + 2 \times C_k^2

五：

这幅图总共有 5 个区域可涂色。

设最上面的图形有 3 种涂色方式，则最下面的图形有 2 种涂色方式，再里面的圆有一半与外围的图形都有 1 种涂色方式，还有一半有 2 种涂色方式。

公式：

3 \times 2^2 \times C_k^3

六：

这幅图总共有 55 个区域可涂色。

这个图形看似比之前的难多了，其实一推简单多了。

设最顶上的正方形有 3 种涂色方式，则最左边的一个正方形有 2 种涂色方式，可以发现剩下的每个正方形都与至少两个涂过颜色的相邻正方形相邻，所以都只有 1 种涂色方式。

公式：

3 \times 2^1 \times C_k^3

七：

这幅图总共有 8 个区域可涂色。

设花瓣有 3 种涂色方式，则花的中心和花杆就有 2 种涂色方式，两个草的一半和花盆也有 2 种涂色方式，两个草的剩下一半有 1 种涂色方式。

公式：

3 \times 2^5 \times C_k^3

八：

这幅图总共有 30 个区域可涂色。

这张图我最开始以为是

3 \times 2^{28} \times C_k^3

然后发现还少考虑了首和尾下面的一个区域颜色相同（尾有两种涂色方式）的情况，实在算不出来，便看了AstralMetal的题解，才知道了有 1073741826 种涂色方式。因为它也可以只用 2 种颜色涂色，所以还要加上 2 \times C_k^2。

公式：

(1073741826 - A_3^2) \times C_k^3 + 2 \times C_k^2 = (1073741826 - 3 \times 2) \times k \times (k - 1) \times (k - 2) \div 3 \div 2 \div 1 + 2 \times k \times (k - 1) \div 2 \div 1 = (1073741826 - 6) \times k \times (k - 1) \times (k - 2) \div 6 + 2 \times k \times (k-1) \div 2 = 1073741820 \times k \times (k - 1) \times (k - 2) \div 6 + k \times (k - 1) = 178956970 \times k \times (k - 1) \times (k - 2) + k \times (k - 1)

除了第 8 幅图外，其它的 7 幅图都可以用一个公式来表示，我们可以用 flag_n 来表示第 n 幅图是否可以用两种颜色涂色，用 cnt_n 来表示 2^x（x 是在第 n 幅图中有 2 种涂色方式的区域个数）。

公式：

(3 \times cnt_n - A_3^2 \times flag_n) \times C_k^3 + flag_n \times 2 \times C_k^2 = (3 \times cnt_n - 3 \times 2 \times flag_n) \times k \times (k - 1) \times (k - 2) \div 3 \div 2 \div 1 + flag_n \times 2 \times k \times (k - 1) \div 2 \div 1 = (3 \times cnt_n - 6 \times flag_n) \times k \times (k - 1) \times (k - 2) \div 6 + flag_n \times 2 \times k \times (k - 1) \div 2 = 3 \times (cnt_n - 2 \times flag_n) \times k \times (k - 1) \times (k - 2) \div 6 + flag_n \times k \times (k - 1) = (cnt_n - 2 \times flag_n) \times k \times (k - 1) \times (k - 2) \div 2 + flag_n \times k \times (k - 1)

Code

#include<bits/stdc++.h>
using namespace std;
int n,k;
bool flag[8]={0,1,0,1,1,0,0,0};
long long cnt[8]={0,1<<19,1<<5,1<<3,1<<13,1<<2,1<<1,1<<5};
//注意位运算符优先级较小，需要用括号。 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>k;
    if(n==8)
        cout<<178956970ll*k*(k-1)*(k-2)+k*(k-1);
    else
        cout<<(cnt[n]-flag[n]*2)*k*(k-1)*(k-2)/2+flag[n]*k*(k-1);
    return 0;
}