牛客多校第四场

发表于 | 更新于: | 分类于 ， ， | 阅读数 次

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---------