10.13

· · 个人记录

今天我发现我记不清比赛编号了。

T1 数数

好像是什么国赛模拟赛T3

T2 Palindrome（回文）

这个题感觉是全场最可做的一道，思想也很好。

赛时感觉暴力不好打跳了，完全没想到正解的方向(

考虑两个给定的，字母构成一样的序列怎么相互转化：给一个串编好号，然后把号对应到另一个串，找新对应的编号序列里逆序对的个数。

所以我们考虑先找到一个回文串。直接将出现偶数的并到两边，奇数的放在中间，然后按照上面的方式找逆序对。

树状数组求逆序对确实方便奥。倒着枚举，直接在数的位置加一，查的时候直接查小的就好了。

#include<bits/stdc++.h>
typedef int count ;
typedef long long value ;
inline value read(){
    count f(1);
    value x(0);
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
    for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);
    return f*x;
}
void write(value x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
#define debug(x) std::cout<<"###"<<x<<std::endl;

#define maxn 1000010
#define tar a[b[get(j)]]
count n;
value cnt[30],p[maxn],now[maxn],a[maxn],b[maxn],c[maxn],g=1,ans=0;
std::vector<count> v[30];
value f[maxn];
char s[maxn];
#define lb(x) (x&(-x))
void add(count x){
    while(x<=n){
        c[x]++; 
        x+=lb(x);
    } 
}
value find(count x){
    value val=0; 
    while(x>0){
        val+=c[x]; 
        x-=lb(x);
    }
    return val;
}
count get(count x){
    return (n&1)?(2*(n/2+1)-x):(1+n-x);
}

int main(){
    scanf("%s",s+1); 
    n=strlen(s+1);

    for(count i=1;i<=n;i++){
        a[i]=s[i]-'a'+1; 
        cnt[a[i]]++; 
        v[a[i]].emplace_back(i);
        now[i]=cnt[a[i]];
    }

    for(count i=1;i<=26;i++){
        if(cnt[i]&1) {
            b[n/2+1]=v[i][v[i].size()/2];
        }
        f[i]=(cnt[i]-1)/2+1;
    }

    for(count i=1;i<=n/2;i++){
        while(now[g]>cnt[a[g]]/2) {
            g++;
        }
        b[i]=g; 
        g++;
    }

    for(count j=n-n/2+1;j<=n;j++){
        b[j]=v[tar][f[tar]];
        f[tar]++; 
    }

    for(count i=n;i>=1;i--){
        ans+=find(b[i]);
        add(b[i]);
    }

    write(ans),putchar('\n');
    return 0;
}

T3 Permutation

好题。

赛时基本上做了一场比赛(

一直以为是容斥，好吧不是。据Meteor_说，容斥一定要到一定地步才能看出来是容斥，（原来上次单纯是我没推到那个地步啊，诶不对，不是题解一上来就整了个容斥式子吗，令人深省）但是我觉得还是看到有去重就想想容斥罢。

还有，别在一棵树上吊死。很多题做法根本不难，如果你钻进牛角尖感觉不行，趁早换换思路吧。真不是说，就这种赛时把题想得这么复杂的情况没一个是押对的(

这个题是dp(

思路很好。

我们有 f_i 表示放完了 [1,i] 的方案数。能得出来转移方程 f_i=\sum f_j

这个 j 是有限制的。因为整个序列大概结构如图：

发现 i+1 和 j 相邻，然后一定要满足 (i+1)\%j \le 2。

这样枚举 i,j 有 n^2 的做法

发现若满足这个转移条件，一定有 i-1,i,i+1 之中有 j 的倍数，这时候就直接枚举倍数就好了，这是 n\log n。

#include<bits/stdc++.h>
typedef int count ;
typedef long long value ;
inline value read(){
    count f(1);
    value x(0);
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
    for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);
    return f*x;
}
void write(value x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
#define debug(x) std::cout<<"###"<<x<<std::endl;

#define mod 998244353
#define maxn 1000010 
count n;
value f[maxn];

int main(){
    n=read();
    if(n==1) {
        write(1),putchar('\n');
        return 0;
    }
    if(n==2){
        write(2),putchar('\n');
        return 0;
    }

    f[3]=1;
    for(count j=3;j<n;j++){
        for(count i=j;i<=n;i+=j){
            if(j!=i){
                f[i]=(f[i]+f[j])%mod;
            }
            f[i-1]=(f[i-1]+f[j])%mod;
            f[i+1]=(f[i+1]+f[j])%mod;
        }
    }

    f[n]=1;
    for(count i=3;i<n;i++){
        f[n]=(f[n]+f[i])%mod;
    } 

    write(f[n]*n%mod*2%mod),putchar('\n');
    return 0;
}