第一题在尝试了几个错误的dp后，意识到所有合法的序列可以抽象为选出一个子序列，并将他们拓展至长度为n的序列。为了避免记重，我们强制选择第一个出现的字符。于是，f[i][j]表示已经填了i个字符，现在正停留在原序列的第j个字符上，若是朴素转移，需要借助nxt[i][26]，即下一个字符的位置。而这件事显然可以用前缀和优化（画个图）。
但做题速度还是太慢了！花了1h才解决。
1 #include<bits/stdc++.h> 2 #define mod 1000000007 3 using namespace std; 4 typedef long long int ll; 5 const int maxn=8005; 6 int n,a[maxn],vis[26],pre[maxn][26]; 7 ll f[2][maxn],sum[maxn]; 8 inline void add(ll&x,ll y) 9 { 10 x=(x+y)%mod; 11 } 12 int main() 13 { 14 freopen("count1.in","r",stdin); 15 freopen("count1.out","w",stdout); 16 ios::sync_with_stdio(false); 17 cin>>n; 18 for(int i=1;i<=n;++i) 19 { 20 char ch; 21 cin>>ch; 22 a[i]=ch-'a'; 23 } 24 for(int i=1;i<=n;++i) 25 { 26 for(int j=0;j<26;++j) 27 pre[i][j]=pre[i-1][j]; 28 pre[i][a[i]]=i; 29 } 30 for(int i=1;i<=n;++i) 31 if(!vis[a[i]]) 32 { 33 vis[a[i]]=1; 34 f[1][i]=1; 35 } 36 for(int j=1;j<n;++j) 37 { 38 int p=j&1; 39 int q=p^1; 40 memset(f[q],0,sizeof(f[q])); 41 for(int i=1;i<=n;++i) 42 sum[i]=sum[i-1]+f[p][i]; 43 for(int i=1;i<=n;++i) 44 add(f[q][i],sum[i]-sum[pre[i-1][a[i]]]); 45 } 46 ll ans=0; 47 int p=n&1; 48 for(int i=1;i<=n;++i) 49 add(ans,f[p][i]); 50 cout<<(ans%mod+mod)%mod<<endl; 51 return 0; 52 }
第二题实质上是维护$sum_{i=1}^{n}{L_i*M_i*R_i}$，支持对每一个变量进行加法或赋值。虽然题解上有更好（指代码长度短）的做法，但是线段树是相当好写的。花了1h解决。
1 #include<bits/stdc++.h> 2 #define mod 1000000007 3 using namespace std; 4 typedef long long int ll; 5 const int maxn=1E5+5; 6 inline int read() 7 { 8 char ch=getchar(); 9 while(!isdigit(ch))ch=getchar(); 10 int s=ch-'0';ch=getchar(); 11 while(isdigit(ch)){s=s*10+ch-'0';ch=getchar();} 12 return s; 13 } 14 int G[55]; 15 inline void write(ll x) 16 { 17 int g=0; 18 do{G[++g]=x%10;x/=10;}while(x); 19 for(int i=g;i>=1;--i)putchar(G[i]+'0');putchar(' '); 20 } 21 struct SEG 22 { 23 int n; 24 ll*mlr,*lr,*ml,*mr,*m,*tl,*tr; 25 ll*aM,*aL,*aR,*bL,*bR; 26 ll*tagX,*tagY; 27 bool*ok; 28 inline void pushup(int num) 29 { 30 mlr[num]=(mlr[num<<1]+mlr[num<<1|1])%mod; 31 ml[num]=(ml[num<<1]+ml[num<<1|1])%mod; 32 mr[num]=(mr[num<<1]+mr[num<<1|1])%mod; 33 lr[num]=(lr[num<<1]+lr[num<<1|1])%mod; 34 m[num]=(m[num<<1]+m[num<<1|1])%mod; 35 tl[num]=(tl[num<<1]+tl[num<<1|1])%mod; 36 tr[num]=(tr[num<<1]+tr[num<<1|1])%mod; 37 } 38 void build(int l,int r,int num) 39 { 40 tagX[num]=tagY[num]=0; 41 if(l==r) 42 { 43 mlr[num]=aM[l]*aR[l]%mod*aL[l]%mod; 44 ml[num]=aM[l]*aL[l]%mod; 45 mr[num]=aM[l]*aR[l]%mod; 46 lr[num]=aM[l]*aR[l]%mod; 47 m[num]=aM[l]; 48 tl[num]=aL[l]; 49 tr[num]=aR[l]; 50 return; 51 } 52 int mid=(l+r)>>1; 53 build(l,mid,num<<1),build(mid+1,r,num<<1|1); 54 pushup(num); 55 } 56 inline void init(int N,ll*M,ll*L,ll*R) 57 { 58 n=N; 59 aM=new ll[n+1]; 60 aL=new ll[n+1]; 61 aR=new ll[n+1]; 62 bL=new ll[n+1]; 63 bR=new ll[n+1]; 64 for(int i=1;i<=n;++i) 65 { 66 bL[i]=L[i],bR[i]=R[i]; 67 aM[i]=M[i]; 68 } 69 aL[1]=bL[1]; 70 for(int i=2;i<=n;++i) 71 aL[i]=(aL[i-1]+bL[i])%mod; 72 aR[n]=bR[n]; 73 for(int i=n-1;i>=1;--i) 74 aR[i]=(aR[i+1]+bR[i])%mod; 75 for(int i=1;i<=n;++i) 76 aL[i]=(aL[i]-bL[i]+mod)%mod,aR[i]=(aR[i]-bR[i]+mod)%mod; 77 mlr=new ll[(n+1)*4]; 78 ml=new ll[(n+1)*4]; 79 mr=new ll[(n+1)*4]; 80 lr=new ll[(n+1)*4]; 81 m=new ll[(n+1)*4]; 82 tl=new ll[(n+1)*4]; 83 tr=new ll[(n+1)*4]; 84 tagX=new ll[(n+1)*4]; 85 tagY=new ll[(n+1)*4]; 86 ok=new bool[n+1]; 87 for(int i=1;i<=n;++i) 88 ok[i]=1; 89 build(1,n,1); 90 } 91 inline void putX(int num,ll x,ll l,ll r) 92 { 93 tagX[num]=(tagX[num]+x)%mod; 94 mlr[num]=(mlr[num]+mr[num]*x)%mod; 95 ml[num]=(ml[num]+m[num]*x)%mod; 96 lr[num]=(lr[num]+tr[num]*x)%mod; 97 tl[num]=(tl[num]+(r-l+1)*x)%mod; 98 } 99 inline void putY(int num,ll x,ll l,ll r) 100 { 101 tagY[num]=(tagY[num]+x)%mod; 102 mlr[num]=(mlr[num]+ml[num]*x)%mod; 103 mr[num]=(mr[num]+m[num]*x)%mod; 104 lr[num]=(lr[num]+tl[num]*x)%mod; 105 tr[num]=(tr[num]+(r-l+1)*x)%mod; 106 } 107 inline void pushdown(int num,int l,int r) 108 { 109 int mid=(l+r)>>1; 110 if(tagX[num]) 111 { 112 ll x=tagX[num]; 113 tagX[num]=0; 114 putX(num<<1,x,l,mid),putX(num<<1|1,x,mid+1,r); 115 } 116 if(tagY[num]) 117 { 118 ll x=tagY[num]; 119 tagY[num]=0; 120 putY(num<<1,x,l,mid),putY(num<<1|1,x,mid+1,r); 121 } 122 } 123 void addX(int L,int R,int l,int r,ll x,int num) 124 { 125 if(L<=l&&r<=R) 126 { 127 putX(num,x,l,r); 128 return; 129 } 130 pushdown(num,l,r); 131 int mid=(l+r)>>1; 132 if(L<=mid) 133 addX(L,R,l,mid,x,num<<1); 134 if(mid<R) 135 addX(L,R,mid+1,r,x,num<<1|1); 136 pushup(num); 137 } 138 void addY(int L,int R,int l,int r,ll x,int num) 139 { 140 if(L<=l&&r<=R) 141 { 142 putY(num,x,l,r); 143 return; 144 } 145 pushdown(num,l,r); 146 int mid=(l+r)>>1; 147 if(L<=mid) 148 149 addY(L,R,l,mid,x,num<<1); 150 if(mid<R) 151 addY(L,R,mid+1,r,x,num<<1|1); 152 pushup(num); 153 } 154 void changePos(int l,int r,int pos,ll x,int num) 155 { 156 if(l==r) 157 { 158 mlr[num]=x*tl[num]%mod*tr[num]%mod; 159 ml[num]=x*tl[num]%mod; 160 mr[num]=x*tr[num]%mod; 161 m[num]=x; 162 return; 163 } 164 pushdown(num,l,r); 165 int mid=(l+r)>>1; 166 if(pos<=mid) 167 changePos(l,mid,pos,x,num<<1); 168 else 169 changePos(mid+1,r,pos,x,num<<1|1); 170 pushup(num); 171 } 172 inline void change0(int pos) 173 { 174 assert(1<=pos&&pos<=n); 175 if(ok[pos]==0) 176 return; 177 addX(pos,n,1,n,-bL[pos],1); 178 addY(1,pos,1,n,-bR[pos],1); 179 changePos(1,n,pos,0,1); 180 ok[pos]=0; 181 } 182 inline void change1(int pos) 183 { 184 assert(1<=pos&&pos<=n); 185 if(ok[pos]==1) 186 return; 187 addX(pos,n,1,n,bL[pos],1); 188 addY(1,pos,1,n,bR[pos],1); 189 changePos(1,n,pos,aM[pos],1); 190 ok[pos]=1; 191 } 192 }T[maxn]; 193 int n,tot,a[maxn],tmp[maxn]; 194 namespace BIT 195 { 196 ll t[maxn]; 197 inline int lowbit(int x) 198 { 199 return x&(-x); 200 } 201 inline void add(int x,int y) 202 { 203 while(x<=n) 204 { 205 t[x]+=y; 206 x+=lowbit(x); 207 } 208 } 209 inline ll ask(int x) 210 { 211 ll s=0; 212 while(x) 213 { 214 s+=t[x]; 215 x-=lowbit(x); 216 } 217 return s; 218 } 219 inline void clear() 220 { 221 memset(t,0,sizeof(t)); 222 } 223 } 224 int where[maxn]; 225 ll bM[maxn],bL[maxn],bR[maxn]; 226 vector<int>waitL[maxn],waitR[maxn],P[maxn]; 227 inline void init() 228 { 229 sort(tmp+1,tmp+tot+1); 230 tot=unique(tmp+1,tmp+tot+1)-tmp-1; 231 for(int i=1;i<=n;++i) 232 a[i]=lower_bound(tmp+1,tmp+tot+1,a[i])-tmp; 233 for(int i=1;i<=n;++i) 234 { 235 bL[i]=BIT::ask(a[i]); 236 BIT::add(a[i],1); 237 } 238 BIT::clear(); 239 for(int i=n;i>=1;--i) 240 { 241 bR[i]=BIT::ask(a[i]); 242 BIT::add(a[i],1); 243 } 244 for(int i=1;i<=n;++i) 245 bM[i]=1; 246 for(int i=1;i<=n;++i) 247 { 248 waitL[a[i]].push_back(bL[i]); 249 waitR[a[i]].push_back(bR[i]); 250 P[a[i]].push_back(i); 251 } 252 for(int i=1;i<=tot;++i) 253 { 254 int m=waitL[i].size(); 255 for(int j=1;j<=m;++j) 256 { 257 bL[j]=waitL[i][j-1],bR[j]=waitR[i][j-1]; 258 where[P[i][j-1]]=j; 259 } 260 T[i].init(m,bM,bL,bR); 261 } 262 } 263 inline void solve() 264 { 265 int q=read(); 266 ll ans=0; 267 for(int i=1;i<=tot;++i) 268 ans=(ans+T[i].mlr[1])%mod; 269 while(q--) 270 { 271 int type=read(),pos=read(); 272 if(type==1) 273 { 274 ll x=T[a[pos]].mlr[1]; 275 T[a[pos]].change0(where[pos]); 276 ll y=T[a[pos]].mlr[1]; 277 ans=(ans-x+y)%mod; 278 } 279 else 280 { 281 ll x=T[a[pos]].mlr[1]; 282 T[a[pos]].change1(where[pos]); 283 ll y=T[a[pos]].mlr[1]; 284 ans=(ans-x+y)%mod; 285 } 286 write((ans%mod+mod)%mod); 287 } 288 } 289 int main() 290 { 291 freopen("count2.in","r",stdin); 292 freopen("count2.out","w",stdout); 293 ios::sync_with_stdio(false); 294 n=read(); 295 for(int i=1;i<=n;++i) 296 { 297 a[i]=read(); 298 tmp[++tot]=a[i]; 299 } 300 init(); 301 solve(); 302 return 0; 303 }
第三题乍看没有任何思路，但某些部分分启示我们每个点出边的选取有“独立性”。在不到5min的观察后，便获得了结论。 这里还要感谢czy给我莫大的帮助！（因为他一直在写这道题，虽然最后挂了）
1 #include<bits/stdc++.h> 2 #define mod 1000000007 3 using namespace std; 4 typedef long long int ll; 5 const int maxn=5E5+5; 6 int n,a[maxn],b[maxn],deg[maxn]; 7 int p[maxn],EE[maxn][2]; 8 ll fac[maxn]; 9 map<ll,bool>vis; 10 inline int read() 11 { 12 char ch=getchar(); 13 while(!isdigit(ch))ch=getchar(); 14 int s=ch-'0';ch=getchar(); 15 while(isdigit(ch)){s=s*10+ch-'0';ch=getchar();} 16 return s; 17 } 18 inline void init() 19 { 20 fac[0]=1; 21 for(int i=1;i<=n;++i) 22 fac[i]=fac[i-1]*i%mod; 23 } 24 namespace work0 25 { 26 inline void main() 27 { 28 ll s=1; 29 for(int i=1;i<=n;++i) 30 s=s*fac[deg[i]]%mod; 31 cout<<s<<endl; 32 } 33 } 34 namespace work1 35 { 36 int size,head[maxn]; 37 struct edge 38 { 39 int to,next; 40 }E[maxn*2]; 41 inline void add(int u,int v) 42 { 43 E[++size].to=v; 44 E[size].next=head[u]; 45 head[u]=size; 46 } 47 int fa[maxn],dep[maxn]; 48 inline void get(int u,int v) 49 { 50 while(u!=v) 51 { 52 if(dep[u]<dep[v]) 53 swap(u,v); 54 --deg[u]; 55 u=fa[u]; 56 } 57 --deg[u]; 58 } 59 void dfs(int u,int F,int d) 60 { 61 fa[u]=F; 62 dep[u]=d; 63 for(int i=head[u];i;i=E[i].next) 64 { 65 int v=E[i].to; 66 if(v==F) 67 continue; 68 dfs(v,u,d+1); 69 } 70 } 71 inline void main() 72 { 73 for(int i=1;i<=n-1;++i) 74 add(EE[i][0],EE[i][1]),add(EE[i][1],EE[i][0]); 75 dfs(1,0,0); 76 for(int i=1;i<=n;++i) 77 if(a[i]!=0) 78 get(i,a[i]); 79 ll s=1; 80 for(int i=1;i<=n;++i) 81 if(deg[i]>=0) 82 s=s*fac[deg[i]]%mod; 83 cout<<s<<endl; 84 } 85 } 86 int main() 87 { 88 freopen("count3.in","r",stdin); 89 freopen("count3.out","w",stdout); 90 ios::sync_with_stdio(false); 91 n=read(); 92 init(); 93 for(int i=1;i<=n-1;++i) 94 { 95 EE[i][0]=read(),EE[i][1]=read(); 96 ++deg[EE[i][0]]; 97 ++deg[EE[i][1]]; 98 } 99 for(int i=1;i<=n-1;++i) 100 p[i]=i; 101 bool f=1; 102 for(int i=1;i<=n;++i) 103 { 104 a[i]=read(); 105 if(a[i]!=0) 106 f=0; 107 } 108 if(f) 109 { 110 work0::main(); 111 return 0; 112 } 113 if(n>11) 114 { 115 work1::main(); 116 return 0; 117 } 118 int ans=0; 119 do 120 { 121 for(int i=1;i<=n;++i) 122 b[i]=i; 123 for(int i=1;i<=n-1;++i) 124 swap(b[EE[p[i]][0]],b[EE[p[i]][1]]); 125 ll s=0; 126 for(int i=1;i<=n;++i) 127 if(a[i]!=0&&a[i]!=b[i]) 128 goto end; 129 for(int i=1;i<=n;++i) 130 s=s*10+b[i]; 131 if(!vis[s]) 132 { 133 ++ans; 134 vis[s]=1; 135 } 136 end:; 137 }while(next_permutation(p+1,p+n)); 138 cout<<ans<<endl; 139 return 0; 140 }