AT_abc380
题目链接：https://atcoder.jp/contests/abc380
打*的是我很不会的题目，要常拿出来重写一下。
D
题目大意：将一个字符串s不断进行 反转—接续 操作。问第i个字符是多少。
题解：其实一开始就想到，s和s’可以看成两个整体。整个结果串就是这两个整体的组合。那么其实就是要找到这两种串出现的位置规律，然后题目要求第k个字符的时候，就直接求它在哪个第几个整体就好。但比赛时想不出来这两个整体的规律。其实首先，看题目是不停反转接续，那结果大概如下：sggsgssggssgsggs...用普通想规律很难看出来，那可以看看和二进制有没有联系（况且这个字符每次操作长度都 *2 ，其实也可以往二进制上引一引。我们可以看出，每个被反转的字符（从0开始排序），二进制中1的个数都是奇数（0 1 2 4 7 8...），我看一篇题解有个网站可以帮忙找规律，叫oeis（也可以去它那看看），反正最后规律是这样的。然后跟着规律写就对了。
代码：
#include<iostream>
using namespace std;
#define int long long
string s;
int l,q,k;
int check(int m){
int cnt=0;
while(m){
if(m%2)cnt++;
m/=2;
}
if(cnt%2==1)return 1;//需要反转;
return 0;
}
char get(int pos,int check){
if(check==0){
return s[pos];
}
if(s[pos]>='a'&&s[pos]<='z'){
return s[pos]-'a'+'A';
}else{
return s[pos]-'A'+'a';
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>s>>q;
l=s.size();
while(q--){
cin>>k;
int m=(k-1)/l;
cout<<get((k-1)%l,check(m))<<' ';
}
return 0;
}E
题目大意：其实就是并查集维护区间个数的问题。不要怕麻烦，每个颜色的find都要存储与一下其左边和右边的颜色，方便合并，
代码：
#include<iostream>
using namespace std;
int n,q,ty,x,c;
int fa[700010],le[700010],ri[1000010];
int num_col[700010],col[700010],num[1000010];
void init(int n){
for(int i=1;i<=n;i++){
le[i]=i-1;ri[i]=i+1;
fa[i]=i;
col[i]=i;//第i个格子的颜色;
num_col[i]=1;//第i个颜色对应的方块数量;
num[i]=1;//第i个格子并查集的元素个数;
}
}
int find(int x){
if(fa[x]==x)return fa[x];
fa[x]=find(fa[x]);
return fa[x];
}
void unionn(int i,int j){
int fa_i=find(i);int fa_j=find(j);
if(fa_i==fa_j)return ;
fa[fa_i]=fa_j;
num[fa_j]+=num[fa_i];
le[fa_j]=min(le[fa_j],le[fa_i]);ri[fa_j]=max(ri[fa_j],ri[fa_i]);
}
void ty_1(int x,int c){
int fa_x=find(x);
if(col[fa_x]!=c){
num_col[col[fa_x]]-=num[fa_x];
num_col[c]+=num[fa_x];
col[fa_x]=c;
if(col[find(le[fa_x])]==c){
unionn(le[fa_x],fa_x);
}
if(col[find(ri[fa_x])]==c){
unionn(ri[fa_x],fa_x);
}
}
}
int main()
{
cin>>n>>q;
init(n);
while(q--){
cin>>ty;
if(ty==1){
cin>>x>>c;
ty_1(x,c);
}else{
cin>>c;
cout<<num_col[c]<<endl;
}
}
return 0;
}
F***
题目大意：很不错的题目。属于是踩着我的弱点了。这种dp+搜索剪枝真的不太擅长。so以后有机会还得要多练。
思路：一看n+m+l<=12就应该想到搜索+剪纸。同时搜索要用记忆化搜索。那么记忆化如何实现（如何记录状态？）二进制数。牌的每一种不同状态都可以用一列（m+n+l）位的二进制数来表示（2^12也不大，不会爆），然后用一个dp[1<<13][1<<13]来表述两个人的每种不同状态下输赢情况。第一维表示第一个人走时手上牌情况，第二维表示第二个人走时二进制状态（若在这个人的手上就是1，其他情况都为0） 。最后第i张牌是否在桌上可以用（a^b)>>i&1来判断 （a b是两个人的二进制状态串）。那么每次dfs就传两个串就好啦。
代码：
#include<iostream>
using namespace std;
int n,m,l;
int ans[1<<13][1<<13];
int A[15];
bool dfs(int t,int a){
if(ans[t][a])return ans[t][a];
bool flag=false;
for(int i=0;i<n+m+l;i++){//遍历放哪张牌
if(t>>i&1){//t的第i位上是不是1，就是说此人有没有第i张牌
if(!dfs(a,t^(1<<i))){//只放不拿的情况
flag=true;break;
}
for(int j=0;j<n+m+l;j++){//遍历拿桌上哪张牌
if(!((t|a)>>j&1)&&A[j]<A[i]){//此牌要求：桌上有 且 小于拿的牌
if(!dfs(a,t^(1<<i)^(1<<j))){
flag=true;break;
}
}
}
}
}
if(flag){
ans[t][a]=1;
}
return flag;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m>>l;
for(int i=0;i<n+m+l;i++){
cin>>A[i];
}
int t=0,a=0;
for(int i=0;i<n;i++){
t+=1<<i;
}
for(int i=n;i<n+m;i++){
a+=1<<i;
}
if(dfs(t,a)){
cout<<"Takahashi";
}else{
cout<<"Aoki";
}
return 0;
}G
题目大意：其实这题我认为思路不难想。我自己做的时候大致思路是找到了，但困难在实现方面没想到。
思路：逆序对区间问题抓住一个点（我已经遇到两次了）：当对l~r这个区间的数（随机）调换顺序时，对于1~l-1,r+1~n的所有数，与它们有关的逆序对是不变的。也就是说，不管怎么调换，逆序对变换的也就只有l~r这区间部分的数。抓住这点，其实这题很好分析。（草稿纸忘带了，等带了我直接贴上来吧，不想写了）我就被卡在：1~l-1&&r+1~n这段数的逆序对数量和怎么求。后来看懂答案了：用总的逆序对数量-l~r这段的逆序对数量。那么问题就转换成：如和不超时求l~r这段的逆序对和呢？首先，1~k这段可以算出来（树状数组走即可），接着，随着l++，r++，只要把（l-1）个数从树状数组里删掉，并且加上（r+1）个数即可。逆序对的数量就是 上次(l-1~r-1)求得的-（l-1）产生的+（r+1）产生的。l-1产生的直接用树状数组即可，r+1产生的就是k-1-（树状数组求得比r+1小的数量）。就得到了。
同时，学习一下分数求模。（快速幂）
最后那个，每一步都要求模，很容易错！最多mod*mod,mod*mod*mod就嫌多了。要当心。
代码：
#include<iostream>
#include<algorithm>
using namespace std;
#define int long long
int n,k;
const int N=5e5;
const int mod=998244353;
int p[1000010];
int a[1000010];
int tr[1000010];
int fastPow(int a, int k, int p){ // a 底数， k 指数， 求 a^k mod p
int res = 1;
a%=p;
while(k > 0){
if (k & 1) res = res * a % p;
a = a * a % p;
k >>= 1;
}
return res;
}
int fractionMod(int a, int b, int p){ // a/b mod p
return ((a % p) * fastPow(b, p-2, p)) % p;
}
int lowbit(int i){
return i&-i;
}
void my_add(int i,int t){
int pos=i;
while(pos<=N){
tr[pos]+=t;
pos+=lowbit(pos);
}
}
int my_sum(int i){
int pos=i,ans=0;
while(pos){
ans+=tr[pos];
pos-=lowbit(pos);
}
return ans;
}
signed main()
{
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>p[i];
}
int cnt=0,u=0,v=0,sum=0;
for(int i=n;i>=1;i--){
my_add(p[i],1);
sum=(sum+my_sum(p[i]-1)%mod)%mod;//he
}
for(int i=n;i>=1;i--){
my_add(p[i],-1);
}
for(int i=k;i>=1;i--){
my_add(p[i],1);
v=(v+my_sum(p[i]-1)%mod)%mod;
}
cnt=(cnt+(sum-v)%mod)%mod;
for(int i=2;i<=n-k+1;i++){
int g=0;
g=(g-my_sum(p[i-1]-1))%mod;
my_add(p[i-1],-1);
g=(g+(k-1)-my_sum(p[i+k-1]-1))%mod;
v=(v+g)%mod;
cnt=(cnt+(sum-v)%mod)%mod;
my_add(p[i+k-1],1);
}
v=cnt%mod;
u=((4*(n-k+1))%mod*(((k-1)*k/2+1)%mod))%mod;
v=v*((k-1)*k/2+1)%mod;
v=((v*4)%mod+((n-k+1)%mod*(((k-1)*k)%mod))%mod*(((k-1)*k/2+1)%mod))%mod;
// cout<<v<<" "<<u<<endl;
int t=__gcd(u,v);
v=v/t;u=u/t;
// cout<<v<<" "<<u<<endl;
int ans=fractionMod(v,u,998244353);
cout<<ans;
return 0;
}