[51nod1773] A国的贸易 [FWT]

[51nod1773] A国的贸易 [FWT]

​​传送门​​

设当前状态为 Fi

#include#define N (1 << 20) + 50using namespace std;typedef long long ll;const int Mod = 1000000007, inv2 = (Mod + 1) / 2;int n, T; ll a[N], b[N];ll mul(ll a, ll b){ return a * b % Mod;}ll add(ll a, ll b){ return (a + b) % Mod;}void Xor(ll *a, int flag){ for(int i = 1; i < n; i <<= 1) for(int j = 0; j < n; j += (i<<1)) for(int k = 0; k < i; k++){ ll v = a[k + j]; if(flag == 1){ a[k + j] = add(v, a[k + j + i]); a[k + j + i] = add(v, Mod - a[k + j + i]); } else{ a[k + j] = mul(inv2, add(v, a[k + j + i])); a[k + j + i] = mul(inv2, add(v, Mod - a[k + j + i])); } }}int main(){ scanf("%d%d", &n, &T); n = 1 << n; for(int i = 0; i < n; i++) scanf("%d", &a[i]); for(int i = 1; i < n; i <<= 1) b[i] = 1; b[0] = 1; Xor(a, 1); Xor(b, 1); for(;T;T>>=1){ if(T&1){ for(int i = 0; i < n; i++) a[i] = mul(a[i], b[i]);} for(int i = 0; i < n; i++) b[i] = mul(b[i], b[i]); } Xor(a, -1); for(int i = 0; i < n; i++) cout << a[i] << " "; return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。