題意

題目鏈接

Sol

神仙題Orzzzz

題目可以轉化為從\(\leqslant M\)的質數中選出\(N\)個\(xor\)和為\(0\)的方案數

這樣就好做多了

設\(f(x) = [x \text{是質數}]\)

\(n\)次異或FWT即可

快速冪優化一下，中間不用IFWT，最后轉一次就行(然而并不知道為什么)

哪位大佬教教我這題的DP怎么寫呀qwqqqq

死過不過去樣例。。

#include<bits/stdc++.h> using namespace std; const int MAXN = (1 << 17) + 10, mod = 998244353, inv2 = 499122177; inline int read() {char c = getchar(); int x = 0, f = 1;while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();return x * f; } int N, A[MAXN], B[MAXN], C[MAXN]; int add(int x, int y) {if(x + y < 0) return x + y + mod;return x + y >= mod ? x + y - mod : x + y; } int mul(int x, int y) {return 1ll * x * y % mod; } void FWTor(int *a, int opt) {for(int mid = 1; mid < N; mid <<= 1) for(int R = mid << 1, j = 0; j < N; j += R)for(int k = 0; k < mid; k++) if(opt == 1) a[j + k + mid] = add(a[j + k], a[j + k + mid]);else a[j + k + mid] = add(a[j + k + mid], -a[j + k]); } void FWTand(int *a, int opt) {for(int mid = 1; mid < N; mid <<= 1) for(int R = mid << 1, j = 0; j < N; j += R)for(int k = 0; k < mid; k++) if(opt == 1) a[j + k] = add(a[j + k], a[j + k + mid]);else a[j + k] = add(a[j + k], -a[j + k + mid]); } void FWTxor(int *a, int opt) {for(int mid = 1; mid < N; mid <<= 1) for(int R = mid << 1, j = 0; j < N; j += R)for(int k = 0; k < mid; k++) {int x = a[j + k], y = a[j + k + mid];if(opt == 1) a[j + k] = add(x, y), a[j + k + mid] = add(x, -y);else a[j + k] = mul(add(x, y), inv2), a[j + k + mid] = mul(add(x, -y), inv2); }} int main() {N = 1 << (read());for(int i = 0; i < N; i++) A[i] = read();for(int i = 0; i < N; i++) B[i] = read();FWTor(A, 1); FWTor(B, 1);for(int i = 0; i < N; i++) C[i] = mul(A[i], B[i]);FWTor(C, -1); FWTor(A, -1); FWTor(B, -1);for(int i = 0; i < N; i++) printf("%d ", C[i]); puts("");FWTand(A, 1); FWTand(B, 1);for(int i = 0; i < N; i++) C[i] = mul(A[i], B[i]);FWTand(C, -1); FWTand(A, -1); FWTand(B, -1); for(int i = 0; i < N; i++) printf("%d ", C[i]); puts("");FWTxor(A, 1); FWTxor(B, 1);for(int i = 0; i < N; i++) C[i] = mul(A[i], B[i]);FWTxor(C, -1); FWTxor(A, -1); FWTxor(B, -1); for(int i = 0; i < N; i++) printf("%d ", C[i]);return 0; }

轉載于:https://www.cnblogs.com/zwfymqz/p/10040817.html

總結

以上是生活随笔為你收集整理的BZOJ4589: Hard Nim(FWT 快速幂)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。