CF453D Little Pony and Elements of Harmony题解-171主机测评

CF453D Little Pony and Elements of Harmony

题目描述

题意翻译：

谐律精华是六个超自然的神器，它们代表着"和谐"自身主观的意志。它们被认为是小马国最强大的力量。

谐律精华的内部，可以被看作是一个有 $n$ 个节点的完全图，从 $0$ 到 $n - 1$ 标号， $n$ 是一个二的幂次，等于 $2^m$ 。

上图是六个谐律精华。

谐律精华中的能量在不断变化。根据古籍记载，节点 $u$ 在时间 $i$ 时的能量(记作 $e_i[u]$ )为：

$ei[u]=∑vei−1[v]⋅b[f(u,v)]e_i[u]=\\sum_ve_{i-1}[v]\\cdot b[f(u,v)]$ 。这里 $b []$ 称作变换系数——一个有 $m + 1$ 个元素的数组。而 $f (u, v)$ 为二进制数 $v)(u\\;xor\\;v)$ 中 $1$ 的个数。

给定变换系数 $b []$ 和在时间 $0$ 时的初始能量分布 $e_0[]$ 。帮助暮光闪闪预测在时刻 $t$ 时的能量分布。答案可能非常大，你只要输出答案除以 $p$ 的余数即可。

输入格式

第一行三个整数 $m, t, p$ $(1≤m≤20,0≤t≤1018,2≤p≤109)(1\\le m\\le 20,0\\le t\\le10^{18},2\\le p\\le10^9)$ 。

接下来一行 $n$ $n=2^m)$ 个整数 $e_0[i]$ $1≤e0[i]≤109,0≤i<n1\\le e_0[i]\\le 10^9,0\\le i<n$ 。

接下来一行 $m + 1$ 个整数 $b [i]$ $(0≤b[i]≤109,0≤i≤m)(0\\le b[i]\\le 10^9,0\\le i\\le m)$ 。

输出格式

输出 $n$ 行，第 $i$ 行包含一个整数表示 $e_t[i]$ 对 $p$ 取模的结果。

输入输出样例 #1

输入 #1

2 2 10000
4 1 2 3
0 1 0

输出 #1

14
6
6
14

思路

FWT即可。

代码见下

#include<bits/stdc++.h>
using namespace std;
long long n,m,t,p,st;
__int128 e0[2000006],e[2000006],b[2000006],a[2000005];
__int128 abc(__int128 a1){
__int128 c1=0;
while(a1!=0){
c1+=a1%2;
a1/=2;
}
return c1;
}
void xor1(__int128 *f,long long x){
for(int o=2,k=1;o<=n;o*=2,k*=2){
for(int i=0;i<=n–1;i+=o){
for(int j=0;j<=k–1;j++){
f[i+j]=(f[i+j]+f[i+j+k])%p;
f[i+j+k]=(f[i+j]–f[i+j+k]–f[i+j+k]+p*2)%p;
f[i+j]=(f[i+j])%p;
f[i+j+k]=(f[i+j+k])%p;
}
}
}
if(x==0){
for(int i=0;i<=n–1;i++){
f[i]=f[i]/n;
}
}
return ;
}
__int128 pow2(__int128 a1,long long b1){
__int128 c1=1;
while(b1!=0){
if(b1%2==1){
c1=c1*a1%p;
}
a1=a1*a1%p;
b1/=2;
}
return c1;
}
int main(){
cin>>m>>t>>p;
n=(1<<m);
p=p*n;
for(int i=0;i<=n–1;i++){
cin>>st;
e0[i]=st;
e0[i]%=p;
}
for(int i=0;i<=m;i++){
cin>>st;
b[i]=st;
}
for(int i=0;i<=n–1;i++){
a[i]=b[abc(i)];
}
for(int i=0;i<=n–1;i++){
e[i]=a[i];
}
xor1(e0,1);
xor1(e,1);
for(int i=0;i<=n–1;i++){
e0[i]=(pow2(e[i],t)*e0[i])%p;
}
xor1(e0,0);
for(int i=0;i<=n–1;i++){
cout<<(long long)(e0[i]+p)%p<<endl;
}
return 0;
}

CF453D Little Pony and Elements of Harmony题解