首页 > 其他分享 >2024.11.8 鲜花

2024.11.8 鲜花

时间:2024-11-08 16:42:38浏览次数:1  
标签:2024.11 鲜花 int Fmt long 卷积 MOD out

Moon Halo
Some deserts on this planet were oceans once
这颗星球上的一些沙漠曾是海洋
Somewhere shrouded by the night, the sun will shine
被黑夜笼罩的地方,也会迎来光明
Sometimes I see a dying bird fall to the ground
偶尔也会见到濒死的鸟跌落地面
But it used to fly so high
但它也曾展翅高飞
I thought I were no more than a bystander till I felt a touch so real
我本以为我不过是个旁观者 直到我感觉到如此真实的触觉
I will no longer be a transient when I see smiles with tears
当我看到人们含泪的微笑 我便不再是个匆匆过客
If I have never known the sore of farewell and pain of sacrifices
如果不曾知晓生离死别的伤痛
What else should I engrave on my mind
我又该将什么铭记于心
Frozen into icy rocks, that's how it starts
冰冻成石一般的开端
Crumbled like the sands of time, that's how it ends
沙漏崩落一般的终结
Every page of tragedy is thrown away burned out in the flame
悲剧的每一页已被焚烧殆尽
A shoulder for the past
给过往一个肩膀
Let out the cries imprisoned for so long
让久被禁锢的哭泣得以放声
A pair of wings for me at this moment
给此刻的自己一双翅膀
To soar above this world
翱翔于世界之上
Turn into a shooting star that briefly shines but warms up every heart
化为一颗流星,给每个心灵一瞬的希望
May all the beauty be blessed
愿所有的美好都能得到祝福
May all the beauty be blessed
愿所有的美好都能得到祝福
I will never go
我不会离开
There's a way back home
这就是我们的归途
Brighter than tomorrow and yesterday
比过往与未来都要更加闪耀着
May all the beauty be blessed
愿所有的美好都能得到祝福
Wave good-bye to the past when hope and faith have grown so strong and sound
当希望和信念羽翼丰满,就向昨日告别吧
Unfold this pair of wings for me again
再一次为我张开这双羽翼
To soar above this world
翱翔于世界之上
Turned into a moon that always tells the warmth and brightness of the sun
化为月亮长久地传达着太阳的光耀
May all the beauty be blessed
愿所有的美好都能得到祝福
May all the beauty be blessed
愿所有的美好都能得到祝福

你说得对,没人问我,但这是我们初一第一首起床铃

sosdp,FMT,FWT 下

不是,怎么 FMT 只有板子和不可做题啊!!!

那就先放板子吧:CF582E Boolean Function

solution

起手建表达式树。

\(A,B,C,D\) 只有四个,直接状压,设 \(dp_{i,j}\) 表示在 \(i\) 的子树内,状态为 \(j\) 的方案数,转移就是 OR 和 AND 卷积。

但是队奶告诉我可以 FMT 可以直接求异或卷积,快快推荐一下。

感觉放课件太魔怔了,想看的可以看 this,就复述一下把。

考虑前缀和时第 \(i\) 维实际上是由两个第 \(i-1\) 维组成的,设其前缀和完 \(i-1\) 维的值为 \(a_i,b_i\),那么前缀和实际上就是变成了 \(a_i,b_i+a_i\)。

类似定义新运算,依次对第 \(i\) 维做 \(a_i+b_i,a_i-b_i\)。

逆运算是显然的 \(\frac{a_i+b_i}2,\frac{a_i-b_i}2\)

于是我们用这个做莫变即可。

证明:\((a_i,b_i)*(c_i,d_i)\to(a_i+b_i,a_i-b_i)(c_i+d_i,c_i-d_i)=(a_ic_i+a_id_i+b_ic_i+b_id_i,a_ic_i-a_id_i-b_ic_i+b_id_i)\to(a_ic_i+b_id_i,a_id_i+b_ic_i)\)

于是就有真正的板子了:P4717 【模板】快速莫比乌斯/沃尔什变换 (FMT/FWT)

放个代码:

Code
#include<bits/stdc++.h>
using namespace std;
using llt=long long;
using llf=long double;
using ull=unsigned long long;
#define endl '\n'
#ifdef LOCAL
	FILE *InFile=freopen("in_out/in.in","r",stdin),*OutFile=freopen("in_out/out.out","w",stdout);
#else
	FILE *InFile=stdin,*OutFile=stdout;
#endif

const int N=1<<17|3,MOD=998244353,Inv=(MOD+1)/2;
int Add(int a,int b){return (a+=b)>=MOD?a-MOD:a;}
int Sub(int a,int b){return (a-=b)<0?a+MOD:a;}
int ca[N],cb[N],a[N],b[N],n;

