牛客多校第四场

E.triples ll

题意

让你用$n$个3的倍数,把$a$或出来,问你有几种方案,对998244353取模

思路

在二进制中$1,4,16,\mod 3余1$, 而 $2,8,32 \mod 3余2$

首先如果$a$中为$1$的二进制位在$b$中也都为$1$,那么就称$a$是$b$的子集

我们用$dp[i][j]$来表示二进制位$mod$ $3$ 余$1$的个数为$i$,$mod$ $3$ 余$2$的个数为$j$并且所有是3的倍数的子集个数

我们可以先一个$(logn)^4$求出所有的$dp$值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void Fac() {
for (int i = 0; i < maxn; i ++) C[i][0] = 1;
for (int i = 1; i < maxn; i ++)
for (int j = 1; j <= i; j ++)
C[i][j] = (C[i-1][j] + C[i-1][j-1]) % mod;
}

void init() {
Fac();
for (int x = 0; x < maxn; x ++)
for (int y = 0; y < maxn; y ++)
for (int i = 0; i <= x; i ++)
for (int j = 0; j <= y; j ++)
if((i+2*j)%3==0) dp[x][y] = (dp[x][y] + C[x][i] * C[y][j] % mod) % mod;
dp[0][0] = 1;
}

如果要求或出来的结果是$a$的子集,那么方案数就是$(a的子集的个数)^n$

但是题目要求或出来的结果是$a$,那我们就要容斥一下了

打个比方,现在$a$的$\mod2$的个数为$1$,$\mod1$的个数为$2$

那么$dp[2][1]$所代表的是$<2,1>$的子集的个数,但有些子集在相或$n$次以后得不到a,这时候就要减掉那些不能或到$a$的子集

img1

$dp[2][1]$就像上图中由 A-E,​A-D,A-C,B-E,B-D,B-C 组成,而能或出来$a$的只有A-E,那么我们就要把其余不满足的减掉,也就是减掉$dp[1][1]+dp[2][0]$,发现减多了,我们要加上$dp[1][0]+dp[0][1]$,后面就跟容斥一样,多写几个样例就会发现当$(num1+num2-i-j)\mod2$时是减,其他是加。

注意:减的时候减掉的是不符合个数的$n$次幂

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 70;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;

ll C[maxn][maxn], dp[maxn][maxn];
int cnt[2], o;

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

void Fac() {
for (int i = 0; i < maxn; i ++) C[i][0] = 1;
for (int i = 1; i < maxn; i ++)
for (int j = 1; j <= i; j ++)
C[i][j] = (C[i-1][j] + C[i-1][j-1]) % mod;
}

void init() {
Fac();
for (int x = 0; x < maxn; x ++)
for (int y = 0; y < maxn; y ++)
for (int i = 0; i <= x; i ++)
for (int j = 0; j <= y; j ++)
if((i+2*j)%3==0) dp[x][y] = (dp[x][y] + C[x][i] * C[y][j] % mod) % mod;
dp[0][0] = 1;
}

int main() {
init();
int t;
scanf("%d", &t);
while(t --) {
ll n, a;
scanf("%lld %lld", &n, &a);
cnt[0] = cnt[1] = o = 0;
while(a) {
if(a & 1) cnt[o] ++;
o ^= 1; a /= 2;
}
ll ans = 0;
for (int i = 0; i <= cnt[0]; i ++)
for (int j = 0; j <= cnt[1]; j ++) {
ll f = C[cnt[0]][i] * C[cnt[1]][j] % mod * Ksm(dp[i][j], n) % mod;
if((cnt[0] + cnt[1] - i - j) & 1) f *= -1;
ans = (ans + f + mod) % mod;
}
printf("%lld\n", ans);
}
return 0;
}
---------Thanks for your attention---------