首页 > 其他分享 >2024.11.10 鲜花

2024.11.10 鲜花

时间:2024-11-10 21:19:02浏览次数:1  
标签:10 2024.11 鲜花 int long 卷积 using MOD out

Triple 扩展

像神一样呐
愛のネタバレ
「別れ」っぽいな
人生のネタバレ
「死ぬ」っぽいな
なにそれ意味深で
かっこいいじゃん
それっぽい単語集で踊ってんだ
失敬
とぅ とぅる とぅ とぅ とぅる
“風”
とぅ とぅる とぅ とぅ とぅる
“風”
とぅ とぅる とぅ とぅ とぅる
“風”
ぽいじゃん ぽいじゃん
とぅ とぅる とぅ とぅ とぅる
“風”
とぅ とぅる とぅ とぅ とぅる
“風”
とぅ とぅる とぅ とぅ とぅる
神っぽいな
もういいぜ もういいぜ それ
もういいぜ もういいぜ
逆に興奮してきたなあ
おっきいね おっきいね 夢
おっきいね おっきいね
景気いいけど 品性はthe end
うええい うええい
"Gott ist tot"
神っぽいな それ 卑怯
神っぽいな それ "my god"
アイウォンチュー ウォンチュー
IQが下がっていく感じ
邪心ぽいな それ 畢竟
邪心ぽいな それ "my god"
アイヘイチュー ヘイチュー
害虫はどっち
その髪型 その目 その口元
その香水 その服 そのメイク
アレっぽいな それ 比況
アレっぽいな それ
その名言 その意見 その批評
そのカリスマ
そのギャグ そのセンス
神っぽいな それ 卑怯
ぽいな ぽいな ぽい 憧れちゃう
とぅ とぅる とぅ とぅ とぅる
“風”
とぅ とぅる とぅ とぅ とぅる
“風”
とぅ とぅる とぅ とぅ とぅる
“風”
ぽいじゃん ぽいじゃん
とぅ とぅる とぅ とぅ とぅる
“風”
とぅ とぅる とぅ とぅ とぅる
“風”
とぅ とぅる とぅ とぅ とぅる
神っぽいな
メタ思考する本質は悪意?
人を小馬鹿にしたような作為
無為に生き延びるのは難しい
権力に飲まれて揺らぐ灯り
神を否定し神に成り代わり
玉座で豹変する小物達
批判に見せかけ自戒の祈り
Do you know?
何言ってんの? それ ウザい
何言ってんの? それ
意味がよくわかんないし
眠っちゃうよ マジ
飽きっぽいんだ オーケー
みんな 飽きっぽいんだ オーケー
踊れるやつ
ちょうだい ちょうだい ビーム
きっしょいね きっしょいね それ
きっしょいね きっしょいね
逆にファンになってきたじゃん
ちっちゃいね ちっちゃいね 器
ちっちゃいね ちっちゃいね
天才ゆえ孤独ですね
かっけえ かっけえ
"Gott ist tot"
神っぽいな それ 卑怯
神っぽいな それ "my god"
超健康 健康 言い張って
くたばっていく感じ
ヤケっぽいな それ 畢竟
ヤケっぽいな それ "my god"
もう哀愁 哀愁
エピゴーネンのヒール
そのタイトル その絵
そのストーリー
その音楽 その歌 そのメロディ
アレっぽいな それ 比況
アレっぽいな それ
その名言 その意見 その批評
そのカリスマ
そのギャグ そのセンス
神っぽいな それ 卑怯
ぽいな ぽいな ぽい 憧れちゃうわ
とぅ とぅる とぅ とぅ とぅる
“風”
とぅ とぅる とぅ とぅ とぅる
“風”
とぅ とぅる とぅ とぅ とぅる
“風”
ぽいじゃん ぽいじゃん
とぅ とぅる とぅ とぅ とぅる
“風”
とぅ とぅる とぅ とぅ とぅる
“風”
とぅ とぅる とぅ とぅ とぅる
神っぽいな
愛のネタバレ
「別れ」っぽいな
人生のネタバレ
「死ぬ」っぽいな
すべて理解して患った
無邪気に踊っていたかった 人生

miaomaio:什么玩意,听得脑袋疼,下回请你们听儿歌。

上次鲜花已经讲了这题做法,就不在赘述了。

考虑扩展,形式化的,求:

给定 \(n,m,k\),有 \(n\) 个多项式 \(f_i=\sum\limits_{j=1}^k w_ix^{a_{i,j}},0\le a_{i,j} < 2^m\),求其异或卷积。

显然直接暴力有 \(nm2^m\),或者简单调整一下是 \((n+km)2^m\)。

考虑当 \(n\) 较大而 \(k\) 很小时,如 Triple,考虑一些更好的解法。