void Fmt(int *f,const function<void(int &,int &)> &F){for(int i=1;i<n;i<<=1) for(int j=0;j<n;++j) if(j&i) F(f[j^i],f[j]);}
const function<void(int &,int &)>  
	Or=[](int &a,int &b){b=Add(a,b);},
	And=[](int &a,int &b){a=Add(a,b);},
	Xor=[](int &a,int &b){int t=a; a=Add(a,b),b=Sub(t,b);};
void Cp(){memcpy(a,ca,sizeof a),memcpy(b,cb,sizeof b);}
void Mrg(){for(int i=1;i<=n;++i) a[i]=1ll*a[i]*b[i]%MOD;} 
void Out(){for(int i=1;i<=n;++i) cout<<a[i]<<' '; cout<<endl;}

int main(){
	ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
	cin>>n; n=1<<n; for(int i=1;i<=n;++i) cin>>ca[i]; for(int i=1;i<=n;++i) cin>>cb[i];
	Cp(),Fmt(a+1,Or),Fmt(b+1,Or),Mrg(),Fmt(a+1,[](int &a,int &b){b=Sub(b,a);}),Out();
	Cp(),Fmt(a+1,And),Fmt(b+1,And),Mrg(),Fmt(a+1,[](int &a,int &b){a=Sub(a,b);}),Out();
	Cp(),Fmt(a+1,Xor),Fmt(b+1,Xor),Mrg(),Fmt(a+1,[](int &a,int &b){int t=a; a=1ll*(a+b)*Inv%MOD,b=1ll*(t-b+MOD)*Inv%MOD;}),Out();
}

但只会这个还不够,你还要会写子集卷积。

求 \(h(S)=\sum_{T\subseteq S} f(T)g(S-T)\)

你发现这个相较于 OR 卷积多出了一个 \(A\cap B = \varnothing\)。

发现 \(A\cap B = \varnothing\Leftrightarrow |A|+|B|=|A \cup B|\)

所以如果我们每次只考虑大小为 \(p\) 的集合,将所的函数记为 \(f_p\),有 \(h_{i+j}(S)=\sum_{T\subseteq S} f_i(T)g_j(S-T)\)

所以对每一个 \(p\) 单独计算最后在暴力卷积即可,复杂度 \(n^2\log n\) 或 \(n\log^2 n\)。

板子:P6097 【模板】子集卷积

Code
#include<bits/stdc++.h>
using namespace std;
using llt=long long;
using llf=long double;
using ull=unsigned long long;
#define endl '\n'
#ifdef LOCAL
	FILE *InFile=freopen("in_out/in.in","r",stdin),*OutFile=freopen("in_out/out.out","w",stdout);
#else
	FILE *InFile=stdin,*OutFile=stdout;
#endif

const int N=1<<20|3,MOD=1e9+9,Inv=(MOD+1)/2;
int Add(int a,int b){return (a+=b)>=MOD?a-MOD:a;}
int Sub(int a,int b){return (a-=b)<0?a+MOD:a;}
int n,ca[23][N],cb[23][N],aas[23][N];

void Fmt(int *f,const function<void(int &,int &)> &T){for(int i=0;i<n;++i) for(int j=0;j<1<<n;++j) if(j>>i&1) T(f[j^1<<i],f[j]);}
const function<void(int &,int &)> Or=[](int &a,int &b){b=Add(a,b);},IOr=[](int &a,int &b){b=Sub(b,a);};

int main(){
	ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
	cin>>n; for(int i=0;i<1<<n;++i) cin>>ca[__builtin_popcount(i)][i]; for(int i=0;i<1<<n;++i) cin>>cb[__builtin_popcount(i)][i];
	for(int i=0;i<=n;++i) Fmt(ca[i],Or),Fmt(cb[i],Or);
	for(int i=0;i<=n;++i) for(int j=0;j<=i;++j) for(int s=0;s<1<<n;++s) aas[i][s]=Add(aas[i][s],1ll*ca[j][s]*cb[i-j][s]%MOD);
	for(int i=0;i<=n;++i) Fmt(aas[i],IOr); for(int i=0;i<1<<n;++i) cout<<aas[__builtin_popcount(i)][i]<<' ';
}

FWT

其实 FWT 和 FMT 本质是一个东西,它们俩变换出来的多项式都一模一样。

上次也说了,FWT 是基于变换的思想实现的,和 FFT 更相似,也更难写,所以学这个不是为了写板子的,其实是在学一些性质和构造本质的东西。

可以先去模板题的题解看一下板子。

容易发现,这个东西是线性变换,所以有 \(FWT(A+B)=FWT(A)+FWT(B),FWT(cA)=cFWT(A)\)。

以下的 \(i,j\) 都表示状压后的状态。

我们设,对于第 \(i\) 个元素,他会给每个 \(j\in[1,n]\) 贡献 \(c(i,j)\) 次,其实用矩阵乘法表示就是那个矩阵。

