old_Math/Bitwise_And_Convolution.cpp

• View this file on GitHub
• Last update: 2022-07-19 22:14:43+09:00

Code

vector<long long> and_fwt(vector<long long> A, bool inv){
	int N = A.size();
	for (int i = 1; i < N; i <<= 1){
		for (int j = 0; j < N; j++){
			if ((j & i) == 0){
				if (!inv){
					A[j] += A[j | i];
					A[j] %= MOD;
				} else {
					A[j] -= A[j | i];
					A[j] += MOD;
					A[j] %= MOD;
				}
			}
		}
	}
	return A;
}
vector<long long> and_convolution(vector<long long> A, vector<long long> B){
	int N = A.size();
	A = and_fwt(A, false);
	B = and_fwt(B, false);
	vector<long long> C(N);
	for (int i = 0; i < N; i++){
		C[i] = A[i] * B[i] % MOD;
	}
	C = and_fwt(C, true);
	return C;
}

#line 1 "old_Math/Bitwise_And_Convolution.cpp"
vector<long long> and_fwt(vector<long long> A, bool inv){
	int N = A.size();
	for (int i = 1; i < N; i <<= 1){
		for (int j = 0; j < N; j++){
			if ((j & i) == 0){
				if (!inv){
					A[j] += A[j | i];
					A[j] %= MOD;
				} else {
					A[j] -= A[j | i];
					A[j] += MOD;
					A[j] %= MOD;
				}
			}
		}
	}
	return A;
}
vector<long long> and_convolution(vector<long long> A, vector<long long> B){
	int N = A.size();
	A = and_fwt(A, false);
	B = and_fwt(B, false);
	vector<long long> C(N);
	for (int i = 0; i < N; i++){
		C[i] = A[i] * B[i] % MOD;
	}
	C = and_fwt(C, true);
	return C;
}

Back to top page