首先我们容易发现,考虑变换后的函数的 \(o\) 次项系数 \(\widehat{f}=\sum_{i=1}^k s_{o,i}w_ix^o\) 我们的变换系数 \(s\) 有 \(2^k\) 种取值,我们将其压成 \(k\) 位二进制数,\(1\) 表示取 \(-1\),\(0\) 表示取 \(i\),后面就会发现这样定义的深意,并设 \(c_{Now,t}\) 表示状态是 \(t\) 的次数。这里以及以后我们考虑当前是 \(Now\) 次项。

考虑 Triple 的解题过程,考虑枚举 \(t< 2^k\),即 \(t\) 是全集的子集,设 \(z_{i}=\bigoplus_{j\in t} a_{i,j}\),求 \(\sum\limits_{i=0}^{m} x^{z_{i}}\) 的变换,考虑其第 \(Now\) 项的总共 \(2^k\) 个值。

考虑到卷积是线性变换,其第 \(i\) 实际上是求的 \(\sum FMT(x^{z_i})\),考虑到每种 \(c\) 的情况对系数的贡献,这个值显然等于一些 \(c_i\) 有正有负的加起来。

考虑 \(c_i\) 前面的系数,\(z_{i}=\bigoplus_{j\in t} a_{i,j}\),求 \(\sum\limits_{i=0}^{m} x^{z_{i}}\) 本质是在求卷积,所以其相当于是单独卷 \(a_{i,j}\) 的贡献做点乘,简单分析一下,当 \(t\) 的第 \(k\) 位是 \(1\) 且 \(i\) 的第 \(k\) 位也是 \(1\)(\(i\) 是状压的 \(s\),而 \(i\) 的第 \(k\) 位是一意味着是负)的时候会有 \(-1\) 的贡献,所以其系数是 \((-1)^{|t\&i|}\)。

发现这就是 XOR 变换的系数,于是我们将每个逆变换一下就知道次数了,最后快速幂即可,复杂度 \(n2^k+(m+k)2^{m+k}\)。

下面代码实现了 $k=3$ 的 Triple,可以自行更改 $k$,注意要改值域
#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=1e5+3,MOD=998244353,Inv=(MOD+1)/2,M=17,K=3;
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,m,ck,h[1<<K|3][1<<M|3],sm[1<<K|3],c[N][K+3],tim[1<<M|3],cw[K+3],sw[1<<K|3],aas[1<<M|3];

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,int l,const function<void(int &,int &)> &F){for(int i=1;i<l;i<<=1) for(int j=0;j<l;++j) if(j&i) F(f[j^i],f[j]);}
const auto Xor=[](int &a,int &b){int t=a; a=Add(a,b),b=Sub(t,b);};
const auto IXr=[](int &a,int &b){int t=a; a=1ll*(a+b)*Inv%MOD,b=1ll*(t-b+MOD)*Inv%MOD;};

int main(){
	ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
	cin>>n>>m; ck=3;
	for(int i=0;i<ck;++i) cin>>cw[i];
	for(int i=0;i<1<<ck;++i) for(int j=0;j<ck;++j) sw[i]=(i>>j&1)?Sub(sw[i],cw[j]):Add(sw[i],cw[j]); // sw[i] 表示状态是 i 的值。
	for(int i=1;i<=n;++i){
		for(int j=0;j<ck;++j) cin>>c[i][j];
		++h[0][0]; for(int j=1;j<1<<ck;++j){int low=j&-j,p=__lg(low); ++h[j][sm[j]=sm[j^low]^c[i][p]];} // sm 是异或和,h 维护的是枚举 t 后的多项式。
	}
	for(int i=0;i<1<<ck;++i) Fmt(h[i],1<<m,Xor); // 变换 h
	for(int i=0;i<1<<m;++i){
		for(int j=0;j<1<<ck;++j) tim[j]=h[j][i]; Fmt(tim,1<<ck,IXr); // 复制并做 IFMT
		aas[i]=1; for(int j=0;j<1<<ck;++j) aas[i]=1ll*aas[i]*Fpw(sw[j],tim[j])%MOD; // 统计
	}
	Fmt(aas,1<<m,IXr); for(int i=0;i<1<<m;++i) cout<<aas[i]<<' ';
}

考虑做 OR 卷积,状态设计和推导基本是一样的,就是最后做逆变换是 AND 卷积的逆变换。

