首页 > 其他分享 >「解题报告」ARC133E Cyclic Medians

「解题报告」ARC133E Cyclic Medians

时间:2023-02-26 14:11:30浏览次数:41  
标签:方案 那么 Cyclic int Medians ARC133E 中位数 套路 ans

套路题不会做!套路题不会做!套路题不会做!套路题不会做!套路题不会做!

处理中位数的套路就将大于等于 \(k\) 的设置为 \(1\),小于 \(k\) 的设置为 \(0\)。我们要求中位数的和,其实就是对于每一个 \(k\),求中位数 \(\ge k\) 的方案数的和。

没人喜欢 \([1, V]\),我们先改成 \([0, V - 1]\)。考虑三个数的 \(0, 1\) 中位数有什么情况:

  1. \((a, 0, 0) \to 0\);
  2. \((a, 1, 1) \to 1\);
  3. \((a, 0, 1) \to a\)。

发现如果中途出现了前两种情况,那么最后的中位数就与 \(a\) 没有关系了。我们将出现前两种情况的方案和不出现的方案分别计算。

如果出现了,我们发现,根据对称性,如果对于某个 \(k\) 答案为 \(0\),那么对于 \(v - k\) 答案为 \(1\)。那么显然,最后答案等于 \(1\) 的方案数就是总方案数的一半。

考虑没出现的情况,那么我们实际上就是要满足 \(a_{i \bmod n} \ne b_{i \bmod m}\)。设 \(g = \gcd(n, m)\),那么其实就是 \(a_{i} = a_{i + g} = a_{i + 2g} = \cdots, b_{i} = b_{i + g} = b_{i + 2g} = \cdots, a_{i} \ne b_{i}\)。

那么要不然 \(a\) 全选 \(0\)、\(b\) 全选 \(1\),要不然反过来。选 \(0\) 的方案数为 \(k\),选 \(1\) 的方案数为 \(v - k\),那么方案数就是:

\[\left(k^{n/g} (v-k)^{m/g} + k^{m/g} (v-k)^{n/g}\right)^g \]

对于这种情况,最后中位数就是 \(a\),那么统计 \(a \ge k\) 的方案即可。

除掉这个就是前一种情况,拿 \(v^{n+m}\) 减去上式然后除以 \(2\) 就是前一种情况的方案数。

然后计算即可。

#include <bits/stdc++.h>
using namespace std;
const int P = 998244353;
int qpow(int a, int b) {
    int ans = 1;
    while (b) {
        if (b & 1) ans = 1ll * ans * a % P;
        a = 1ll * a * a % P;
        b >>= 1;
    }
    return ans;
}
int n, m, v, a;
int main() {
    scanf("%d%d%d%d", &n, &m, &v, &a);
    a--;
    int g = __gcd(n, m);
    int ans = 0;
    for (int k = 0; k <= v; k++) {
        int w = qpow((1ll * qpow(k, n / g) * qpow(v - k, m / g)
             + 1ll * qpow(k, m / g) * qpow(v - k, n / g)) % P, g);
        ans = (ans + 1ll * (qpow(v, n + m) - w + P) * ((P + 1) / 2)) % P;
        if (a >= k) ans = (ans + w) % P;
    }
    printf("%d\n", ans);
    return 0;
}

标签:方案,那么,Cyclic,int,Medians,ARC133E,中位数,套路,ans
From: https://www.cnblogs.com/apjifengc/p/17156462.html

相关文章

  • CyclicBarrier 的使用
    CyclicBarrier使用场景用于协调多个线程同步执行操作的场合,所有线程等待完成,然后一起做事情(相互之间都准备好,然后一起做事情)例如百米赛跑,必须等待所有运动员都准备......
  • 多线程等待所有子线程执行完使用总结(3)——CyclicBarrier使用和源码初步分析
    问题背景我们在日常开发和学习过程中,经常会使用到多线程的场景,其中我们经常会碰到,我们代码需要等待某个或者多个线程执行完再开始执行,上一篇文章中(参考https://blog.51cto......
  • CyclicBarrier源码解析
    CyclicBarrier源码解析描述:一个同步帮助,允许一组线程互相等待到达一个共同的屏障点。Cyclicbarrier在涉及固定大小的线程组的程序中非常有用,这些线程必须偶尔相互等待。......
  • Cyclic Nacklace HDU - 3746 (kmp最小循环节)
    题意:现在给你一个字符串,请问在该字符串末尾最少添加多少个字符,可以让这个字符串获得重复循环序列。AC代码:#include<iostream>#include<cstring>usingnamespacestd;const......
  • Java并发编程——CyclicBarrier
    一、CyclicBarrier循环栅栏CyclicBarrier是java.util.concurrent包下面的一个工具类,字面意思是可循环使用(Cyclic)的屏障(Barrier),通过它可以实现让一组线程到达一个屏障(也可......
  • 【高并发】AQS中的CountDownLatch、Semaphore与CyclicBarrier用法总结
    CountDownLatch概述同步辅助类,通过它可以阻塞当前线程。也就是说,能够实现一个线程或者多个线程一直等待,直到其他线程执行的操作完成。使用一个给定的计数器进行初始化,该......
  • Cyclical Learning Rates
    学习率的设置是深度学习中一个比较重要的问题,CyclicalLearningRates(CLR)提出了一种新的方法,即让学习率周期性的变化,而不是像之前的方法那样让学习率单调递减变化.Cy......
  • CyclicBarrier(循环屏障)的使用
    一、介绍CyclicBarrier也叫同步屏障,在JDK1.5被引入的一个同步辅助类,在API中是这么介绍的:允许一组线程全部等待彼此达到共同屏障点的同步辅助。循环阻塞在涉及固定大小......
  • 同步屏障CyclicBarrier
    CyclicBarrier,根据字面意思理解:循环屏障。屏障的意思:CyclicBarrier可以让一组线程到达某个屏障点时被阻塞,直到最后一个线程到达屏障点时,屏障才会放开,所有被屏障阻塞的线程才......
  • CyclicBarrier简单使用
    CyclicBarrier就是要实现有福同享有难同当的原理,吃饭的时候,要等室友都到了才会一起去吃食堂,吃饭食堂一起去教室     每一阶段完成后,才会开始下一阶段代码部分......