Little Pony and Elements of Harmony

1
2
3
4
5
6
7
8
import java.util.Scanner;
public class Main {
    public static void main(String[] arg) {
        Scanner scanner = new Scanner(System.in);
        // todo
    }
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include<bits/stdc++.h>

const int N = (1 << 20) | 1;

using namespace std;

#define int long long

int n, m, t, p, b[N], a[N], mod, e[N];

void XOR(int *f, int type) {

for(int mid = 1; mid < n; mid <<= 1)

for(int len = mid << 1, j = 0; j < n; j += len)

for(int k = 0; k < mid; k ++) {

int x = f[j + k] % mod, y = f[j + k + mid] % mod;

f[j + k] = (x + y) % mod;

f[j + k + mid] = (x - y + mod) % mod;

}

if(type == -1) {

for(int i = 0; i < n; i ++) f[i] = f[i] / n;

}

int mul(int a, int b, int mod) {

return (a * b - (int)((long double)a / mod * b) * mod + mod) % mod ;

}

signed main() {

ios::sync_with_stdio(false);

cin.tie(0);

cin >> m >> t >> p;

n = 1 << m; mod = p * n;

for(int i = 0; i < n; i ++) cin >> e[i];

for(int i = 0; i <= m; i ++)

cin >> b[i];

for(int i = 0; i < n; i ++)

a[i] = b[__builtin_popcount(i)];

XOR(e, 1); XOR(a, 1);

while(t) {

if(t & 1) {

for(int i = 0; i < n; i ++)

e[i] = mul(e[i], a[i], mod);

}

t >>= 1;

for(int i = 0; i < n; i ++)

a[i] = mul(a[i], a[i], mod);

}

XOR(e, -1);

for(int i = 0; i < n; i ++)

cout << e[i] << "\n";

}

#include<bits/stdc++.h>

#define ll long long

#define PII pair<int,int>

using namespace std;

template<class T>

inline void read(T &x){

x=0; int sign=1; char c;

do{ c=getchar(); if(c=='-') sign=-1; }while(!isdigit(c));

do{ x=x*10+c-'0',c=getchar();}while(isdigit(c));

x*=sign;

}

const int N=2e6+50;

ll mod;

inline ll qpow(ll a,ll b){

ll ans=1LL;

for(;b;b>>=1,a=(__int128)a*a%mod) if(b&1) ans=(__int128)ans*a%mod;

return ans;

}

int n,m;

void FWT(ll *a,int sign){

for(int k=n,len=1<<(n-1);k>=1;--k,len>>=1)

for(int i=0;i<m;i+=1<<k)

for(int j=i;j<i+len;++j)

a[j]=(a[j]+a[j+len])%mod,

a[j+len]=(a[j]+mod-a[j+len]+mod-a[j+len])%mod;

}

ll t,a[N],b[N],c[N];

int main(){

read(n),read(t),read(mod);

m=1<<n,mod*=m;

for(int i=0;i<m;++i) read(a[i]),a[i]%=mod;

for(int i=0;i<=n;++i) read(c[i]),c[i]%=mod;

for(int i=1;i<m;++i) b[i]=b[i>>1]+(i&1);

for(int i=0;i<m;++i) b[i]=c[b[i]];

FWT(a,1),FWT(b,1);

for(int i=0;i<m;++i) c[i]=(__int128)qpow(b[i],t)*a[i]%mod;

FWT(c,1);

for(int i=0;i<m;++i) printf("%lld\n",c[i]/m);

return 0;

}

详情