D. Guess the Permutation 2000 逆序性质 二分
https://codeforces.com/contest/1589/problem/D
题解:首先我们可以二分查找i的位置:当1->x逆序对>0,则在i右,否则在左,log(n)次询问。找到i的位置后,我们发现逆序对有如下性质,i->j-1的数量和i+1->j-1的数量差为j-1-i,故我们可以询问i+1->n,i->n的值得到j的位置,同理询问j->n的值和j+1->n的值得到k,总询问为32+2+2<40。
D. Hossam and (sub-)palindromic tree 2100 gq! dp,树
https://codeforces.com/problemset/problem/1771/D
题解:这种回文串且在树上,显然可以转移。如何转移?我们可以拓展回文串的两侧,我们令to(u,v)为u—>v路径上距离u为1的点,那么当s[u]!=s[v]时f(u,v)=max(f(to(u,v),v),f(u,to(v,u))),当s[u]==s[v]时,ans=max(ans,f(to(u,v),to(v,u))+2)。这样可以得到最长答案,我们只需预处理f(u,u)=0,和距离为1的u,v,将剩下的点对按照距离排序后遍历,即可得到ans。to数组的处理可以以u为根,对于其每个子节点的儿子,其to[u,v]=it。
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N=3e3+10;
int d[N][N],f[N][N],go[N][N];
char s[N];
vector<int> g[N];
vector<pair<int,int> > e;
void dfs(int x,int fa,int w,int u){
d[u][x]=d[u][fa]+1;
for(auto it:g[x]){
if(it==fa) continue;
go[u][it]=w;
dfs(it,x,w,u);
}
}
bool cmp(pair<int,int> x,pair<int,int> y){
auto [u1,v1]=x;
auto [u2,v2]=y;
return d[u1][v1]<d[u2][v2];
}
void solve(){
int n;cin>>n;
int ans=1;
string ss;cin>>ss;
for(int i=1;i<=n;i++){
g[i].clear();
s[i]=ss[i-1];
}
for(int i=1;i<n;i++){
int u,v;cin>>u>>v;
g[u].pb(v);g[v].pb(u);
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
f[i][j]=0;
d[i][j]=0;
go[i][j]=0;
}
}
for(int i=1;i<=n;i++){
f[i][i]=1;
d[i][i]=0;
for(auto it:g[i]){
if(s[it]==s[i]){
f[i][it]=f[it][i]=2;
}
else f[i][it]=f[it][i]=1;
ans=max(ans,f[i][it]);
}
}
for(int i=1;i<=n;i++){
for(auto it:g[i]){
d[i][it]=1;
dfs(it,i,it,i);
}
}
e.clear();
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
if(d[i][j]<=1) continue;
e.pb({i,j});
}
}
sort(e.begin(),e.end(),cmp);
for(auto it:e){
auto [u,v]=it;
f[u][v]=max({f[u][v],f[go[u][v]][v],f[u][go[v][u]]});
if(s[u]==s[v]) f[u][v]=max(f[go[u][v]][go[v][u]]+2,f[u][v]);
f[v][u]=f[u][v];ans=max(ans,f[u][v]);
// cout<<u<<" "<<v<<" "<<d[u][v]<<" "<<f[u][v]<<endl;
}
cout<<ans<<endl;
}
signed main(){
int T;cin>>T;
while(T--) solve();
}
···
## Tyler and Strings 1900
https://codeforces.com/problemset/problem/1648/C
题解:我们可以枚举第一个比b小的位置,由多重排列公式,每次用一个比b[i]小的数相当于乘上一个系数(该数数量),那么我们可以维护比b[i]小的所有数的数量并求其和,树状数组很容易做到,复杂度nlogn。具体细节见代码:
include<bits/stdc++.h>
define int long long
using namespace std;
const int N=2e5+10,mod=998244353;
int a[N],b[N],c[N],fac[N],s[N],v[N];
void add(int x,int k){
for(;x<=2e5;x+=x&-x) c[x]=(c[x]+k)%mod;
}
int ask(int x){
int res=0;
for(;x;x-=x&-x) res=(res+c[x])%mod;
return res;
}
void init(int n){
fac[0]=1;
for(int i=1;i<=n;i++) fac[i]=fac[i-1]i%mod;
}
int qpow(int x,int y){
int res=1;
while(y){
if(y&1) res=resx%mod;
x=xx%mod;
y>>=1;
}
return res;
}
int inv(int x){
return qpow(x,mod-2);
}
signed main(){
int n,m;cin>>n>>m;
init(200005);
for(int i=1;i<=n;i++) cin>>a[i],v[a[i]]++,s[a[i]]++;
for(int j=1;j<=m;j++) cin>>b[j];
int mul=1;
for(int i=1;i<=n;i++){
add(a[i],v[a[i]]);
mul=mulfac[v[a[i]]]%mod;
v[a[i]]=0;
}
int ans=0;
for(int i=1;i<=min(n,m);i++){
int w=fac[n-i];
w=winv(mul)%mod;
int p=ask(b[i]-1);
w=wp%mod;
ans=(ans+w)%mod;
int sum=ask(b[i])-ask(b[i]-1);
mul=mulinv(fac[sum])%modfac[sum-1]%mod;
add(b[i],-1);
}
if(n<m){
int ok=1;
for(int i=1;i<=n;i++){
if(!s[b[i]]) ok=0;
else s[b[i]]--;
}
if(ok) ans=(ans+1)%mod;
}
cout<<ans<<endl;
}
标签:res,int,题解,CF,ans,fac,mod
From: https://www.cnblogs.com/wjhqwq/p/17327603.html