P4287 [SHOI2011] 双倍回文
考虑马拉车，但是我不会马拉车
怎么办，考虑PAM
我们在记录一般的fail之外再记录一个trans指针指向小于等于当前节点长度一半的最长回文后缀
然后枚举每个节点
#include<bits/stdc++.h>
using namespace std;
char s[2000001];
int len[2000001],trans[2000001],n,num[2000001],fail[2000001],last,cur,pos,trie[2000001][26],tot=1;
int getf(int x,int i)
{
while(i-len[x]-1<0||s[i-len[x]-1]!=s[i])x=fail[x];
return x;
}
int main()
{
cin>>n;
scanf("%s",s);
fail[0]=1;len[1]=-1;
for(int i=0;i<n;i++){
pos=getf(cur,i);
if(!trie[pos][s[i]-'a']){
fail[++tot]=trie[ getf(fail[pos],i)][s[i]-'a'];
trie[pos][s[i]-'a']=tot;
len[tot]=len[pos]+2;
num[tot]=num[fail[tot]]+1;
if(len[tot]<=2) trans[tot]=fail[tot];
else{
int tmp=trans[cur];
while(s[i-len[tmp]-1]!=s[i]||((len[tmp]+2)<<1)>len[tot]) tmp=fail[tmp];
trans[tot]=trie[tmp][s[i]-'a'];
}
}
cur=trie[pos][s[i]-'a'];
}
int ans=0;
for(int i=2;i<=tot;i++)
if(((len[trans[i]]<<1)==len[i]&&len[trans[i]]%2==0))
ans=std::max(ans,len[i]);
printf("%d\n",ans);
return 0;
}
暴力枚举每个节点用trans判断
CF1895F Fancy Arrays
妙妙数数题
考虑容斥可以做掉第一个限制，然后就可以dp了
dp好慢，注意到可以写出转移矩阵，然后快速幂搞一发
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
int T,ans,b;
int n,x,k;
struct node{
int dp[41][41];
node operator*(const node &A)const{
node sum;
for(int i=0;i<x;++i)
for(int j=0;j<x;++j)
for(int k=0;k<x;++k)
sum.dp[i][j]=(sum.dp[i][j]+dp[i][k]*A.dp[k][j])%mod;
return sum;
}
}a,res;
int qpow(int a,int b){
int sum=1;
while(b){
if(b&1)sum*=a,sum%=mod;
a*=a,a%=mod;
b>>=1;
}
return sum;
}
signed main(){
std::ios::sync_with_stdio(false);
cin>>T;
while(T--){
cin>>n>>x>>k;
ans=qpow(2*k+1,n-1)*(x+k)%mod;
for(int i=0;i<x;++i)
for(int j=0;j<x;++j)
a.dp[i][j]=(abs(i-j)<=k);
res=node();
for(int i=0;i<x;++i)
res.dp[0][i]=1;
b=n-1;
while(b){
if(b&1)res=res*a;
a=a*a;
b>>=1;
}
for(int i=0;i<x;++i)
ans=(ans-res.dp[0][i]+mod)%mod;
cout<<ans<<"\n";
}
return 0;
}
P7453 [THUSCH2017] 大魔法师
经典的矩阵乘法线段树
每个节点存向量
\[\begin{bmatrix} A\\ B \\ C \\ len \end{bmatrix} \]给出每个操作的变换矩阵
\[\begin{bmatrix} 1& 1& 0& 0& \\ 0& 1& 0& 0& \\ 0& 0& 1& 0& \\ 0& 0& 0& 1& \end{bmatrix} \]\[\begin{bmatrix} 1& 0& 0& 0& \\ 0& 1& 1& 0& \\ 0& 0& 1& 0& \\ 0& 0& 0& 1& \end{bmatrix} \]\[\begin{bmatrix} 1& 0& 0& 0&\\ 0& 1& 0& 0&\\ 1& 0& 1& 0&\\ 0& 0& 0& 1& \end{bmatrix} \]\[\begin{bmatrix} 1& 0& 0& v& \\ 0& 1& 0& 0& \\ 0& 0& 1& 0& \\ 0& 0& 0& 1& \end{bmatrix} \]\[\begin{bmatrix} 1& 0& 0& 0& \\ 0& v& 0& 0& \\ 0& 0& 1& 0& \\ 0& 0& 0& 1& \end{bmatrix} \]\[\begin{bmatrix} 1& 0& 0& 0& \\ 0& 1& 0& 0& \\ 0& 0& 0& v& \\ 0& 0& 0& 1& \end{bmatrix} \]然后可以码了
然后寄了
稍微卡常，矩阵乘法循环展开，取模用一定减法代替
#include<bits/stdc++.h>
#define ls (now<<1)
#define rs (now<<1|1)
using namespace std;
const int mod=998244353;
const int N=3e5+5;
int n,m;
int add(int x) {return x > mod ? x - mod : x;}
struct matrix{
int num[4][4];
matrix() {memset(num, 0, sizeof(num));}
inline void clear() {memset(num, 0, sizeof(num));}
inline void init() {num[0][0] = num[1][1] = num[2][2] = num[3][3] = 1;}//对角线1
matrix(const int a[][4]){
for(int i = 0; i < 4; ++i)
for(int j = 0; j < 4; ++j)
num[i][j] = a[i][j];
}
matrix operator + (const matrix &b) const{
matrix r;
for(int i = 0; i < 4; ++i)
for(int j = 0; j < 4; ++j)
r.num[i][j] = (1ll * num[i][j] + b.num[i][j]) % mod;
return r;
}
matrix operator * (const matrix &b) const{
matrix r;
r.clear();
for(int i = 0; i < 4; ++i)
for(int j = 0; j < 4; ++j){
r.num[i][j] = add(r.num[i][j] + 1ll * num[i][0] * b.num[0][j]%mod);
r.num[i][j] = add(r.num[i][j] + 1ll * num[i][1] * b.num[1][j]%mod);
r.num[i][j] = add(r.num[i][j] + 1ll * num[i][2] * b.num[2][j]%mod);
r.num[i][j] = add(r.num[i][j] + 1ll * num[i][3] * b.num[3][j]%mod);
// for(int k = 0; k < 4; k++) {
// r.num[i][j] = (r.num[i][j] + 1ll * num[i][k] * b.num[k][j] % mod) % mod;
// }
}
return r;
}
}a[N], A[4], B[4];
matrix tr[N<<2],tag[N<<2];
void pushup(int now){
tr[now]=tr[ls]+tr[rs];
}
void pushdown(int now){
tr[ls]=tag[now]*tr[ls];
tr[rs]=tag[now]*tr[rs];
tag[ls]=tag[now]*tag[ls];
tag[rs]=tag[now]*tag[rs];
tag[now].clear(),tag[now].init();
}
void build(int now,int l,int r){
tag[now].init();
if(l==r){
tr[now]=a[l];
return;
}
int mid=(l+r)>>1;
build(ls,l,mid);
build(rs,mid+1,r);
pushup(now);
}
void upd(int now,int l,int r,int L,int R,matrix k){
if(L<=l and r<=R){
tr[now]=k*tr[now];
tag[now]=k*tag[now];
return;
}
pushdown(now);
int mid=(l+r)>>1;
if(L<=mid) upd(ls,l,mid,L,R,k);
if(R>mid) upd(rs,mid+1,r,L,R,k);
pushup(now);
}
matrix query(int now,int l,int r,int L,int R){
if(L<=l and r<=R) return tr[now];
pushdown(now);
int mid=(l+r)>>1;
matrix res;res.clear();
if(L<=mid) res=res+query(ls,l,mid,L,R);
if(R>mid) res=res+query(rs,mid+1,r,L,R);
return res;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
A[0].init(),A[1].init(),A[2].init();
B[0].init(),B[1].init(),B[2].init();
A[0].num[0][1]=A[1].num[1][2]=A[2].num[2][0]=1;
B[2].num[2][2]=0;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i].num[0][0]>>a[i].num[1][0]>>a[i].num[2][0],a[i].num[3][0]=1;
build(1,1,n);
cin>>m;
while(m--){
int opt,l,r,v;
cin>>opt>>l>>r;
if(opt<=3) upd(1,1,n,l,r,A[opt-1]);
else if(opt<=6){
cin>>v;
B[0].num[0][3]=B[1].num[1][1]=B[2].num[2][3]=v;
upd(1,1,n,l,r,B[opt-4]);
}
else{
matrix ans=query(1,1,n,l,r);
cout<<ans.num[0][0]<<" "<<ans.num[1][0]<<" "<<ans.num[2][0]<<"\n";
}
// cout << tr[1].num[0][0] << '\n';
}
}
P2522 [HAOI2011] Problem b
来点莫反
我们先考虑 P3455 [POI2007] ZAP-Queries
也就是给出 \(a,b,d\)，求满足 \(1 \leq x \leq a\)，\(1 \leq y \leq b\)，且 \(\gcd(x,y)=k\) 的二元组 \((x,y)\) 的数量。
也就是 \(\large \sum\limits_{i=1}^{n} \sum\limits_{j=1}^{m} [gcd(i,j)=k]\)
简单思考我们能发现这个式子等价于 \(\large \sum\limits_{i=1}^{n/k} \sum\limits_{j=1}^{m/k} [\gcd(i,j)=1]\) (\(n/k,m/k\)下取整)
我们集中注意力回想一下怎么莫反于是这个式子变成了 \(\large \sum\limits_{i=1}^{n/k} \sum\limits_{j=1}^{m/k} \sum\limits_{d|\gcd(i,j)} \mu(d)\)
然后 \(\large \sum\limits_{i=1}^{n/k} \sum\limits_{j=1}^{m/k} \sum\limits_{d|i,d|j} \mu(d)\)
$=\large \sum\limits_{d=1}^{\min(n,m)} $
标签：21,19,sum,2024,int,num,bmatrix,mod,matrix From： https://www.cnblogs.com/exut/p/18020510