#Codeforces Round #341 (Div. 2)

@(E ACMer)

• • C Wet Shark and Flowers機率容斥
  • E Wet Shark and Blocksdp 矩陣快速幂

C. Wet Shark and Flowers（機率+容斥）

題意：先給一個素數 p ，有n個人，圍成一圈，每個人有會等機率的取自己區間中的一個數，如果兩個相鄰的人的數的乘積能被p整除，那麼這兩個人就會一人獲得1000元，問你整個圈的人期望得到的錢是多少？

分析：首先，根據素數的性質：兩個數的乘積要能被 p 整除，等價于兩個數中至少一個數能被p整除。

那麼對于第 i 個人我們就開始研究，它為能被p整除的機率:

Pi=r/p−(l−1)/p

那麼根據容斥原理兩個相鄰的人獲得的錢的期望就是： (Pi+Pi+1−Pi∗Pi+1)∗2000

比賽的時候比較慌，連每個人的機率都沒有分析清楚=——=，直接YY了一個方法，下來才想到正解。比賽的時候應該冷靜地想清楚思路。

我的Code如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <stack>
#include <vector>
#include <string>
#include <queue>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
typedef pair<int, int> pii;
typedef unsigned long long ull;
typedef long long ll;
typedef vector<int> vi;
#define xx first
#define yy second
#define rep(i, a, n) for (int i = a; i < n; i++)
#define sa(n) scanf("%d", &(n))
#define vep(c) for(decltype((c).begin()) it = (c).begin(); it != (c).end(); it++)
const int mod = int() + , INF = , maxn =  + ;
int a[maxn], b[maxn];
int n, p;

int doit(int l, int r) {
    return r / p - (l - ) / p;
}

int main(void)
{
    cin >> n >> p;
    double temp = ;
    double ans = , q = ;
    for (int i = ; i < n; i++) {
        int x, y;
        sa(x), sa(y);
        a[i] = doit(x, y);
        b[i] = y - x + ;
        // cout << a[i] << " " << b[i] << endl;
        // temp *= (y - x + 1);
    }
    for (int i = ; i < n; i++) {
        ans = double(a[i]) * b[i +  == n ?  : i + ] + double(a[i +  == n ?  : i + ]) * (b[i] - a[i]);
        temp = double(b[i]) * b[i +  == n ?  : i + ];
        //if (ans > temp) cout << i << ": " <<  a[i] << " " << b[i] << endl;
        q += ans / temp * ;
    }

    printf("%.14f\n", q);
    return ;
}
           

E. Wet Shark and Blocks（dp + 矩陣快速幂）

題意：有一個長度為 n 的數列，有b組相同的這樣的數列，從每組數列中選取一個數，串成的一個長數字，問取餘 x 等于k的數字有多少個？

分析：

很容易想到狀态定義: dp[i][k] 表示前 i 組數列構成的取餘x餘數為k的數字的個數.

那麼根據大數取餘的性質容易有:

dp[i][k]=∑dp[i−1][j]∗cnt[a] (其中(j∗10+a)%x=j 且a∈[0,9])

這樣就是求 dp[b][k] ,直接暴力dp顯然不能, 109 的資料範圍,會想到矩陣快速幂來優化,直接是初始狀态乘以轉移矩陣的 b 次方.

那麼如何構造這個轉移矩陣?

首先根據矩陣乘法的性質,轉移矩陣move[k][j]=x,代表的意思是把原矩陣的 i 列的x倍加到新矩陣的第 j 列上.

這時觀察狀态轉移方程,我們需要的是将原矩陣的第j列的 cnt[a] 倍加到新矩陣的第 k 列上(其中(j∗10+a)%x=j 且a∈[0,9]),這樣令: move[k][j]=cnt[a], (其中(j∗10+a)%x=j 且a∈[0,9])

就構造好了轉移矩陣.

Code如下:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <stack>
#include <vector>
#include <string>
#include <queue>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
typedef pair<int, int> pii;
typedef long long ull;
typedef long long ll;
typedef vector<int> vi;
#define xx first
#define yy second
#define rep(i, a, n) for (int i = a; i < n; i++)
#define sa(n) scanf("%d", &(n))
#define vep(c) for(decltype((c).begin()) it = (c).begin(); it != (c).end(); it++)
const int mod = int() + , INF = , maxn =  + ;
int x;

//建立一個矩陣類
class matrix
{
public:
    ll v[][];

    matrix(int y) {
        for (int i = ; i < ; i++) {
            for (int j = ; j < ; j++) {
                v[i][j] = i == j ? y : ;
            }
        }
    }

    //矩陣乘法,操作符重載
    matrix operator*(matrix& temp) {
        matrix ret();
        for (int i = ; i < x; i++) {
            for (int j = ; j < x; j++) {
                for (int k = ; k < x; k++) {
                    ret.v[i][j] = (ret.v[i][j] + l * v[i][k] * temp.v[k][j]) % mod;
                }
            }
        }
        return ret;
    }

    //矩陣乘方,操作符重載
    matrix operator^(int n) {
        matrix ret(), b = *this;
        while (n) {
            if (n & ) ret = ret * b;
            b = b * b;
            n >>= ;
        }
        return ret;
    }
};


int main(void)
{
    //freopen("in.txt", "r", stdin);
   // freopen("out.txt", "w", stdout);
    int n, b, k;
    cin >> n >> b >> k >> x;

    int cnt[];//對于每組數列,我們隻關心每個數的個數   
    memset(cnt, , sizeof(cnt));
    for (int i = ; i < n; i++) {
        int x;
        sa(x);
        cnt[x]++;
    }


    matrix move();

    //構造轉移矩陣
    for (int i = ; i < x; i++) {
        for (int j = ; j < ; j++) {
            move.v[i][(i *  + j) % x] += cnt[j];
        }
    }

    move = move ^ b;
    cout << move.v[][k] << endl;
}