下面代码实现了 OR 卷积,没有题,但是和暴力在 $n\le 1000,m\le 10,k\le 10$ 值域在模数范围内的随机数据过拍了,应该不会错
#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=1003,MOD=998244353,M=10,K=10;
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,m,ck,h[1<<K|3][1<<M|3],sm[1<<K|3],c[N][K+3],tim[1<<M|3],cw[K+3],sw[1<<K|3],aas[1<<M|3];
 
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,int l,const function<void(int &,int &)> &F){for(int i=1;i<l;i<<=1) for(int j=0;j<l;++j) if(j&i) F(f[j^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);},IAd=[](int &a,int &b){a=Sub(a,b);};
 
int main(){
	ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
	cin>>n>>m>>ck;
	for(int i=0;i<ck;++i) cin>>cw[i];
	for(int i=0;i<1<<ck;++i) for(int j=0;j<ck;++j) if(i>>j&1) sw[i]=Add(sw[i],cw[j]); // sw[i] 表示状态是 i 的值。
	for(int i=1;i<=n;++i){
		for(int j=0;j<ck;++j) cin>>c[i][j];
		++h[0][0]; for(int j=1;j<1<<ck;++j){int low=j&-j,p=__lg(low); ++h[j][sm[j]=sm[j^low]|c[i][p]];} // sm 是或和,h 维护的是枚举 t 后的多项式。
	}
	for(int i=0;i<1<<ck;++i) Fmt(h[i],1<<m,Or); // 变换 h
	for(int i=0;i<1<<m;++i){
		for(int j=0;j<1<<ck;++j) tim[j]=h[j][i]; Fmt(tim,1<<ck,IAd); // 复制并做 IFMT,做的是 IAnd
		aas[i]=1; for(int j=0;j<1<<ck;++j) aas[i]=1ll*aas[i]*Fpw(sw[j],tim[j])%MOD; // 统计
	}
	Fmt(aas,1<<m,IOr); for(int i=0;i<1<<m;++i) cout<<aas[i]<<' ';
}

AND 类似。

感觉可以上升到子集卷积,有时间在说吧。

P


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

相关文章

  • 如何使用Yolov8训练——胸部肺结节目标检测数据集 1个类别 精确度P:0.655,召回率R:0.575,m
    同时yolov8n训练100个epoch检测结果如下精确度P:0.655,召回率R:0.575,mAP50:0.639,map50-95:0.289数据集可直接使用,未做任何数据增强等预处理胸部肺结节目标检测数据集该数据集已经包括1个类别分别是:target总计图片4882张图像,分辨率是1024x1024像素数据集是txt格式数......
  • 11.4-11.10做题总结
    自从CCF出分,到得知自己考了150pts,再到得知自己无法参加NOIP,我的内心一直是悲痛的。WB老师之后让我做LYD做的算法进阶指南。tx告诉我acwing上有单独题单,于是一直做acwing的题。AcWing89.a^b快速幂即可。AcWing5579.增加模数拆开。AcWing90.64位整数乘法......
  • 【优化参数】粒子群算法PSO求解三轴稳定航天器姿态控制PD参数优化问题【含Matlab源码
    ......
  • 小北的字节跳动青训营与LangChain实战课:深入探索Chain的奥秘(上)写一篇完美鲜花推文?用Se
     前言    最近,字节跳动的青训营再次扬帆起航,作为第二次参与其中的小北,深感荣幸能借此机会为那些尚未了解青训营的友友们带来一些详细介绍。青训营不仅是一个技术学习与成长的摇篮,更是一个连接未来与梦想的桥梁~小北的青训营XMarsCode技术训练营——AI加码,字节跳......
  • P3628 [APIO2010] 特别行动队
    原题链接byd的题敢卡李超线段树!!望周知!!......
  • 11.10闲话-柏林噪声(有图)
    柏林噪声参考博客&&代码出处前言柏林噪声主要用于生成平滑的地形、特效等关于为什么要用柏林噪音,单纯的随机并不能适用于生成地形等场合,那会使得效果十分奇怪,忽高忽低,毫无美感而柏林噪音就像名字般,靠模拟噪声来实现平滑柏林噪音可以有多维,其本质都是一样的例如:2D可用于......
  • Python从0到100(六十九):Python OpenCV-图像加噪与滤波
    前言:零基础学Python:Python从0到100最新最全教程。想做这件事情很久了,这次我更新了自己所写过的所有博客,汇集成了Python从0到100,共一百节课,帮助大家一个月时间里从零基础到学习Python基础语法、Python爬虫、Web开发、计算机视觉、机器学习、神经网络以及人工智能相关知......
  • 10-文件包含、CSRF、SSRF相关练习
    1、文件包含(1)DVWA环境下去包含其他目录的任意3个文件,要求使用相对路径../../../../../(输入多个../返回系统根目录),包含账户信息文件:/etc/passwd包含账户组信息文件:/etc/group包含磁盘配置文件:/etc/fstab(2)远程文件包含使用DVWA的文件包含漏洞包含Upload-......
  • [考试记录] 2024.11.9 noip模拟赛9
    T1星际联邦菠萝算法。不过简化版。考虑从后往前遍历,如果当前的电的联通块大小为\(1\)的话,就把他和前缀最大值或者是前缀最小值连边。如果大于\(1\),那就将联通块里的最小权点和前缀最大值连边即可。#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongcon......
  • DAY109代码审计-PHP模型开发篇&动态调试&反序列化&变量覆盖&TP框架&原生POP链
    知识点1、PHP审计-动态调试-变量覆盖2、PHP审计-动态调试-原生反序列化3、PHP审计-动态调试-框架反序列化PHP常见漏洞关键字SQL注入:selectinsertupdate deletemysql_querymysqli等文件上传:$_FILES,type="file",上传,move_uploaded_file()等XSS跨站:printprint_r......