牛客多校第七场

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll dp[35][2][2][2][2];
int num_a[35], num_b[35], num_c[35];

void GetNum(ll a, ll b, ll c) {
memset(num_a, 0, sizeof(num_a));
memset(num_b, 0, sizeof(num_b));
memset(num_c, 0, sizeof(num_c));
num_a[0] = 0;
while(a) {
num_a[++num_a[0]] = a % 2;
a /= 2;
}
num_b[0] = 0;
while(b) {
num_b[++num_b[0]] = b % 2;
b /= 2;
}
num_c[0] = 0;
while(c) {
num_c[++num_c[0]] = c % 2;
c /= 2;
}
}

ll dfs(int pos, int a, int b, int an, int xo) {
if(!pos) return 1;
if(dp[pos][a][b][an][xo] != -1) return dp[pos][a][b][an][xo];
int ua = a ? num_a[pos] : 1;
int ub = b ? num_b[pos] : 1;
int uan = an ? num_c[pos] : 1;
int uxo = xo ? num_c[pos] : 0;
ll ret = 0;
for (int i = 0; i <= ua; i ++)
for (int j = 0; j <= ub; j ++)
if((i&j) <= uan && (i^j) >= uxo)
ret += dfs(pos-1, a&&(i==ua), b&&(j==ub), an&&((i&j)==uan), xo&&((i^j)==uxo));
return dp[pos][a][b][an][xo] = ret;
}

int main() {
int t;
scanf("%d", &t);
while(t --) {
ll a, b, c;
scanf("%lld %lld %lld", &a, &b, &c);
GetNum(a, b, c);
memset(dp, -1, sizeof(dp));
ll ans = dfs(32, 1, 1, 1, 1) - max(0ll, a-c+1) - max(0ll, b-c+1);
cout << a*b-ans << endl;
}
return 0;
}

I:Chessboard

题意

给你一个N,M,然后你可以任意构造一个 k * k的矩阵,使得矩阵内每个元素最少是M,且任意不同行不同列的 k 个元素总和不超过N且都相同,问有多少种构造方法。

思路

img1

我们枚举$k$,我们可以把每个元素减去$M$,那么就相当于$N$减去$ k \times M$,简化问题并且不影响答案

img2

构造两个矩阵$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$份

img3

为什么会算重,我们拿$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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e5 + 5;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;

ll fac[maxn], inv[maxn];

ll Ksm(ll a, ll b, ll p) {
ll res = 1;
while(b) {
if(b & 1) res = res * a % p;
a = a * a % p;
b >>= 1;
}
return res;
}

void Fac() {
fac[0] = 1;
for (int i = 1; i < maxn; i ++)
fac[i] = (fac[i-1] * i) % mod;
inv[maxn-1] = Ksm(fac[maxn-1], mod-2, mod);
for (int i = maxn-2; i >= 0; i --)
inv[i] = inv[i+1] * (i+1) % mod;
}

ll C(int n, int m) {
if(n < 0 || m < 0 || n < m) return 0;
return fac[n] * inv[m] % mod * inv[n-m] % mod;
}

int main() {
Fac();
int T;
scanf("%d", &T);
while(T --) {
int n, m;
scanf("%d %d", &n, &m);
ll ans = 0;
for (int k = 1; k * m <= n; k ++) {
int tt = n - k*m;
for (int t = 0; t <= tt; t ++) {
ans += C(t+k+k-1, k+k-1);
if(t >= k) ans -= C(t+k-1, k+k-1);
ans = (ans % mod + mod) % mod;
}
}
printf("%lld\n", ans);
}
return 0;
}

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<bits/stdc++.h>
using namespace std;

#define ll long long
const int maxn = 1e5 + 7;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
typedef pair<int, int> pis;

ll sum[maxn][4], prime[maxn], tot, h[maxn][4];
ll w[maxn], m, id1[maxn], id2[maxn];
ll sqr;
bool vis[maxn];

ll f(ll p, ll e) {
if(p % 4 == 1) return 3 * e + 1;
return 1;
}

ll init(ll n) {
for (int i = 0; i < 4; i ++) sum[0][i] = 0;
for (int i = 1; i <= n; i ++) vis[i] = 0;
vis[1] = 1; tot = 0;
for (int i = 2; i <= n; i ++) {
if(!vis[i]) {
prime[++tot] = i;
for (int j = 0; j < 4; j ++)
sum[tot][j] = sum[tot-1][j] + (i % 4 == j);
}
for (int j = 1; j <= tot; j ++) {
if(i * prime[j] > n) break;
vis[i*prime[j]] = 1;
if(i % prime[j] == 0) break;
}
}
}

void getW(ll n) {
m = 0;//离散下标
for (ll l = 1, r; l <= n; l = r + 1) {
r = n/(n/l);
w[++m] = n/l;//把所有数字当成质数
h[m][1] = w[m] / 4 + (w[m] % 4 >= 1) - 1;
h[m][2] = w[m] / 4 + (w[m] % 4 >= 2);
h[m][3] = w[m] / 4 + (w[m] % 4 >= 3);
h[m][4] = w[m] / 4;
if(w[m] <= sqr) id1[w[m]] = m;
else id2[n/w[m]] = m;
}
}

void getG(ll n) {//dp都质数模4的个数
for (ll i = 1; i <= tot; i ++) {
for (ll j = 1; j <= m && prime[i] * prime[i] <= w[j]; j ++) {
ll d = w[j] / prime[i];
ll id = d <= sqr ? id1[d] : id2[n/d];
for (int r = 0; r < 4; r ++)
h[j][r*prime[i]%4] = h[j][r*prime[i]%4] - h[id][r] + sum[i-1][r];
}
}
}

ll S(ll x, ll y, ll n) {
if(x <= prime[y-1] || x <= 1) return 0;
ll id = x <= sqr ? id1[x] : id2[n/x];
ll ans = h[id][3] - sum[y-1][3] + 4 * (h[id][1] - sum[y-1][1]);//模4余1的值为4,余3的值为1
if(y == 1) ans ++;
for (ll i = y; i <= tot && prime[i] * prime[i] <= x; i ++) {
ll t = prime[i];
for (int j = 1; t <= x; j ++, t = t * prime[i])
ans = ans + f(prime[i], j) * (S(x/t, i+1, n) + (j != 1));
}
return ans;
}

int main() {
int t;
scanf("%d", &t);
while(t --) {
ll n;
scanf("%lld", &n);
sqr = sqrt(n);
init(sqr);
getW(n);
getG(n);
printf("%lld\n", S(n, 1, n) + 1);//S(n,1,n)+f(1)
}
return 0;
}
---------Thanks for your attention---------