22.07.18 Monday

"蔚来杯"2022牛客暑期多校训练营1
- DMocha and Railgun
- I Chiitoitsu
  
  code:

// #pragma GCC optimize(2)
#include <bits/stdc++.h>
#include <iostream>
#include <bitset>
#include <queue>
#include <cstdio>
#include <map>
#include <algorithm>
#include <stack>
// #include <random>
using namespace std;
#define int128 __int128_t
typedef long long ll;
// #define ll int
typedef long double ld;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef pair<P, ll> PP;
struct triplet
{
    ll first, second, third;
};
const ll INF = 1e9;
const ll MAXN = 1e7 + 5;
const ll MOD = 1e9 + 7;
const ll Base = 131;
// mt19937_64 mrand(random_device{}());
ll ExGCD(ll a, ll b, ll &x, ll &y)
{
    // x, y 为引用传参，故最终程序结束后，x,y会被赋值为可行解
    if (b == 0)
    {
        // 递归终点，ax+by=GCD(a,b)的b为0，故方程变为
        // ax=a，则可行解可以是 x=1, y=0
        x = 1, y = 0;
        return a;
    }
    ll d = ExGCD(b, a % b, x, y), t = x;
    x = y, y = t - a / b * x;
    return d; // 这里返回值是GCD(a,b)的结果，即最大公约数
}
ll ExGcdInv(ll a, ll b)
{
    ll x, y;
    ExGCD(a, b, x, y);
    return x;
}
int cnt[40];
int cal(string s)
{
    for (int i = 0; i <= 35; i++)
        cnt[i] = 0;
    for (int i = 1; i < (int)s.length(); i += 2)
    {
        if (s[i] == 'm')
            cnt[(s[i - 1] - '0')]++;
        if (s[i] == 'p')
            cnt[(s[i - 1] - '0' + 9)]++;
        if (s[i] == 's')
            cnt[(s[i - 1] - '0' + 18)]++;
        if (s[i] == 'z')
            cnt[(s[i - 1] - '0') + 27]++;
    }
    int result = 0;
    for (int i = 1; i <= 34; i++)
        if (cnt[i] == 2)
            result++;
    return result;
}
string s;
ll dp[200][10];
ll func()
{
    for (int i = 1; i <= 123; i++)
    {
        for (int j = 0; j <= 7; j++)
        {
            if (3 * (13 - 2 * j) <= 34 * 4 - 13 - i + 1 && j != 7)
            {
                ll temp1 = 34 * 4 - 13 - i + 1 - 3 * (13 - 2 * j);
                temp1 *= ExGcdInv(34 * 4 - 13 - i + 1, MOD);
                temp1 = (temp1 % MOD + MOD) % MOD;
                dp[i][j] += dp[i - 1][j] * temp1;
                dp[i][j] = (dp[i][j] % MOD + MOD) % MOD;
            }
            if (3 * (13 - 2 * (j - 1)) <= 34 * 4 - 13 - i + 1 && j != 0)
            {
                ll temp2 = 3 * (13 - 2 * (j - 1));
                temp2 *= ExGcdInv(34 * 4 - 13 - i + 1, MOD);
                temp2 = (temp2 % MOD + MOD) % MOD;
                dp[i][j] += dp[i - 1][j - 1] * temp2;
                dp[i][j] = (dp[i][j] % MOD + MOD) % MOD;
            }
        }
    }
    ll result = 0;
    for (int i = 0; i <= 123; i++)
    {
        result += dp[i][7] * i;
        result = (result % MOD + MOD) % MOD;
    }
    return (result % MOD + MOD) % MOD ;
}
ll result[10];
void solve()
{
    cin >> s;
    cout<<result[cal(s)]<<"\n";
}
int main()
{
    // freopen("Test_File\\Test.in", "r", stdin);
    // freopen("Test_File\\My_code.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    for(int i=0;i<=6;i++)
    {
        memset(dp,0,sizeof(dp));
        dp[0][i]=1;
        result[i]=func();
    }
    int T;
    cin >> T;
    int k = 0;
    while (T--)
    {
        k++;
        cout << "Case #" << k << ": ";
        solve();
    }
    return 0;
}

// Code By Eloi

21.12.14 Tuesday

Codeforces Round #105 (Div. 2)
- D. Bag of mice
  概率dp
  题意：
  两个人轮流从袋子里取老鼠
  现在袋子里有 w 只白的 b 只黑的
  princess先手 dragon 后手（特别的：dragon取了之后会随机吓跑一只老鼠）
  谁先取到白的谁获胜求princess 获胜概率
  
  思路:
  定义dp状态：
  dp [i] [0] princess就在第i轮获胜的概率 dp [i] [1] dragon就在第i轮获胜的概率
  
  状态转移：
  dp[i][0] = (1 - sum) * (w / (w + b - (i - 1)));
  dp[i][1] = (1 - sum) * (w / (w + b - (i - 1)));
  
  sum是指在前 i-1 轮就已经有人获胜的概率
  
  (w / (w + b - (i - 1)))是白老鼠/总共剩下的老鼠
  之前被抓走的一定是黑老鼠
  至于吓跑的老鼠要不要考虑？
  由于吓跑的老鼠白的与黑的概率一致
  等比例减少
  所以白老鼠占所有老鼠的比例不变
  
  代码：

