新疆省赛A.A. chino with string(AC自动机+广义矩阵快速幂)
2021/8/27 23:10:47
本文主要是介绍新疆省赛A.A. chino with string(AC自动机+广义矩阵快速幂),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
前置知识:
[TJOI2012]可乐
广义矩阵快速幂
AC自动机
#include<bits/stdc++.h> using namespace std; const int maxn=1010; typedef long long ll; int nxt[maxn][26],fail[maxn]; ll c[maxn]; int tot=1,rt=1,n,m; void ins (string s,int x) { int u=rt; for (char i:s) { if (!nxt[u][i-'a']) nxt[u][i-'a']=++tot; u=nxt[u][i-'a']; } c[u]+=x; } void build () { queue<int> q; fail[rt]=rt; for (int i=0;i<26;i++) { if (!nxt[rt][i]) nxt[rt][i]=rt; else { fail[nxt[rt][i]]=rt; q.push(nxt[rt][i]); } } while (q.size()) { int u=q.front(); q.pop(); for (int i=0;i<26;i++) { if (!nxt[u][i]) { nxt[u][i]=nxt[fail[u]][i]; } else { fail[nxt[u][i]]=nxt[fail[u]][i]; q.push(nxt[u][i]); } } } } vector<int> g[maxn]; ll cc[maxn]; void dfs (int u,ll sum) { cc[u]=sum; for (int v:g[u]) { dfs(v,sum+c[v]); } } struct matrix { ll m[205][205]; }ans,base; matrix mul (matrix a,matrix b) { matrix ans; for (int i=1;i<=tot;i++) for (int j=1;j<=tot;j++) ans.m[i][j]=-1e18; // for (int i=1;i<=tot;i++) for (int j=1;j<=tot;j++) { // ans.m[i][j]=max(a.m[i][j],b.m[i][j]); // } for (int k=1;k<=tot;k++) { for (int i=1;i<=tot;i++) { for (int j=1;j<=tot;j++) { if (a.m[i][k]!=-1e18&&b.m[k][j]!=-1e18) ans.m[i][j]=max(ans.m[i][j],a.m[i][k]+b.m[k][j]); } } } return ans; } void qpow (int p) { while (p) { if (p&1) ans=mul(ans,base); base=mul(base,base); p>>=1; } } /* 17 3 helloworld 100 ldldl 5 aaa -6 */ int main () { cin>>n>>m; for (int i=1;i<=m;i++) { string s; int x; cin>>s>>x; ins(s,x); } build(); for (int i=2;i<=tot;i++) g[fail[i]].push_back(i); dfs(1,c[1]); //for (int i=1;i<=tot;i++) printf("%d ",cc[i]); //puts(""); for (int i=1;i<=tot;i++) for (int j=1;j<=tot;j++) { base.m[i][j]=-1e18; } for (int i=1;i<=tot;i++) { for (int j=0;j<26;j++) { base.m[i][nxt[i][j]]=cc[nxt[i][j]]; } } ans=base; // for (int i=1;i<=tot;i++) { // for (int j=1;j<=tot;j++) printf("%lld ",base.m[i][j]); // puts(""); // } //n=1; //n=17; qpow(n-1); long long Ans=-1e18; for (int i=1;i<=tot;i++) { Ans=max(Ans,ans.m[1][i]); //printf("%lld ",ans.m[1][i]); } printf("%lld\n",Ans); }
这篇关于新疆省赛A.A. chino with string(AC自动机+广义矩阵快速幂)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-25Elevate Your Lead Generation Game with Maps Scraper AI
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 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项独有的隐藏技能