本文共 4217 字，大约阅读时间需要 14 分钟。
#include #include #include #include #include #include #include #include #include #include #include #define ll long long#define maxn 4001000#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define rep(i,a,b) for(int i=a;i<=b;i++)using namespace std;ll dp[1010100][5];char s[1010100];int l,d,pre[100];ll rd(){ ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}void init(){ scanf("%s",s);}void work(){ l=strlen(s); dp[0][0]=1; rep(i,1,l) { dp[i][0]=1; d=pre[s[i-1]-'a']; pre[s[i-1]-'a']=i; rep(j,1,3) { dp[i][j]=dp[i-1][j-1]+dp[i-1][j]; if(d&&(j-(i-d)>=0)) dp[i][j]-=dp[d-1][j-(i-d)]; } } printf("%lld\n",dp[l][0]+dp[l][1]+dp[l][2]+dp[l][3]);}int main(){ init(); work();}
#include #include #include #include #include #include #include #include #include #include #include #define ll long long#define maxn 4001000#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define rep(i,a,b) for(int i=a;i<=b;i++)using namespace std;const int P=998244353;int n,k,len,cnt[101000][110],f[101000][110],s[101000],a[101000];ll rd(){ ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}void init(){ n=rd();k=rd();len=rd(); rep(i,1,n) a[i]=rd(); s[0]=1; rep(i,1,k) rep(j,1,n) cnt[j][i]=cnt[j-1][i]+(a[j]==i||a[j]==-1?1:0);}void work(){ memset(f,0,sizeof(f)); rep(i,1,n) { rep(j,1,k) { if(a[i]!=-1&&a[i]!=j) continue; f[i][j]=s[i-1]; if(i>=len&&cnt[i][j]-cnt[i-len][j]==len) { f[i][j]=(f[i][j]-s[i-len]+f[i-len][j])%P; f[i][j]=(f[i][j]+P)%P; } } rep(j,1,k) s[i]=(s[i]+f[i][j])%P; } printf("%d\n",s[n]);}int main(){ init(); work();}
#include #include #include #include #include #include #include #include #include #include #include #define ll long long#define maxn 4001000#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define rep(i,a,b) for(int i=a;i<=b;i++)const ll P=1e9+7;using namespace std;ll n,m,k,f[1010000][4];ll calc(ll m,ll k){ f[0][0]=1;f[0][1]=f[0][2]=0; for(int i=1;i<=n;i++) { ll sum=(f[i-1][0]+f[i-1][1]+f[i-1][2]) %P; f[i][2]=sum; if(i<=m) f[i][0]=sum; else if(i==m+1) f[i][0]=(sum-1)%P; else f[i][0]=(sum-f[i-m-1][1]-f[i-m-1][2])%P; if(i<=k) f[i][1]=sum; else if(i==k+1) f[i][1]=(sum-1)%P; else f[i][1]=(sum-f[i-k-1][0]-f[i-k-1][2])%P; } return (f[n][0]+f[n][1]+f[n][2])%P;}int main(){ while(scanf("%lld%lld%lld",&n,&m,&k)!=EOF) { printf("%lld\n",((calc(n,k)-calc(m-1,k))%P+P)%P); }}
#include #include #include #include #include #include #include #include #include #include #define ll long long#define maxn 4001000#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define rep(i,a,b) for(int i=a;i<=b;i++)using namespace std;int n,x,cnt[101010],s[101010],a[101010];ll f[101010];vector q[101010];ll rd(){ ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}ll cal(int x,int y){ return f[x-1]+1ll*a[x]*y*y;}int solve(int x,int y){ int l=1,r=n,ret=n+1; while(l<=r){ int mid=l+r>>1; if(cal(x,mid-s[x]+1)>=cal(y,mid-s[y]+1)){ ret=mid; r=mid-1; } else l=mid+1; } return ret;}void init(){ n=rd();}void work(){ rep(i,1,n) { x=rd();a[i]=x; s[i]=++cnt[x]; while(q[x].size()>=2&&solve(q[x][q[x].size()-2],q[x][q[x].size()-1])<=solve(q[x][q[x].size()-1],i)) q[x].pop_back(); q[x].push_back(i); while(q[x].size()>=2&&solve(q[x][q[x].size()-2],q[x][q[x].size()-1])<=s[i]) q[x].pop_back(); f[i]=cal(q[x][q[x].size()-1],s[i]-s[q[x][q[x].size()-1]]+1); } printf("%lld\n",f[n]);}int main(){ init(); work();}
转载于:https://www.cnblogs.com/The-Pines-of-Star/p/10587138.html
