求用n個(gè)3的倍數(shù)的數(shù)按位或出數(shù)字a的方案數(shù)有多少種（0也算3的倍數(shù)）

題解

• 若數(shù)b的每個(gè)二進(jìn)制位上的1，在a中也為1，則稱b為a的子集
• 容易知道任意個(gè)a的子集按位或出來(lái)的結(jié)果還是a的子集
• 若問(wèn)題改為按位或出來(lái)的結(jié)果是a的子集的方案數(shù)，那么答案就是a的子集中是3的倍數(shù)的子集個(gè)數(shù)的n次方
  接著我們對(duì)子集按二進(jìn)制上的1 mod 3的個(gè)數(shù)劃分，例如1101有兩個(gè)1mod3=1, 一個(gè)1mod3 = 2，設(shè)\(S[i][j]\)表示a的子集中有i個(gè)mod3=1，j個(gè)mod3=2的子集的子集 中是3的倍數(shù)的個(gè)數(shù)，例如a = 1101的一個(gè)子集1001表示的狀態(tài)為\(S[1][1]\), 1001的子集中是3的倍數(shù)的有1001和0000所以\(S[1][1] = 2\)，那么\(S[i][j]\)的n次方就可以表示為用n個(gè)3的倍數(shù)的數(shù)按位或出來(lái)的結(jié)果的狀態(tài)是S[i][j]的子集方案數(shù)
  那么\(\sum_{i=1}^kS[i][k-i]\)就表示或出來(lái)的結(jié)果最多匹配上a中K個(gè)1的方案數(shù)，那么我們就可以用最多匹配上a中K個(gè)1的方案數(shù)，減去匹配上a中K-1個(gè)1的方案數(shù)得出答案，但是這樣簡(jiǎn)單的相減是不行的因?yàn)?span id="ze8trgl8bvbq" class="math inline">\(S[i][k-i]\)的子集是會(huì)有重疊的，會(huì)多扣掉最多匹配k-2個(gè)1的方案數(shù)，根據(jù)容斥原理應(yīng)當(dāng)減去最多匹配K-1的方案數(shù)，加上最多匹配K-2的方案數(shù)，扣掉K-3加上K-4...

代碼

#include <bits/stdc++.h> typedef long long ll; using namespace std; const int mx = 65; const ll mod = 998244353; int C[mx][mx], S[mx][mx];ll pow_mod(ll a, ll b) {ll ans = 1;while (b > 0) {if (b & 1) ans = ans * a % mod;a = a * a % mod;b /= 2;}return ans; }int main() {C[0][0] = 1;for (int i = 1; i < mx; i++) {C[i][0] = 1;for (int j = 1; j <= i; j++) {C[i][j] = (C[i-1][j-1] + C[i-1][j]) % mod;}}for (int i = 0; i < mx; i++) {for (int j = 0; j < mx; j++) {for (int p = 0; p <= i; p++) {for (int q = 0; q <= j; q++) {if ((p + 2*q) % 3 != 0) continue;S[i][j] += C[i][p] * C[j][q] % mod;S[i][j] %= mod;}}}}S[0][0] = 1;int T;scanf("%d", &T);while (T--) {ll n, a, x = 0, y = 0;scanf("%lld%lld", &n, &a);for (int i = 0; i < 64; i++) {if (a & (1LL<<i)) {if (i % 2 == 0) x++;else y++;}}ll ans = 0;for (int i = 0; i <= x; i++) {for (int j = 0; j <= y; j++) {ll tmp = C[x][i] * C[y][j] % mod * pow_mod(S[i][j], n) % mod;if ((x+y-i-j) % 2) tmp *= -1;ans = (ans + tmp) % mod;}}ans = (ans + mod) % mod;printf("%lld\n", ans);}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/bpdwn-cnblogs/p/11289740.html

總結(jié)

以上是生活随笔為你收集整理的E-triples II_2019牛客暑期多校训练营（第四场）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。