codeforces 616F Expensive Strings (广义后缀自动机)
https://codeforces.com/contest/616/problem/F
题意:
给你n个字符串串,串的权值为,对于一个字符串有函数
其中为字符串在串中出现的次数。
让你构造一个使得最大,输出即可。
题解:
先考虑单独一个串怎么做。
对这个串建SAM,对于每一个节点,实际上它的贡献就是
而对于多个串,其实是一样的。直接用广义后缀自动机做就好啦
代码:
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
const int mod=1e9+7;
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
typedef long long ll;
typedef double db;
typedef vector<int> vi;
typedef pair<int,int> pii;
ll qpow(ll a,ll b){ll ans=1;a%=mod;assert(b>=0);for(;b;b>>=1){if(b&1)ans=ans*a%mod;a=a*a%mod;}return ans;}
ll gcd(ll a,ll b){return b>0?gcd(b,a%b):a;}
int n,m,T;
string s[maxn];
int c[maxn];
struct SAM{
int nxt[maxn<<1][30];
int link[maxn<<1];
int step[maxn<<1];
ll sum[maxn<<1];
int sz,last,rt;
void init(){
sz=last=rt=1;
}
void add(int c){
int p=last;
int np=++sz;
last=np;
step[np]=step[p]+1;
memset(nxt[np],0,sizeof nxt[np]);
while(!nxt[p][c]&&p){
nxt[p][c]=np;
p=link[p];
}
if(p==0){
link[np]=rt;
}else{
int q=nxt[p][c];
if(step[q]==st