H:Pair
题意
给你3个数字$A,B,C$,让你计算$1\leq x\leq A,1\leq y\leq B$,并且$(x$ $and$ $y)>C$或者$(x$ $xor$ $y)<C$ 这样的
$
思路
很像数位dp,枚举二进制的每一位,4种状态分别是(A临界,B临界,A$and$B临界,A$xor$B临界)
这样直接数位dp可以算出有多少对不满足条件,然后用总数减去
因为$x,y>1$,所有要在数位dp算出的结果中减去x为0时和y为0时的数量
AC代码
1 |
|
I:Chessboard
题意
给你一个N,M,然后你可以任意构造一个 k * k的矩阵,使得矩阵内每个元素最少是M,且任意不同行不同列的 k 个元素总和不超过N且都相同,问有多少种构造方法。
思路
我们枚举$k$,我们可以把每个元素减去$M$,那么就相当于$N$减去$ k \times M$,简化问题并且不影响答案
构造两个矩阵$Ai,Bi $对于这两个矩阵,我们可知他们前面的系数和为$T$则满足结果 等价于将$T$ 分成$2\times k$份($a$,$b$各有$k$个)采用隔板法 (将$T$ 转换成$1$排,每两个$1$之间有一个隔间,那么$k \times 2 + T$有$k \times 2 - 1 +T$个隔间,我们选择$k \times 2 - 1$个隔间就可以把这些$1$分成$k \times 2$份
为什么会算重,我们拿$T=3,k=2$来举个例子,比如$a_1=1,a_2=2,b_1=0,b_2=0$
那这个矩阵就是长这个样子
$\begin{bmatrix} a_1+b_1 &a_1+b_2 \\ a_2+b_1 &a_2+b_2 \end{bmatrix}$ $==>$ $\begin{bmatrix} 1 & 1\ 2 &2 \end{bmatrix}$
跟$\begin{bmatrix} a_1-1+b_1+1 &a_1-1+b_2+1\ a_2-1+b_1+1 &a_2-1+b_2+1 \end{bmatrix}$ $==>$ $\begin{bmatrix} 1 & 1\ 2 &2 \end{bmatrix}$
是相同的,也就是当$a_i$全部减1,而$b_i$全部加1时,跟原来的矩阵相同,所以这就重复了,那去重也就是这样去
PS:这篇博客其实是我扒CM大佬的=^=
AC代码
1 |
|
K:Function
题意
$csl(p,x)= \begin{cases} 3e+1 & x=p^e\& p\in prime \& p = a^2+b^2\1 & x=p^e \& p!= a^2+b^2\0 & others\end{cases}$
$tl(p,x)=\max\limits_{d|x}csl(p,d)$
求$S=\sum\limits{i=1}^{n}\prod\limits{p} tl(p,i)$
思路
可得知
$tl(p,x)=\begin{cases}3e+1& x=p^e\& p\in prime \&p=a^2+b^2 \1 & others\end{cases}$
$f(x)=\prod\limits_{d|n}\begin{cases}3e+1& x=p^e\& p\in prime \&p=a^2+b^2 \1 & others\end{cases}$
答案就是$f(i)$的前缀和,即$S=\sum\limits_{i=1}^{n}f(i)$
我们先不考虑$p=a^2+b^2$,考虑$i$为质数时的情况$f(i)=3+1$
$i$为质数次幂的情况$f(p^e)=3e+1$
这样可以快速算出i为质数和i的质数次幂的情况
可以用$min_25$筛来求这个前缀和
那么现在我们来考虑$p=a^2+b^2$这个限制,因为$min_25$筛由构造一个函数,把所有数字看成质数,
我们可以设$h[i][4]$,来代表i以前由多少数字余数为$0,1,2,3$,通过dp可以得到有多少质数余数为$0,1,2,3$
因为费马二次定理,我们知道模$4$与$1$的可以分解成$a^2+b^2$,而模$4$余$3$的一定不行,那么质数部分我们就都算出来了,下面的合数部分就用$min_25$筛就好了
AC代码
1 |
|