容易发现,对于 OR 卷积,\(c(i,j)=[i\&j==i]\),AND 卷积,\(c(i,j)=[i\&j==i]\),XOR 卷积,\(c(i,j)=(-1)^{popcount(i\&j)}\)

知道了上面的,来做好题:CF1119H Triple

solution

首先暴力卷积是显然的,考虑以 \(a,b,c\) 为指数,\(x,y,z\) 为对应系数,直接做异或卷积即可,复杂度 \(nk2^k\),过不去。

发现只有三个位置有值,对于每个的莫变可以暴力乘上贡献次数,这样的复杂度是 \((n+k)2^k\),还是过不去。

发现最后的卷积数组 \(S\) 的第 \(i\) 项 \(S_i=\prod\limits_{k=1}^n c(k,a_k)x+c(k,b_k)y+c(k,c_k)z\)

后面的取值只有 \(8\) 种可能,如果你有耐心,依据接下来的规律找出 \(8\) 种次数的 \(8\) 个方程也是不难做到的,但是可以减少情况。

考虑将 \(a,b,c\) 都 \(\oplus a\),最后查询时也 \(\oplus a\),这样 \(c(k,a_k)=c(k,0)=1\),所以只有 \(4\) 种情况。

考虑设 \(x+y+z,x+y-z,x-y+z,x-y-z\) 的次数分别为 \(t_1,t_2,t_3,t_4\),考虑解方程,显然的第一个方程是 \(t_1+t_2+t_3+t_4=n\)

