首先需要对一位数和多位数分别计数。一位数的好算，就是字符串里偶数的个数，对于多位数，需要在遍历到偶数的时候，累加上之前跟所有非零数字中间数字的“选或者不选”，也就是2的多少次方，这个技巧可以用前缀和的思想，时间复杂度O(n)
import java.util.*;
public class Main{
static int mod=(int)1e9+7;
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
String s=sc.next();
long ans=0,pre=0;
for(int i=0;i<n;i++){
if(i>0&&s.charAt(i-1)!='0'){
pre++;
}
if(s.charAt(i)%2==0){
ans=(ans+pre+1)%mod;
}
pre=pre*2%mod;
}
System.out.println(ans);
}
}
对于每个字符串，找到可以完整配成子序列的最早位置，中间的长度就是可以的末尾，时间复杂度O(n(len(s1)+len(s2))，本题中s1="ACCEPT",s2="WA
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt(),k=sc.nextInt(),next[][]=new int[n+1][26];
Arrays.fill(next[n],n);
String s=sc.next();
for(int i=n-1;i>=0;i--){
next[i]=next[i+1].clone();
next[i][s.charAt(i)-'A']=i;
}
long ans=0;
for(int i=0;i<n;i++){
//end1是字符串最左边的可能终点，end2-1是最右边的终点
int end1=find(n,i-1,next,"ACCEPT"),end2=find(n,i-1,next,"WA");
ans+=Math.max(0,end2-Math.max(end1,i+k-1));
}
System.out.println(ans);
}
static int find(int n,int start,int next[][],String s){
//寻找s作为子列的最左边下标
for(char c:s.toCharArray()){
start++;
start=next[start][c-'A'];
if(start==n){
break;
}
}
return start;
}
}
对于每个数，计算对于前边的贡献，再乘以对后边贡献的次数，时间复杂度O(nlogC)，其中C=1e6
import java.util.*;
public class Main{
static int mod=(int)1e9+7;
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt(),count[][]=new int[20][2];
long ans=0;
for(int i=0;i<n;i++){
int a=sc.nextInt();
for(int j=0;j<20;j++){
int b=a>>j&1;
count[j][b]=(count[j][b]+i+1)%mod;
ans=(ans+(1L<<j)*count[j][b^1]%mod*(n-i))%mod;
}
}
System.out.println(ans*2%mod);
}
}
方法一：总体思路就是字符串哈希，每个节点向根节点方向幂次上升和下降各哈一次，可用倍增的方法进行，正反哈希值比较，核心算法时间复杂度O((n+q)*logn)
import java.util.*;
public class Main{
static int mod=(int)1e9+7,base=(int)1e9+9;
static long pow[]=new long[100005];
public static void main(String args[]){
pow[0]=1;
for(int i=1;i<=100000;i++){
pow[i]=pow[i-1]*base%mod;
}
Scanner sc=new Scanner(System.in);
int n=sc.nextInt(),p[][]=new int[n+5][17],level[]=new int[n+5];
long hash1[][]=new long[n+5][17],hash2[][]=new long[n+5][17];
String s=sc.next();
Arrays.fill(level,-1);
level[0]=0;
for(int i=1;i<=n;i++){
p[i][0]=sc.nextInt();
hash1[i][0]=hash2[i][0]=s.charAt(i-1);
}
for(int i=1;i<=n;i++){
//计算每个点跟0的距离
findLevel(i,p,level);
}
for(int i=1;i<17;i++){
for(int j=1;j<=n;j++){
//更新新祖先
if(level[j]-1>=(1<<i)){
p[j][i]=p[p[j][i-1]][i-1];
}
//更新哈希值
//hash1是本地为最低次幂，hash2是本地为最高最低次幂
if(level[j]>=(1<<i)){
hash1[j][i]=(hash1[j][i-1]+hash1[p[j][i-1]][i-1]*pow[1<<(i-1)])%mod;
hash2[j][i]=(hash2[j][i-1]*pow[1<<(i-1)]+hash2[p[j][i-1]][i-1])%mod;
}
}
}
int q=sc.nextInt();
for(int i=0;i<q;i++){
int u=sc.nextInt(),v=sc.nextInt(),lca=lca(u,v,p,level);
System.out.println(find(u,v,lca,level,p,hash1,hash2)==find(v,u,lca,level,p,hash1,hash2)?"YES":"NO");
}
}
static long find(int a,int b,int lca,int level[],int p[][],long hash1[][],long hash2[][]){
//寻找a到b的哈希值，其中a是低次幂
long ans=0;
for(int i=16,j=a;i>=0;i--){
if(level[j]-level[lca]+1>=(1<<i)){
ans=(ans+hash1[j][i]*pow[level[a]-level[j]])%mod;
j=p[j][i];
}
}
for(int i=16,j=b;i>=0;i--){
if(level[j]-level[lca]+1>=(1<<i)){
//b此时为1<<i次方，但是实际上为d=level[b]+level[a]-level[lca]*2
ans=(ans+hash2[j][i]*pow[level[j]+level[a]-level[lca]*2-(1<<i)+1])%mod;
j=p[j][i];
}
}
ans=(ans+mod-hash1[lca][0]*pow[level[a]-level[lca]]%mod)%mod;
return ans;
}
static int lca(int a,int b,int p[][],int level[]){
if(level[a]<level[b]){
return lca(b,a,p,level);
}
for(int i=16;i>=0;i--){
if(level[a]-level[b]>=(1<<i)){
a=p[a][i];
}
}
if(a!=b){
for(int i=16;i>=0;i--){
if(p[a][i]!=p[b][i]){
a=p[a][i];
b=p[b][i];
}
}
a=p[a][0];
}
return a;
}
static int findLevel(int a,int p[][],int level[]){
if(level[a]==-1){
level[a]=1+findLevel(p[a][0],p,level);
}
return level[a];
}
}
方法二：据说可以后缀数组，，未完待续吧。。。
京公网安备 11010502036488号