C 栗酱的数列 kmp结论题 模运算移项差分
2022/9/12 23:23:17
本文主要是介绍C 栗酱的数列 kmp结论题 模运算移项差分,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
链接:https://ac.nowcoder.com/acm/contest/27589/C
来源:牛客网
题目描述
栗酱有一个长度为n的数列A,一个长度为m的数列B,现在询问A中有多少个长度为m的连续子序列A',满足(a'1+b1)%k = (a'2+b2)%k = …… = (a'm + bm)%k。
输入描述:
第一行一个数T,表示有T组数据。 对于每组数据, 第一行三个整数,n, m, k。 第一行输入n个数, a1,a2,…,an, 表示A数列中的数, 第二行输入m个数, b1,b2,…,bm, 表示B数列中的数。输出描述:
每一组数据输出一行,满足条件的连续子序列数量。示例1
输入
复制2 3 2 5 7 8 7 8 7 3 2 5 7 8 9 8 7
输出
复制1 2
备注:
T≤15, 2≤m≤n≤2×105, 1≤ai,bi,k≤109分析:
%运算是可以满足结合律的
移项就变成了差分运算
只要存在 (a[i] - a[i+1]) % k == -(b[i] - b[i+1) % k 就行了
在a的差分数组里kmp b的差分数组
//-------------------------代码---------------------------- //#define int ll const int N = 3e6+10,base = 1e9+10; int n,m,k; int a[N],b[N]; int ca[N],cb[N]; int ha[N],hb[N]; int nxt[N]; void solve() { // cin>>n>>m; cin>>n>>m>>k; fo(i,1,n) a[i] = b[i] = nxt[i] = 0; fo(i,1,n) cin>>a[i],a[i] %= k; fo(i,1,m) cin>>b[i],b[i] %= k; fo(i,1,n-1) a[i] = (a[i+1] - a[i] + k) % k; fo(i,1,m-1) b[i] = (b[i] - b[i+1] + k) % k; n -- ,m -- ; fo(i,2,m) { nxt[i] = nxt[i-1]; while(nxt[i] && b[nxt[i] + 1] != b[i]) nxt[i] = nxt[nxt[i]]; nxt[i] += (b[nxt[i] + 1] == b[i]); } fo(i,1,m) { // cout<<nxt[i]<<' '; } // cout<<endl; int j = 1,cnt = 0; fo(i,1,n) { while(j != 1 && b[j] != a[i]) j = nxt[j-1] + 1; if(a[i] == b[j]) j ++ ; if(j == m + 1) { cnt ++ ; j = nxt[j-1] + 1; } } cout<<cnt<<endl; } void main_init() {} signed main(){ AC();clapping();TLE; cout<<fixed<<setprecision(12); main_init(); // while(cin>>n,n) // while(cin>>n>>m,n,m) int t;cin>>t;while(t -- ) solve(); // {solve(); } return 0; } /*样例区 */ //------------------------------------------------------------
这篇关于C 栗酱的数列 kmp结论题 模运算移项差分的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升
- 2024-05-08代码报错不用愁,CodeGeeX一键完成代码修复、错误解释的功能上线了!