// #pragma GCC optimize(2)
#include <bits/stdc++.h>
#include <iostream>
#include <bitset>
#include <queue>
#include <cstdio>
#include <map>
#include <algorithm>
#include <stack>
// #include <random>
using namespace std;
#define int128 __int128_t
typedef long long ll;
// #define ll int
typedef long double ld;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef pair<P, ll> PP;
struct triplet
{
    ll first, second, third;
};
const ll INF = 1e9;
const ll MAXN = 1e6 + 5;
const ll MOD = 1e9 + 7;
const ll Base = 131;
// mt19937_64 mrand(random_device{}());
ld w, b;
ld dp[MAXN][2];
void solve()
{
    cin >> w >> b;
    int times = floor((w + b) / 3.0) * 2 +(w + b) - floor((w + b) / 3.0) * 3;
    // cout<<times<<endl;



    
    ld sum=0;
    for (int i = 1; i <= times; i++)
    {
        if (i % 2)
        {
            if (b - (i - 1) == 0)
            {
                dp[i][0] = (1-sum);
                break;
            }
            dp[i][0] = (1 - sum) * (w / (w + b - (i - 1)));
            sum+=dp[i][0];
        }
        else
        {
            if (b -  (i - 1) == 0)
            {
                dp[i][1] = (1-sum);
                break;
            }
            dp[i][1] = (1 - sum) * (w / (w + b - (i - 1)));
            sum+=dp[i][1];
        }
    }



    double result = 0;
    for (int i = 1; i <= times; i++)
        result+=dp[i][0];
    printf("%.10lf",result);
}
int main()
{
    // freopen("Test_File\\Test.in", "r", stdin);
    // freopen("Test_File\\My_code.out", "w", stdout);
    // ios::sync_with_stdio(false);
    // cin.tie(0);
    // int T;
    // cin >> T;
    // while (T--)
    solve();
    return 0;
}

// Code By Eloi

21.12.15 Wednesday

poj-3071 Football
概率dp
代码：

// #pragma GCC optimize(2)
// #include <bits/stdc++.h>
#include <math.h>
#include <iostream>
#include <bitset>
#include <queue>
#include <cstdio>
#include <map>
#include <algorithm>
#include <stack>
// #include <random>
using namespace std;
#define int128 __int128_t
typedef long long ll;
// #define ll int
typedef long double ld;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef pair<P, ll> PP;
struct triplet
{
    ll first, second, third;
};
const ll INF = 1e9;
const ll MAXN = 1e6 + 5;
const ll MOD = 1e9 + 7;
const ll Base = 131;
// mt19937_64 mrand(random_device{}());
int n;
int flag[10][200];
double p[200][200];
double dp[10][200];
void solve()
{
    for(int i=1;i<=(1<<n);i++)
        for(int j=1;j<=(1<<n);j++)
            cin>>p[i][j];
    for(int i=1;i<=(1<<n);i++)
        dp[0][i]=1;
    for(int i=1;i<=(1<<n);i++)
        flag[0][i]=i;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=(1<<n);j++)
        {
            flag[i][j]=ceil((double)j/(1<<i));
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=(1<<n);j++)
        {
            double sum=0;
            for(int k=1;k<=(1<<n);k++)
            {
                if(flag[i-1][k]!=flag[i-1][j]&&flag[i][k]==flag[i][j])
                    sum+=dp[i-1][k]*p[j][k];
            }
            dp[i][j]=dp[i-1][j]*sum;
        }
    }
    // for(int i=1;i<=n;i++)
    // {
    //     for(int j=1;j<=(1<<n);j++)
    //         cout<<dp[i][j]<<" ";
    //     cout<<endl;
    // }
    int result;
    double MAX=0;
    for(int i=1;i<=(1<<n);i++)
    {
        if(dp[n][i]>MAX)
        {
            MAX=dp[n][i];
            result=i;
        }
    }
    cout<<result<<"\n";
}
int main()
{
    // freopen("Test_File\\Test.in", "r", stdin);
    // freopen("Test_File\\My_code.out", "w", stdout);
    // ios::sync_with_stdio(false);
    // cin.tie(0);
    // int T;
    // cin >> T;
    while (1)
    {
        cin>>n;
        if(n==-1)
            break;
        solve();
    }
    return 0;
}

// Code By Eloi