发现 \(y\) 和 \(z\) 的符号互相无关,考虑 \(y\) 的系数,将 \(x=0,y=1,z=0\) 带入变换,得到的结果为 \(FMT(G_i)\),则有 \(\sum FMT(G_i)=\sum c(k,b_k)=t_1+t_2-t_3-t_4\),计算 \(\sum FMT(G_i)\) 是容易的,发现 FMT 是线性变换,求 \(FMT(G'[k]=\sum[b_k=k])\) 即可。

对于 \(z\) 做类似处理可以在得到一个方程,考虑最后一个方程,发现其应该由 \(y,z\) 共同给出,于是对于每个 \(i\) 将 \(F_i[b_i\oplus c_i]=1\)(这里 \(F[k]\) 表示多项式 \(F\) 的 \(k\) 次系数,前面的两种带入可以视为 \(G_i=F_i[b_i]=1\) 和 \(G_i=F_i[c_i]=1\) ),容易发现其卷积结果是 \(\sum c(i,b_i)c(i,c_i)=t_1-t_2-t_3+t_4\)。

解方程即可,最后做一遍 IFMT 即可,复杂度 \(O((k+\log n)2^k)\)。

Code
#include<bits/stdc++.h>
using namespace std;
using llt=long long;
using llf=long double;
using ull=unsigned long long;
#define endl '\n'
#ifdef LOCAL
	FILE *InFile=freopen("in_out/in.in","r",stdin),*OutFile=freopen("in_out/out.out","w",stdout);
#else
	FILE *InFile=stdin,*OutFile=stdout;
#endif

const int N=2e5+3,MOD=998244353,Inv=(MOD+1)/2;
int n,m,x,y,z,p1[N],p2[N],p3[N],aas[N],sa;

int Fpw(int a,int b){
	int ans=1;
	while(b){
		if(b&1) ans=1ll*a*ans%MOD;
		a=1ll*a*a%MOD,b>>=1;
	}
	return ans;
}
void Fmt(int *f,const function<void(int &,int &)> &F){for(int i=1;i<m;i<<=1) for(int j=0;j<m;++j) if(j&i) F(f[j^i],f[j]);}
const auto Xor=[](int &a,int &b){int t=a; a=(a+b)%MOD,b=(t-b)%MOD;};
const auto IXr=[](int &a,int &b){int t=a; a=1ll*(a+b)*Inv%MOD,b=1ll*(t-b)*Inv%MOD;};

int main(){
	ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
	cin>>n>>m>>x>>y>>z,m=1<<m; for(int i=1;i<=n;++i){int a,b,c; cin>>a>>b>>c; sa^=a,b^=a,c^=a,++p1[b],++p2[c],++p3[b^c];}
	Fmt(p1,Xor),Fmt(p2,Xor),Fmt(p3,Xor); int s1=(1ll*x+y+z)%MOD,s2=(1ll*x+y-z)%MOD,s3=(1ll*x-y+z)%MOD,s4=(1ll*x-y-z)%MOD;
	for(int i=0;i<m;++i){
		int c1=(1ll*n+p1[i]+p2[i]+p3[i])/4,
			c2=(1ll*n+p1[i]-c1-c1)/2,
			c3=(1ll*n+p2[i]-c1-c1)/2,
			c4=(1ll*n+p3[i]-c1-c1)/2;
		aas[i]=1ll*Fpw(s1,c1)*Fpw(s2,c2)%MOD*Fpw(s3,c3)%MOD*Fpw(s4,c4)%MOD;
	}
	Fmt(aas,IXr); for(int i=0;i<m;++i) cout<<(aas[i^sa]+MOD)%MOD<<' ';
}

扩展到 \(k\) 进制

对于取 \(max,min\) 可以直接套 \(FMT\),因为其本质是前后缀和,但是不进位加法涉及一些深刻矛盾,我还不会,等我会了在写。

P


标签:2024.11,鲜花,int,Fmt,long,卷积,MOD,out
From: https://www.cnblogs.com/xrlong/p/18534992

相关文章

  • 鲜花:bitset求解高维偏序
    书接上回一维偏序直接做、二维偏序套线段树或归并排序、三维偏序可以树套树或者CDQ套树,那四维偏序呢?可以CDQ套树套树。那五维偏序呢?可以发现,无论是CDQ分治还是树,都很难再继续嵌套,再写下去不但码量巨大,还巨难调,效率还相当低。树或CDQ嵌套\(m\)维偏序时间复杂度为\(O(n......
  • 2024.11.7随笔
    前言觉得就两三个人在机房安静自习真的好,有很多事情要做,规划好后按计划走不会感到迷茫而无所适从,头脑中也有时间的意识。只能说我个人比较喜欢对时间的掌控感,也喜欢安静的环境。明天大家就都要归队了,不知道下一次这么安静又要等到多久?写题今天水了个三倍经验所以就过了六道题,然......
  • [考试记录] 2024.11.7 noip模拟赛7
    基础暴力分300pts......
  • 2024.11.6 鲜花
    アイデン貞貞メルトダウンアリ!?ナシ!?ナシ!?アリ!?ついてるついてないあれどっち?どっち?Trance,trance,trance蟻!?梨!?nAシ!?ァ理!?自我字が崩壊!インドア警備隊紫外線さよなら(バイバイalright!一級在宅allday!)やる気の“や”の字どっかにいっちゃったんだナイナイ心技体......
  • 2024.11.6随笔
    前言半期考试第一天?停课!前一天晚上提前做好了这几天的计划,本来以为晚上要回班自习,结果不用,于是计划就奇妙的往前平移了!CSP后我也反思了自己近期的学习情况,无论是whk还是竞赛。只能说有目标但是缺乏决心和长远的目光,且自己的日常习惯做的还不够好,有的东西没有坚持好。然后就......
  • 2024.11.6训练记录
    今天主要是做的单个题。下次打模拟赛就是放假了。怕会有段时间没打手感下降/ll。csp-J2024Ddp。f[i][j]表示,第i轮结束后,最终颜色是j的结束位置。f[i][j]=-1:状态不能达到。f[i][j]=0:可以在多个人处结束。(即有大于等于2个序列中的j颜色可以被转到)f[i][j]=l:只有在第l......
  • GJ Round (2024.11) Round 22~?
    前言:点此返回GJRound目录Round22(11.4)唯一一次快速补完了题AAT_arc077_a[ABC066C]pushpush不懂这原题标号咋这么奇怪给你一个序列\(a_1\dotsa_n\),按照如下规则构造新序列:将\(a_i\)插入序列末尾将整个序列反转模拟/打表找规律:当\(n\)为奇数时......
  • [2024.11.06]NOIP 模拟赛
    不会tarjan不会广义串并联图……赛时T1看上去很可做。看到中位数首先想到二分。在二分的背景下,问题转化为求当前最多能使多少个元素大于等于某个定值。我们不妨先让所有的元素都选择\(a\)值,然后相当于要选择一段连续的\(b\)替换一些\(a\),要求最后总和最大。所以可以新设......
  • 2024.11.5 鲜花
    放点屁话大家多交hack。有的人觉得没意义,这也无可厚非,有的人怕被骂,我一直认为这是多余的,但竟然真的有人骂?这是无法理解的,所以发文声讨一下。叠甲:本文仅代表个人观点,可能有过激言论,不针对任何人。不是你们骂交hack的人是什么心态啊。你站在道德制高点上,谴责人家交hack,你首......
  • 2024.11.5 闲话
    别人的闲话都推图or歌,我的鲜花啥也没有。我也没啥可推的啊,求图or歌高维前缀和常见的柿子是\(s_{i,j}=s_{i-1,j}+s_{i,j-1}-s_{i-1,j-1}+a_{i,j}\)。但是还可以一维一维求。点此查看代码rep(i,1,n,1)rep(j,1,m,1)a[i][j]+=a[i-1][j];rep(i,1,n,1)rep(j,1,m,1)a[i]......