需要统计 1≤a,b≤n 且 (a∣b)≤K 的有序对个数。这里的 ≤ 是数值比较,不能只统计“只用到 K 中为 1 的那些二进制位”的数。
用数位 DP:从最高位到最低位决定 (ai,bi),并维护三个紧致标记:
通信系统中有两个通道编号 a、b,均需满足 1≤a,b≤n。只有当它们的按位或不超过限额 K 时,这对编号才被接受。
请统计满足条件的有序对 (a,b) 的个数。答案可能很大,请对 109+7 取模后输出。
按位或:两个整数对应二进制位做逻辑或,例如 5∣3=7。
约束:测试组数不超过 10^4,n 与 K 均不超过 10^18,且 n 至少为 1,K 可以为 0。
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.