生成魔咒
/* 后缀数组+双向链表 参照：https://blog.csdn.net/clove_unique/article/details/53911757 */ #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=1e5+5; int n,cnt,c[N],ans[N],s[N],t[N],rank[N],trank[N],sa[N],tsa[N],h[N],nxt[N],pre[N]; long long res; void DA(){ int p,maxx=cnt; memset(c,0,sizeof c); for(int i=1;i<=n;i++) c[rank[i]=s[i]]++; for(int i=1;i<=maxx;i++) c[i]+=c[i-1]; for(int i=n;i;i--) sa[c[rank[i]]--]=i; trank[sa[1]]=p=1; for(int i=2;i<=n;i++){ if(rank[sa[i]]!=rank[sa[i-1]]) p++; trank[sa[i]]=p; } for(int i=1;i<=n;i++) rank[i]=trank[i]; for(int k=1;p<n;k<<=1,maxx=p){ p=0; for(int i=n-k+1;i<=n;i++) tsa[++p]=i; for(int i=1;i<=n;i++) if(sa[i]>k) tsa[++p]=sa[i]-k; memset(c,0,sizeof c); for(int i=1;i<=n;i++) trank[i]=rank[tsa[i]]; for(int i=1;i<=n;i++) c[trank[i]]++; for(int i=1;i<=maxx;i++) c[i]+=c[i-1]; for(int i=n;i;i--) sa[c[trank[i]]--]=tsa[i]; trank[sa[1]]=p=1; for(int i=2;i<=n;i++){ if(rank[sa[i]]!=rank[sa[i-1]]||rank[sa[i]+k]!=rank[sa[i-1]+k]) p++; trank[sa[i]]=p; } for(int i=1;i<=n;i++) rank[i]=trank[i]; } for(int i=1,k=0;i<=n;i++){ int j=sa[rank[i]-1]; while(s[i+k]==s[j+k]) k++; h[rank[i]]=k;if(k>0) k--; } } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&s[i]),t[i]=s[i]; for(int i=1;i<=n/2;i++) swap(s[i],s[n-i+1]); sort(t+1,t+n+1); cnt=unique(t+1,t+n+1)-(t+1); for(int i=1;i<=n;i++) s[i]=lower_bound(t+1,t+cnt+1,s[i])-t; DA(); for(int i=1;i<=n;i++){ nxt[i]=i+1; pre[i]=i-1; } for(int i=1;i<=n;i++){ int k=rank[i]; ans[i]=n-i+1-max(h[k],h[nxt[k]]); h[nxt[k]]=min(h[k],h[nxt[k]]); nxt[pre[k]]=nxt[k]; pre[nxt[k]]=pre[k]; } for(int i=n;i;i--){ res+=ans[i]; printf("%lld ",res); } return 0; }
排列计数
/* ans=C(n,m)*dp(n-m);|dp(i)表示i的错排数 */ #include<cstdio> using namespace std; typedef long long ll; inline ll read(){ ll x=0;char ch=getchar(); while(ch<'0'||ch>'9'){ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; } #define FRE(name) freopen(#name".in","r",stdin);freopen(#name".out","w",stdout); #define fre(name) freopen(#name".txt","r",stdin); #ifdef WIN32 #define LL "%I64d" #else #define LL "%lld" #endif const ll S=1e6; const ll N=S+5; const ll mod=1e9+7; ll cas,n,m,ans,dp[N],fz[N],fm[N]; ll fpow(ll a,ll p){ ll res=1; for(;p;p>>=1,a=a*a%mod) if(p&1) res=res*a%mod; return res; } void first(){ dp[0]=1;dp[1]=0; fz[1]=fz[0]=fm[1]=fm[0]=1; for(ll i=2;i<=S;i++) dp[i]=(i*dp[i-1]%mod+((i&1)?-1:1)+mod)%mod; for(ll i=2;i<=S;i++) fz[i]=fz[i-1]*i%mod; fm[S]=fpow(fz[S],mod-2); for(ll i=S-1;i>=1;i--) fm[i]=fm[i+1]*(i+1)%mod; } void solve(){ for(cas=read();cas--;){ n=read();m=read(); ans=(((fz[n]*fm[m])%mod*fm[n-m])%mod*dp[n-m])%mod; printf(LL " ",ans); } } int main(){ //FRE(permutation); first(); solve(); return 0; }
征途
/* ans=m(x_1^2+X_2^2+……+x_m^2)-(x_1+X_2+……+x_m)^2 令dp[i][j]表示前i个数已经选择到了x_j的最小值；这样就变成了一个区间dp 我懒，就不写单调队列优化了 */ #include<cstdio> #include<cstring> using namespace std; typedef long long ll; #define pf(x) ((x)*(x)) #define fro __attribute__((optimize("O2"))) #define FRE(name) freopen(#name".in","r",stdin);freopen(#name".out","w",stdout); #define fre(name) freopen(#name".txt","r",stdin); #ifdef WIN32 #define LL "%I64d" #else #define LL "%lld" #endif const int N=3005; int n,m,a[N],p[N][N]; ll ans,sum[N],dp[N][N]; fro int main(){ //FRE(journey); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]),sum[i]=sum[i-1]+a[i]; memset(dp,0x3f3f3f3f,sizeof dp); dp[0][0]=0; for(int j=1;j<=m;j++){ for(int i=j;i<=n;i++){ for(int k=p[i-1][j];k<i;k++){ if(dp[i][j]>dp[k][j-1]+pf(sum[i]-sum[k])){ dp[i][j]=dp[k][j-1]+pf(sum[i]-sum[k]); p[i][j]=k; } } } } ans=dp[n][m]*(ll)m-pf(sum[n]); printf(LL,ans); return 0; }