A.数数
不会。
暴力 dp 10pts。
好像数据有些水，直接输出 \(\prod (b_i-c+1)\) 能得 30pts /yiw。
B.Palindrome
设原串为 \(a\)，最终形成的回文串为 \(b\)。最后显然是求 \(a\) 关于 \(b\) 的逆序对个数。
我们需要构造 \(b\) 串，使得逆序对的个数最小化。
考虑一种贪心的构造，从前往后扫 \(a\) 串，将这个位置上的字母直接放到首尾，若只剩下一个字母，那么肯定放中间。
然后树状数组求逆序对就好了，时间复杂度 \(O(n\log n)\)。
赛时差点被卡常了，本机测极限样例跑了 0.8s，还好交上去没挂。
点击查看代码
#include<bits/stdc++.h>
using ll=long long;
std::string s;
int n,a[1000005],b[1000005],c[1000005],cnt[1000005],mp[26],tot1;
inline int change(char ch){
if(!mp[ch-'a']){mp[ch-'a']=++tot1;return tot1;}
return mp[ch-'a'];
}
struct FenwickTree{
int c[1000005];
inline void modify(int x,int v){for(;x<=n;x+=x&-x)c[x]+=v;}
inline int query(int x){int sum=0;for(;x;x-=x&-x)sum+=c[x];return sum;}
}t;
std::map<std::pair<int,int>,int> f;
int main(){
std::cin.tie(nullptr)->sync_with_stdio(false);
std::cin>>s;n=s.size();
for(int i=0;i<n;++i)a[i+1]=change(s[i]);
for(int i=1;i<=n;++i)cnt[a[i]]++;
int mid=(n+1)>>1;
for(int l=1,r=n,i=1;i<=n;++i){
if(!cnt[a[i]])continue;
if(cnt[a[i]]>1){
b[l]=a[i];l++;
b[r]=a[i];r--;
cnt[a[i]]-=2;
continue;
}
b[mid]=a[i];cnt[a[i]]--;
}
for(int i=1;i<=n;++i){
cnt[b[i]]++;
f[{b[i],cnt[b[i]]}]=i;
}
for(int i=1;i<=n;++i)cnt[b[i]]=0;
for(int i=1;i<=n;++i){
cnt[a[i]]++;
a[i]=f[{a[i],cnt[a[i]]}];
}
ll ans(0);
for(int i=n;i;--i){
t.modify(a[i],1);
ans+=t.query(a[i]-1);
}
std::cout<<ans;
return 0;
}
C.Permutation
因为 \(p_i \mod p_{i+1} \le 2\)，所以若 \(p_i<p_{i+1}\)，\(p_i\) 必定为 \(1\) 或 \(2\)。
我们把序列从 \(1\) 和 \(2\) 的位置断开，一定会得到两个单调递减的序列。
考虑直接 dp。设 \(f_i\) 为已经填了 \([1,i]\) 这 \(i\) 个数。
转移的话枚举一个 \(j\)，让 \((j,i]\) 作为同一个段接在后面。那么 \(j\) 和 \(i+1\) 则在另一个段中相邻，需要满足 \(i+1\mod j \le 2\)。
答案就是 \(f_n\)，因为是环，可以循环移位，所以还要乘 \(n\)。
这样直接枚举 \(i,j\) 是 \(O(n^2)\) 的。
因为 \(i+1\mod j \le 2\) 只有 \(0,1,2\) 三种情况，所以可以枚举 \(j\) 的倍数转移。复杂度 \(O(n\log n)\)。
点击查看代码
#include<bits/stdc++.h>
const int P=998244353;inline void Add(int &x,int y){x=x+y<P?x+y:x+y-P;}
using ll=long long;
int n,f[1000005];
int main(){
std::cin.tie(nullptr)->sync_with_stdio(false);
std::cin>>n;if(n<3)std::cout<<n,exit(0);
f[0]=2;
for(int i=n-1;i>=3;--i){
int res(0);
for(int j=0;j<=n;j+=i)Add(res,f[j]),Add(res,f[j+1]),Add(res,f[j+2]);
Add(f[i+1],res);
}
int ans(0);
for(int i=0;i<=n;++i)Add(ans,f[i]);
std::cout<<1ll*n*ans%P;
return 0;
}
D.Zero
不会。