zkx06111's Blog

SRM 695-1 800pts BearEmptyCoin

| Comments

题意

有一个均匀硬币,两面都是空的,你需要抛次。如果向上的那面没有数字,你可以写上一个数字。给分数加上向上的那面写的数字。求使用最优策略的前提下,分数等于的概率,请给这个概率乘以

题解

如果,那么只要写即可,答案是

对于两种数字分别出现了次的情况,只要满足,就存在一种写数字的方案了。

对于种合法的情况,可以证明一定存在一个填在硬币上的数字,使得对于每种情况存在一个满足

证明如下:

,令,那么

,有。因为,令,代入上面的式子得到

化简一下就是,其中任取,那么就是,这个东西是中国剩余定理的形式,所以有解。

由此,可以得到一种最优策略,首先求出所有合法的,然后求出一个作为第一次写在硬币上的数字,(这个求的过程并不需要实现,因为题目不要求给出方案)。

于是,枚举第一次写的数字连续出现的次数,剩下的次里面两种数字是均匀分布的,最优的方案是找到一个合法的第二种数字出现次数(即满足),使得最大。把这个最大的组合数加给答案。

最后答案要乘以2,因为写的数字可以先后交换顺序。

代码

long long comb[70][70];
int ok[70];
int gcd(int a, int b){
    return b == 0 ? a : gcd(b, a % b);
}
class BearEmptyCoin {
public:
    long long winProbability(int K, int S) {
        if (S % K == 0) return 1ll << K;
        comb[0][0] = 1;
        REP(i, 1, K) REP(j, 1, i){
            comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j];
        }
        memset(ok, 0, sizeof ok);
        REP(i, 1, K) ok[i] = (S % gcd(i, K - i) == 0);
        LL ans = 0;
        REP(i, 1, K - 1){
            LL mx = 0;
            REP(j, 1, i) if (ok[j]) mx = max(mx, comb[i][j]);
            ans += mx;
        }
        return ans * 2;
    }

Comments

comments powered by Disqus