“蔚来杯“2022牛客暑期多校训练营1——I题：Chiitoitsu（详解+知识点拆析）

I：Chiitoitsu

链接：https://ac.nowcoder.com/acm/contest/33186/I
来源：牛客网

前置知识

1. 同余
   如果a和b除以c的余数相同，就说a和b关于模c同余，记作 a≡b(mod c)。
   如果两个数a和b的差能够被m整除，那么就说a和b对模数m同余 28≡13(mod 5)
2. 逆元
   一个数有逆元的充分必要条件是 gcd(a,n)=1。
   正整数 a, n，如果有 ax ≡ 1(mod n)，则称 x 的最小正整数解为 a 模 n的逆元。

结合题目 (a / b)%p

由于是对除法取模，往往容易出现精度问题，不得不用高精除法但是那会加重代码负担，所以我们可以通过使用逆元把除法取余转化为乘法取余。

3. 费马小定理求逆元

费马小定理证明

求逆元（注意区分逆和-1次方）

4. 快速幂
快速幂（Exponentiation by squaring，平方求幂）是一种简单而有效的小算法，它可以以O(logn)的时间复杂度计算乘方。快速幂不仅本身非常常见，而且后续很多算法也都会用到快速幂。

快速幂模板

//x^n
ll qkp(ll x,ll n,ll p)
{
	ll ans = 1;
	while(n > 0)
	{
		if(n&1)//指数是奇数
			ans = ans*x %p;	
        n >>= 1;//二进制位置左移 ,指数除以
		x = x*x %p;//底数平方
	}
	return ans;	
} 
1
2
3
4
5
6
7
8
9
10
11
12
13

结合题目上文求逆元为 b的p-2次方

题目为多组样例题目，且范围为 1≤T≤1e5，当执行多次求幂肯定会TLE则使用快速幂解决。

思

关于状态方程dp[i][j]表示手上还有i张单牌，牌堆还有j张牌时还需要摸牌次数的期末值。
每次摸牌会有两种情况但无论哪种情况牌堆的牌数都会减少一张（j-1）：

• 摸一张牌和手牌可以凑成一对，则手上单牌减少两张（i-2）再乘以摸到可以凑对牌的概率（i*3）/ j ;
• 摸一张牌和手牌不一样，任然为单牌，在“上帝视角”的基础上可保证手上单牌数不发生变动（增加）再乘以摸到其余单牌的概率（j - 3 * i）/ j
  

码

# include 
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;

int t;
string s;
int sum = 34 * 4 - 13;
ll dp[15][150];//手上有i张，牌堆里还剩j张牌时还需要摸牌的期望次数

ll qkm(ll a,ll n){
    ll ans = 1;
    while(n > 0){
        if(n & 1) ans = ans * a % mod;
        n >>= 1;
        a = a * a %  mod;
    }
    return ans;
}

void init(){
    //为啥从三开始：当牌堆剩2两张牌时一定能胡
    //初始化dp[1][j]：防止 i-2为负 的情况。
    for(int j=3;j<=sum;j++) dp[1][j] = (1 + (((j - 3) * qkm(j,mod-2) % mod) * dp[1][j-1]) % mod) % mod;
    //手上为单牌的情况之后1、3、5、7、9、11、13,1已经初始化过了，所以i从三开始
    for(int i=3;i<=13;i+=2){
        for(int j=3;j<=sum;j++){
            dp[i][j] =  ((1 + ((((j - 3 * i) * qkm(j,mod-2) % mod) * dp[i][j-1]) % mod)) 
                        + 
                        ((((3 * i) * qkm(j,mod-2) % mod) * dp[i-2][j-1]) % mod)) % mod;
        }
    }
}

int main(){
    cin >> t;
    //处理所有可能的dp结果
    init();
    for(int k=1;k<=t;k++){
        cin >> s;
        map<string,int> mp;//用于统计单牌数
        for(int i=0;i<s.size();i+=2){
            string res = "";
            res += s[i];
            res += s[i+1];
            mp[res]++;
        }
        int single = 0;
        for(auto it : mp)
            //cout << it.first << ":" << it.second << endl;
            if(it.second == 1) ++single;
        //cout << single << endl;
        cout << "Case #" << k << ": " << dp[single][sum] << endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56