Counting Rhyme

时间：2024-03-21 19:12:21浏览次数：19

这道题目就是因为对数论容斥不熟悉导致的。。。之前也做到过

看这篇题解

首先这篇题解用到了一个很大的纲领：公约数是最大公约数的约数

然后看下\(g_k\)怎么求：由于\(g_k\)表示的是\(k|gcd(a_i,a_j)\)的对数，相当于\(k\)是\(a_i,a_j\)的公约数，所以我们把数组中\(k\)的倍数全部标出来，统计总共的个数，然后从这些里面随便选两个（组合数）就好了

像“Small GCD”这道题目一样，离散的结构可以考虑数论容斥呀

标签：数论,题解,容斥,Rhyme,公约数,Counting
From： https://www.cnblogs.com/dingxingdi/p/18088074

CodeForces 1943D2 Counting Is Fun (Hard Version)
洛谷传送门CF传送门被自己的赛时智障操作气笑了。谁告诉你容斥钦定了几个要记到状态里面的。。。/tuu显然先找“好数组”的充要条件。对原数组\(a\)差分，设\(b_i=a_i-a_{i-1}\)。那么一次可以选择一对\((i,j)\)满足\(i\lej-2\)，然后给\(b_i\)减\(1\)，给\(b_......
CF1857G Counting Graphs 题解
题目描述给定一棵最小生成树，求有多少张图的最小生成树是给定的树，并且这张图的所有边边权不超过\(S\)。思路考虑在最小生成树中加边。我们回顾一下Kruskal的过程：找到没被用过的，最小的边判断这条边的两端是否在一个联通块中加入这条边，将两端的联通块连在一起根据第三条......
[ABC259Ex] Yet Another Path Counting 题解
Description有\(N\)行\(N\)列的网格图，只能向下或向右走，合法路径的开端和结尾的格子上数字一样找到合法路径条数，对\(998244353\)取模\(1\leqN\leq400,1\leqa_{i,j}\leqN^2\)。Solution有一个\(O(n^4)\)的做法是每次枚举起点和终点然后用组合数计算答案，但是由于同......
P10013 Tree Topological Order Counting 题解
首先题目里面写了每一个数都有权值，一般这种题只能去想求出每一个的具体方案数，那么也就是我们得求出\(h_{i,j}\)表示在所有合法拓扑序中\(a_i=j\)的方案数。一颗树的拓扑序数量是\(\dfrac{n!}{\prodsiz_i}\)，相信大家都知道。因为我们需要保证这一棵树满足拓扑排序的条件，不......
double counting 小记
前言：doublecounting即算两次，可以对比两次结果得出一些有用的结论。例1：求证：\[\sum_{i=0}^ni\binom{n}{i}=n\times2^{n-1}\]证明：考虑计数问题：从\(\{1,2,3,\dotsn\}\)中选取一个元素\(a\)和一个子集\(A\)，要求\(a\inA\)，求方案数。先取\(A\)再取\(a\)，我们根据......
[ABC212H] Nim Counting
题目链接题目本质就是对一个多项式\(F\)进行等比数列求和得到\(G\)（\(F_i\)表示\(i\)在序列\(A\)中的出现次数），求\(G\)所有下标\(>0\)的位置的权值和。显然，\(M\)固定就可以直接做了。但\(M\)不固定，所以我们只能暴力枚举\(M\)并进行\(N\)次FWT卷积。复杂度显......
CF1884D Counting Rhyme 题解
Problem-D-CodeforcesCountingRhyme-洛谷法1：我们之前肯定看过这样一道非常经典的题：求\(a_i\)中有多少对\((i,j)\)，满足\(\gcd(a_i,a_j)=1\)\(n\leq10^6\)这题是莫反板子题，但显然可以不用莫反做。先不说这题怎么做，我们发现这道题和CF1884D的不同之处在......
Scale-Prior Deformable Convolution for Exemplar-Guided Class-Agnostic Counting
Scale-PriorDeformableConvolutionforExemplar-GuidedClass-AgnosticCounting初读印象comment::（计数用的一个网络）提出了一个标度优先的可变形卷积，将典范的信息，例如标度，整合到计数网络主干中。动机本文考虑的是类别无关的计数，其中计数模型预测由一组查询图像中的少数......
Atcoder-Countings4
Atcoder-Countings4[ABC231G]BallsinBoxesProblem有\(n\)个盒子，初始时第\(i\)个盒子内有\(a_i\)个小球，进行\(k\)次操作后，每次操作等概率随机选择一个盒子放入一个小球，设\(k\)次操作后每个盒子的小球个数为\(b_i\)，那么得分为\(\prod_{i=1}^nb_i\)。求出期望得分......
T399753 counting problem（计数问题）题解
LinkT399753countingproblem（计数问题）Question给出一个正整数\(n\)，求\(AB+CD=n\)的方案数，\(A,B,C,D\)都是要求是正整数Solution考虑直接枚举\(ABCD\)显然是不切实际的那么就折半枚举设\(F_i\)表示两个数的乘积为\(i\)的方案数答案就是\(\sum\limits_{i=1......

Counting Rhyme

相关文章

赞助商

阅读排行