• (AtCoder Beginner Contest 280) E - Critical Hit (经典的组合数学问题)


    题意:

    初始n,每次有 p 100 \frac{p}{100} 100p的概率减少2, 1 − p 100 1-\frac{p}{100} 1100p的概率减少1.
    问最后n小于等于0的 期望步数

    思路:

    p 2 = p 100 p2=\frac{p}{100} p2=100p: 减少2的概率
    p 1 = 1 − p 100 p1=1-\frac{p}{100} p1=1100p: 减少1的概率
    c n t 1 cnt1 cnt1: 枚举多少次减少了1
    c n t 2 = ( n − c n t 1 + 1 ) / 2 cnt2 = (n-cnt1 + 1)/2 cnt2=(ncnt1+1)/2 : 使用了多少次减少2

    这里要分类讨论下:!!

    1. n − c n t 1 n-cnt1 ncnt1为奇数,
      那么最后一步要是减少2才行!!!
      答案加上 ( c n t 1 c n t 1 + c n t 2 − 1 ) ∗ p 1 c n t 1 ∗ p 2 c n t 2 ∗ ( c n t 1 + c n t 2 ) (_{cnt1}^{cnt1+cnt2-1})*p_1^{cnt1}*p_2^{cnt2}*(cnt1+cnt2) (cnt1cnt1+cnt21)p1cnt1p2cnt2(cnt1+cnt2)
    2. n − c n t 1 n-cnt1 ncnt1为偶数
      答案加上 ( c n t 1 c n t 1 + c n t 2 ) ∗ p 1 c n t 1 ∗ p 2 c n t 2 ∗ ( c n t 1 + c n t 2 ) (_{cnt1}^{cnt1+cnt2})*p_1^{cnt1}*p_2^{cnt2}*(cnt1+cnt2) (cnt1cnt1+cnt2)p1cnt1p2cnt2(cnt1+cnt2)

    Java

    package com.hgs.atcoder.abc.contest280.e;
    
    /**
     * @author youtsuha
     * @version 1.0
     * Create by 2022/12/3 21:11
     */
    import java.util.*;
    import java.io.*;
    public class Main {
        static FastScanner cin;
        static PrintWriter cout;
        static long mod = 998244353;
        static long frac[];
        static long invf[];
    
    
        static long qpow(long a, long k, long p){
            long res = 1;
            while(k > 0) {
                if(k % 2 == 1){
                    res = res*a%p;
                }
                a = a*a%p;
                k >>= 1;
            }
            return res;
        }
        private static void init()throws IOException {
            cin = new FastScanner(System.in);
            cout = new PrintWriter(System.out);
    
            frac = new long[(int) (4e5+10)];
            invf = new long[(int) (4e5+10)];
            int mxInt = (int) 4e5;
            frac[0] = 1;
            for(int i = 1; i <= mxInt; i ++ ){
                frac[i] = frac[i-1]*i%mod;
            }
    
            invf[mxInt] = qpow(frac[mxInt], mod-2,mod);
            for(int i = mxInt - 1; i >= 0; i -- ) {
                invf[i] = invf[i+1]*(i+1)%mod;
            }
        }
        static long C(int a, int b){
            return frac[b]*invf[b-a]%mod*invf[a]%mod;
        }
        static long A(int a, int b){
            return frac[b]*invf[b-a]%mod;
        }
        private static void close(){
            cout.close();
        }
        private static void sol()throws IOException {
            int n = cin.nextInt(), p = cin.nextInt();
            //p/100 2
            // (1-p/100) 1
    
            long p2 = p*qpow(100,mod-2,mod)%mod, p1 = (1 - p2 + mod) % mod;
            long ans = 0;
            if(p1 == 0){
    //            ans = qpow(p2,(n+1)/2,mod);
                cout.println((n+1)/2);
                return ;
            }
            if(p2 == 0){
    //            ans = ;
                cout.println(n);
                return;
            }
            for(int c1 = 0; c1 <= n; c1 ++ ) {
                int rem = n - c1;
                int c2 = (n - c1 + 1)/2;
    
                int len = c1+c2;
    
                long pp1 = qpow(p1,c1,mod), pp2 = qpow(p2,c2,mod);
                if(rem % 2 == 0){
                    //最后一步都可以
                    long res = len*pp1%mod*pp2%mod*C(c1,len)%mod;
                    ans = (ans + res) % mod;
                }else {
                    //最后一步为2,变为-1
                    long res = len*pp1%mod*pp2%mod*C(c1,len-1);
                    ans = (ans + res)%mod;
                }
    
    
            }
            cout.println(ans);
        }
        public static void main(String[] args) throws IOException {
            init();
            sol();
            close();
        }
    }
    class FastScanner {
        BufferedReader br;
        StringTokenizer st = new StringTokenizer("");
    
        public FastScanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s));
        }
    
        public FastScanner(String s) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(new File(s)));
        }
    
        public String next() throws IOException {
            while (!st.hasMoreTokens()){
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) { e.printStackTrace(); }
            }
            return st.nextToken();
        }
    
        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }
    
        public long nextLong() throws IOException {
            return Long.parseLong(next());
        }
    
        public double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }
    }
    
    
    • 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
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
  • 相关阅读:
    用 Lunchbox 在 vue3 中创建一个旋转的 3D 地球竟是如此简单
    【Java基础】方法
    IPFS系列 - 答疑
    cv::Mat类的矩阵内容输出的各种格式的例子
    数仓实践:数据仓库建设公共规范指南
    Linux怎么设置中文语言? centos中文乱码的解决办法
    saas化调研
    《Go Web 编程》之第6章 存储数据
    FPGA:基础入门按键控制蜂鸣器
    Go语言进化之路:泛型的崛起与复用的新篇章
  • 原文地址:https://blog.csdn.net/qq_45377553/article/details/128167470