[ICPC Northern Eurasia Finals 2018 K]King Kog’s Reception

Link

多年不碰数据结构的老年选手,估计是做麻烦了。

Solution

对所有来的时刻开线段树,记录每个区间来的骑士的开始时间和结束时间,再记录一下这段时间内有多少时间是空白的,那么这些空白时间可以在开始时间延后时起到“缓冲作用”。
合并也好合并,就是一开始写错了没看出来。

Code

#include <bits/stdc++.h>

const int XN=3e5+11;

struct SegTree {
    struct Info {
        long long l,r,blank;
        Info():l(0),r(-1) {}

        operator bool() const {
            return l<=r;
        }

        friend Info Merge(Info const &a,Info const &b) {
            if(!a) return b;
            else if(!b) return a;
            else {
                Info res=a;
                long long rblank=b.blank+std::max(b.l-a.r-1,0ll);
                res.r=b.r+std::max(a.r-b.l+1-rblank,0ll);
                res.blank+=std::max(rblank-std::max(a.r-b.l+1,0ll),0ll);//
                return res;
            }
        }
    };
    struct Node {
        Node *son[2];
        Info v;
        Node() {
            son[0]=son[1]=0;
        }
    }*root;
    int L,R;

    SegTree(int L,int R):root(0),L(L),R(R) {}

    void Modify(int t,int d) {
        std::function<void(Node*&,int,int)> Modify=[&](Node *&pos,int L,int R) {
            if(!pos)
                pos=new Node;
            if(L==R) {
                pos->v.r=(pos->v.l=t)+d-1;
                pos->v.blank=0;
            } else {
                int M=(L+R)/2;
                t<=M?Modify(pos->son[0],L,M)
                    :Modify(pos->son[1],M+1,R);
                pos->v=Merge(pos->son[0]?pos->son[0]->v:Info()
                            ,pos->son[1]?pos->son[1]->v:Info());
            }
        };
        Modify(root,L,R);
    }

    Info Query(int t) {
        std::function<Info(Node*,int,int)> Query=[&](Node *pos,int L,int R) {
            if(!pos)
                return Info();
            if(R<=t)
                return pos->v;
            else {
                int M=(L+R)/2;
                Info res=Query(pos->son[0],L,M);
                if(M<t)
                    res=Merge(res,Query(pos->son[1],M+1,R));
                return res;
            }
        };
        Info res=Query(root,L,R);
        return Query(root,L,R);
    }
};

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    SegTree seg(1,1e6);
    int q;std::cin>>q;
    static int vt[XN];
    for(int ks=1;ks<=q;++ks) {
        char op[10];
        std::cin>>op;
        if(op[0]=='+') {
            int t,d;std::cin>>t>>d;
            vt[ks]=t;
            seg.Modify(t,d);
        } else if(op[0]=='-') {
            int id;std::cin>>id;
            seg.Modify(vt[id],0);
        } else {
            int t;std::cin>>t;
            std::cout<<std::max(0ll,seg.Query(t).r+1-t)<<'\n';
        }
    }
    return 0;
}

[Codeforces 908D]New Year and Arbitrary Arrangement

Link

Solution

首先,前导b对于ab子序列的个数不会产生影响,为了简化,强制第一个位置是a。
一个比较好用的想法是,任意一个合法解都以b为结尾,可以在最后一个b前面添加任意个a。
从第二个位置开始填,f[i][j]表示填了i个a,有j个ab子序列的概率。
i + j < n时,转移显然。
否则,就直接将在f[i][j]后面加任意个a和一个b产生的贡献累加到答案里,不再进行转移。因为如果将这部分f[i][j]加上一个a继续转移到f[i+1][j]中,就会与f[i][j]后面加任意个a和一个b重复。
f[i][j]后面加任意个a和一个b产生的贡献如下:

\begin{aligned}
&f[i][j]p_b\sum_{k=0}^{\infty}(i+j+k)p_a^k\\
=&f[i][j]p_b[\frac {i+j}{1-p_a}+\frac {p_a}{(1-p_a)^2}]
\end{aligned}

求出最后的答案还要乘上\sum_{i=0}^{\infty}p_b^i=\frac 1{1-p_b},因为在序列前方加上任意个b对概率是有影响的,因而对期望也有影响。

Code

#include <bits/stdc++.h>

const int P=1e9+7,XN=1e3+11;

int Add(int x,int const &y) {
    return (x+=y)>=P?x-P:x;
}

void AddBy(int &x,int const &y) {
    x=Add(x,y);
}

int Minus(int x,int const &y) {
    return (x-=y)<0?x+P:x;
}

int Mul(long long x,int const &y) {
    return x*y%P;
}

int Pow(long long base,int v) {
    static long long res;
    for(res=1;v;v>>=1,(base*=base)%=P)
        if(v&1)
            (res*=base)%=P;
    return res;
}

int Inverse(int x) {
    return Pow(x,P-2);
}

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    int n,a,b;std::cin>>n>>a>>b;
    int pa=Mul(a,Inverse(a+b)),pb=Mul(b,Inverse(a+b));
    static int f[XN][XN];
    f[1][0]=pa;
    int c1=Inverse(Minus(1,pa)),c2=Mul(pa,Mul(c1,c1));
    int Ans=0;
    for(int i=1;i<=n;++i)
        for(int j=0;j<=n;++j) {
            if(i+j<n) {
                AddBy(f[i+1][j],Mul(pa,f[i][j]));
                AddBy(f[i][i+j],Mul(pb,f[i][j]));
            } else
                AddBy(Ans,Mul(Mul(pb,f[i][j]),((long long)(i+j)*c1+c2)%P));
        }
    Ans=Mul(Ans,Inverse(Minus(1,pb)));
    std::cout<<Ans<<'\n';
    return 0;
}

ICPC EC-Final 2018 I Misunderstood … Missing

Link

Solution

小数据爆搜,大数据三个贪心取max
DP的话,需要让2、3操作的贡献能够提前计算。
而2的贡献与后面攻击的下标和有关,3的贡献和后面攻击的次数有关,这样就有了状态。

Code

const int XN=1e2+11;

void Work() {
    static int a[XN],b[XN],c[XN];
    static long long f[2][XN][XN*XN];
    int n;fin>>n;
    for(int i=1;i<=n;++i)
        fin>>a[i]>>b[i]>>c[i];
    memset(f,0,sizeof(f));
    int cur=0;
    for(int i=1,sum=n*(n+1)/2-1;i<=n;sum-=++i,cur^=1)
        for(int j=0;j<=n-i;++j)
            for(int k=0;k<=sum;++k)
                f[cur][j][k]=Max(f[cur^1][j][k]+Max((long long)b[i]*(k-i*j),(long long)c[i]*j),f[cur^1][j+1][k+i]+a[i]);
    fout<<f[cur^1][0][0]<<'\n';
}

int main() {
    int T;fin>>T;
    while(T--)
        Work();
    return 0;
}

[EC-Final 2017H]Mr. Panda and Birthday Song

Link

Solution

两次dp,一次尽量符合要求,一次尽量不符合要求,即一次让连续的元音、辅音尽量长,一次让连续的辅音元音尽量短,判断判断就能转移出来了。

Code

const int XN=1e6+11,INF=0x1f1f1f1f;

int main() {
    int T;fin>>T;
    const char *Ans[]={"LIKE","SURPRISE","DISLIKE"};
    std::set<char> vowels({'a','e','i','o','u'});
    for(int ks=1;ks<=T;++ks) {
        printf("Case #%d: ",ks);
        static char s[XN];
        int x,y;
        fin>>(s+1)>>x>>y;//x vow y non-vow
        int n=strlen(s+1);
        static int f[XN][2];
        int type=0;
        for(int i=1;i<=n;++i) {
            f[i][0]=f[i][1]=-1;
            if(s[i]=='?') {
                if(~f[i-1][0])
                    f[i][1]=1;
                else
                    f[i][1]=f[i-1][1]+1;
                if(~f[i-1][1])
                    f[i][0]=1;
                else
                    f[i][0]=f[i-1][0]+1;
            } else if(vowels.count(s[i])) {
                if(~f[i-1][0])
                    f[i][1]=1;
                else
                    f[i][1]=f[i-1][1]+1;
            } else {
                if(~f[i-1][1])
                    f[i][0]=1;
                else
                    f[i][0]=f[i-1][0]+1;
            }
            if(f[i][0]==y)
                f[i][0]=-1;
            if(f[i][1]==x)
                f[i][1]=-1;
            if(f[i][0]==-1 && f[i][1]==-1) {
                type=2;
                break;
            }
        }
        if(type!=2) {
            for(int i=1;i<=n;++i) {
                f[i][0]=f[i][1]=-1;
                if(s[i]=='?') {
                    if(f[i-1][1]!=-1)
                        f[i][1]=f[i-1][1]+1;
                    else
                        f[i][1]=1;
                    if(f[i-1][0]!=-1)
                        f[i][0]=f[i-1][0]+1;
                    else
                        f[i][0]=1;
                } else if(vowels.count(s[i])) {
                    if(f[i-1][1]!=-1)
                        f[i][1]=f[i-1][1]+1;
                    else
                        f[i][1]=1;
                } else {
                    if(f[i-1][0]!=-1)
                        f[i][0]=f[i-1][0]+1;
                    else
                        f[i][0]=1;
                }
                if(f[i][0]==y || f[i][1]==x) {
                    type=1;
                    break;
                }
            }
        }
        puts(Ans[type]);
    }
    return 0;
}

[ECL-Final 2017D]Mr. Panda and Geometric Sequence

Link

Solution

x划分出的前三项为a[1],a[2],a[3],则a[1]a[2]a[3]=a[2]^3\le x\le 10^{15}a[2]\le 10^5

Code

std::vector<long long> nums;
void Prep() {
    const int N=1e5;
    const long long UP=1e15;
    //k*p*q
    auto Join=[](long long a,long long b)->long long {
        for(long long x=b;x;x/=10)
            if((a*=10)>UP)
                return UP+1;
        return a+=b;
    };

    for(long long p=1;p<=N;++p)
        for(long long q=p+1;p*q<=N;++q)
            if(std::__gcd(p,q)==1) {
                for(long long k=1;k*p*q<=N;++k) {
                    long long x=Join(Join(k*p*p,k*p*q),k*q*q),a=k*q*q;
                    while(x<=UP) {
                        nums.push_back(x);
                        if(a*q%p)
                            break;
                        else
                            x=Join(x,a=a*q/p);
                    }
                }
            }
    std::sort(nums.begin(),nums.end());
    nums.erase(std::unique(nums.begin(),nums.end()),nums.end());
}

int main() {
    Prep();
    int T;fin>>T;
    for(int ks=1;ks<=T;++ks) {
        printf("Case #%d: ",ks);
        long long l,r;fin>>l>>r;
        auto Solve=[&](long long x) {
            return std::upper_bound(nums.begin(),nums.end(),x)-nums.begin();
        };

        fout<<Solve(r)-Solve(l-1)<<'\n';
    }
    return 0;
}

[ECL-Final 2017 G]Image Recognition

Link

Solution

最开始的想法是,把每次的询问中相邻两个串找到一个不同的位置就能区分开。然而,“不同”关系不具有传递性。如何才能让A、B不同,B、C不同,那么A、C就不同?考虑把01串排序,也将询问的串排序。那么设A、B第一个不同的位置为i。由于A<B,则A[i]=0,B[i]=1,C[i]=1,由此推出了A、C不同。

Code

暴力的实现:

const int XN=2e3+11,XM=4e5+11;

struct BitSet {

    static int BW;

    unsigned long long s[(XM>>6)+1];

    void Set(unsigned int pos,bool val) {
        val==0?(s[pos>>6]&=~(1ull<<(pos&63))):(s[pos>>6]|=1ull<<(pos&63));
    }

    static int XorFirst1(BitSet const &a,BitSet const &b) {
        for(int i=0;i<BW;++i) {
            unsigned long long x=a.s[i]^b.s[i];
            if(x)
                return 64*i-1+__builtin_ffsll(x);
                    //(x&(-1u)?__builtin_ffs(x&(-1u)):__builtin_ffs(x>>32)+32);
        }
        return -1;
    }

    void Reset() {
        for(int i=0;i<BW;++i)
            s[i]=0;
    }
}b[XN];
int BitSet::BW;

int main() {
    int T;fin>>T;
    for(int ks=1;ks<=T;++ks) {
        printf("Case #%d:\n",ks);
        int n,m,q;fin>>n>>m>>q;
        BitSet::BW=(m>>6)+1;
        static std::pair<std::string,int> c[XN];
        for(int i=0;i<n;i++){
            std::cin>>c[i].first;
            c[i].second=i;
        }
        std::sort(c,c+n);
        static int ref[XN];
        for(int i=0;i<n;++i) {
            ref[c[i].second]=i;
            b[i].Reset();
            for(int j=0;j<m;j++)
                b[i].Set(j,c[i].first[j]=='1');
        }
        while(q--) {
            int cnt;fin>>cnt;
            static int a[XN];
            for(int i=0;i<cnt;++i) {
                fin>>a[i];
                a[i]=ref[a[i]];
            }
            std::sort(a,a+cnt);
            static int Ans[XN];
            for(int i=0;i<cnt-1;++i)
                Ans[i]=BitSet::XorFirst1(b[a[i]],b[a[i+1]]);
            std::sort(Ans,Ans+cnt-1);
            int ac=std::unique(Ans,Ans+cnt-1)-Ans;
            fout<<ac<<' ';
            for(int i=0;i<ac;++i)
                fout<<Ans[i]<<' ';
            fout<<'\n';
        }
    }
    return 0;
}

Hash+二分
从CF上学来的做法。注意这是01串,可以将字符串的hash转化成集合的hash。

const int XN=2e3+11,XM=4e3+11;

int main() {
    srand(233);
    static unsigned long long h[XM];
    for(int i=0;i<XM;++i)
        h[i]=(unsigned long long)rand()<<32|rand();
    int T;fin>>T;
    for(int ks=1;ks<=T;++ks) {
        printf("Case #%d:\n",ks);
        int n,m,q;fin>>n>>m>>q;
        static unsigned long long hash[XN][XM];
        static char s[XN][XM];
        static int seq[XN],rank[XN];
        for(int i=0;i<n;++i) {
            fin>>s[i];
            hash[i][0]=s[i][0]=='1'?h[0]:0;
            for(int j=1;j<m;++j)
                hash[i][j]=hash[i][j-1]^(s[i][j]=='1'?h[j]:0);
            seq[i]=i;
        }
        auto First=[&](int x,int y)->int {
            if(hash[x][0]!=hash[y][0])
                return 0;
            else {
                int L=0,R=m-2;
                while(L!=R) {
                    int M=(L+R+1)/2;
                    if(hash[x][M]==hash[y][M])
                        L=M;
                    else
                        R=M-1;
                }
                return L+1;
            }
        };
        std::sort(seq,seq+n,[&](int x,int y)->bool {return s[x][First(x,y)]=='0'; });
        for(int i=0;i<n;++i)
            rank[seq[i]]=i;
        while(q--) {
            int cnt;fin>>cnt;
            static int a[XN];
            for(int i=0;i<cnt;++i)
                fin>>a[i];
            std::sort(a,a+cnt,[&](int x,int y)->bool { return rank[x]<rank[y]; });
            static int Ans[XN];
            for(int i=0;i<cnt-1;++i)
                Ans[i]=First(a[i],a[i+1]);
            std::sort(Ans,Ans+cnt-1);
            int ac=std::unique(Ans,Ans+cnt-1)-Ans;
            fout<<ac<<' ';
            for(int i=0;i<ac;++i)
                fout<<Ans[i]<<' ';
            fout<<'\n';
        }
    }
    return 0;
}

[CF1088E]Ehab and a component choosing problem

Link

Solution

答案的值等于整棵树的点权最大联通块,可以用一次树形DP求出来。
接下来就求最多有多少个点权和等于所求答案的联通块。
有一个贪心是,凑出顶点深度更深的联通块一定不会比凑出顶点深度更浅的联通块更优。因此第二次DFS的时候如代码所示再DP一遍。

Code

const int XN=3e5+11;

std::vector<int> G[XN];
int a[XN];

long long f[XN],g[XN],res;

void DP(int pos,int fa) {
    f[pos]=a[pos];
    for(int u : G[pos]) if(u!=fa) {
        DP(u,pos);
        f[pos]+=std::max(f[u],0ll);
    }
}

int cnt=0;

void DFS(int pos,int fa) {
    g[pos]=a[pos];
    for(int u : G[pos]) if(u!=fa) {
        DFS(u,pos);
        g[pos]+=std::max(g[u],0ll);
    }
    if(g[pos]==res) {
        cnt++;
        g[pos]=0;
    }
}

int main() {
    int n;fin>>n;
    for(int i=1;i<=n;++i)
        fin>>a[i];
    for(int i=1;i<=n-1;++i) {
        int x,y;fin>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    DP(1,0);
    res=*std::max_element(f+1,f+1+n);
    DFS(1,0);
    fout<<res*cnt<<' '<<cnt<<'\n';
    return 0;
}

[CF1043E]Make It One

Link

Solution

将找最小值变成求是否可行,而求是否可行的方法又是容斥计数判断是否为0,这波操作666
f[i][j]表示选i个数字\gcdj的方案数目,答案就是最小的i使得f[i][1]\not=0
f[i][j]=\binom {i}{c[j]}-\sum_{k=2}f[i][j*k]c[j]表示所有数字中整除j的个数。

Code

const int XN=3e5+11,P=1e9+7;

int Add(int x,int const &y) {
    return (x+=y)>=P?x-P:x;
}

int Minus(int x,int const &y) {
    return (x-=y)<0?x+P:x;
}

int Mul(long long x,int const &y) {
    return x*y%P;
}

int Pow(long long base,int v) {
    long long res;
    for(res=1;v;(v>>=1),(base*=base)%=P)
        if(v&1)
            (res*=base)%=P;
    return res;
}

int main() {
    static int f[8][XN],a[XN],fact[XN],ifact[XN],cnt[XN],c[XN];
    int n,m=0;fin>>n;

    fact[0]=1;
    for(int i=1;i<=n;++i)
        fact[i]=Mul(fact[i-1],i);
    ifact[n]=Pow(fact[n],P-2);
    for(int i=n-1;i>=0;--i)
        ifact[i]=Mul(ifact[i+1],i+1);

    auto C=[](int n,int m) { return n>=m?Mul(fact[n],Mul(ifact[n-m],ifact[m])):0; };

    for(int i=1;i<=n;++i) {
        fin>>a[i];
        f[1][a[i]]=1;
        Enlarge(m,a[i]);
        cnt[a[i]]++;
    }
    for(int i=1;i<=m;++i)
        for(int j=1;i*j<=m;++j)
            c[i]+=cnt[i*j];
    for(int i=2;i<=7;++i) {
        for(int j=m;j>=1;--j) {
            f[i][j]=C(c[j],i);//整除j的个数
            for(int k=2;k*j<=m;++k)
                f[i][j]=Minus(f[i][j],f[i][k*j]);
        }
    }
    int Ans=-1;
    for(int i=1;i<=7;++i)
        if(f[i][1]) {
            Ans=i;
            break;
        }
    fout<<Ans<<'\n';
    return 0;
}

[ICPC 2018 Shenyang Onsite L][Gym 101955L]Machining Disc Rotors

Link

Solution

最远点对一定出现在一对交点处,或者交点和它的未被覆盖的对称点处。考虑弦长变化的单调性即可证明。

Code

const int XN=2e2+11;
const double eps=1e-10,pi=acos(-1);

int sgn(double const &x) {
    return (x>-eps)-(x<eps);
}

struct Point {
    double x,y;

    double Length() const {
        return sqrt(x*x+y*y);
    }

    Point Normal() const {
        return Point{-y,x};
    }

    Point Unit() const {
        double len=Length();
        return Point{x/len,y/len};
    }

    friend Point operator +(const Point &a,const Point &b) {
        return Point{a.x+b.x,a.y+b.y};
    }

    friend Point operator -(const Point &a,const Point &b) {
        return Point{a.x-b.x,a.y-b.y};
    }

    friend Point operator *(const Point &a,const double &k) {
        return Point{a.x*k,a.y*k};
    }

    friend Point operator /(const Point &a,const double &k) {
        return Point{a.x/k,a.y/k};
    }

    friend double Inner(const Point &a,const Point &b) {
        return a.x*b.x+a.y*b.y;
    }

    friend double Outer(const Point &a,const Point &b) {
        return a.x*b.y-a.y*b.x;
    }
};

double Dist(const Point &a,const Point &b) {
    return (a-b).Length();
}

void Work() {
    int n,R;fin>>n>>R;
    Point o{0,0};
    auto Atan2=[](double const &y,double const &x) { double r=atan2(y,x); return r<0?r+pi*2:r; };
    bool flag=0;
    auto Calc=[&](Point p,int r)->std::vector<Point> {
        int d1=sgn(Dist(o,p)-R-r),d2=sgn(Dist(o,p)-fabs(R-r));
        if(d1==0)
            return {p/(R+r)*R};
        else if(d1<0 && d2==0) {
            return {p/(R-r)*R};
        } else if(d1<0 && d2>0) {
            double d=Dist(o,p),x=(R*R-r*r+d*d)/(2*d),h=sqrt(R*R-x*x);
            Point v=(p-o).Unit(),n=v.Normal();
            return {v*x-n*h,v*x+n*h};
        } else
            return {};
    };

    std::vector<Point> cross;
    std::vector<std::pair<double,double> > ranges;
    for(int i=1;i<=n;++i) {
        int x,y,r;
        fin>>x>>y>>r;
        std::vector<Point> nc=Calc(Point{(double)x,(double)y},r);
        for(Point &p : nc)
            cross.push_back(p);
        if(nc.size()==1) {
            double x=Atan2(nc[0].y,nc[0].x);
            ranges.push_back({x,x});
        } else if(nc.size()==2)
            ranges.push_back({Atan2(nc[0].y,nc[0].x),Atan2(nc[1].y,nc[1].x)});
    }
    std::sort(ranges.begin(),ranges.end());
    double Ans=0;
    for(size_t i=0;i<cross.size();++i) {
        for(size_t j=i+1;j<cross.size();++j)
            Enlarge(Ans,Dist(cross[i],cross[j]));
        double ang=Atan2(-cross[i].y,-cross[i].x);
        auto Cover=[&](std::pair<double,double> const &x,double const &y)->bool {
            if(x.first<=x.second)
                return x.first<=y && y<=x.second;
            else
                return x.first<=y || y<=x.second;
        };
        auto iter=std::upper_bound(ranges.begin(),ranges.end(),std::pair<double,double>(ang,ang));
        if(iter!=ranges.begin())
            flag|=!Cover(*--iter,ang) && !Cover(ranges.back(),ang);
        else
            flag|=!Cover(ranges.back(),ang);
        if(flag)
            break;
    }
    if(flag)
        Ans=R*2;
    fout<<Ans<<'\n';
}

int main() {
    int T;fin>>T;
    for(int ks=1;ks<=T;++ks) {
        printf("Case #%d: ",ks);
        Work();
    }
    return 0;
}

[ICPC 2018 Shenyang Onsite K][Gym 101955K]Let the Flames Begin

Link

Solution

求步长为k的约瑟夫游戏中第m个出圈的人。
n\le 10^{18},\min{m,k}\le 10^6

The Initial Josephus Problem Solution

f[n]表示n个人围成一圈玩约瑟夫最后剩下的人的标号。
由于删掉一个人之后就会变成n-1的问题,只需要考虑删掉这一个人对于n-1问题的影响。可以发现,删掉第k个人的影响只是n-1问题中的第一个人变成大问题中的第k+1个人,也就是所有人的标号都增加了k
因此f[n]=(k+f[n-1])\mod n(从0开始标号)

This Enhanced Problem Solution

类似的思路
f[n][m]表示n个人第m个出圈的是谁,那么根据前面的分析f[n][m]=(k+f[n-1][m-1])\mod n
边界条件f[n][1]=m-1,在m小的时候直接递推过去就行了。
km大的时候,核心思想是优化递推式。由于kn大,所以走很多步才会被膜一次,那么就算一下会走几步被膜,把k乘上次数去算,一次走多步。
假设当前递推值为p,当前总人数为tx步之后需要mod,则有下式
p+xk\ge t+x。根据此式就能解出x了。

Code

int main() {
    int T;fin>>T;
    for(int ks=1;ks<=T;++ks) {
        printf("Case #%d: ",ks);
        long long n,m,k;fin>>n>>m>>k;
        long long Ans=(k-1)%(n-m+1);
        if(m<k) {
            for(int i=2;i<=m;++i)
                Ans=(Ans+k)%(n-m+i);
            ++Ans;
        } else {
            if(k==1)
                Ans=m;
            else {
                long long tot,p,x;
                for(tot=n-m+1,p=(k-1)%(n-m+1);
                        tot+(x=(tot-p)/(k-1)+((tot-p)%(k-1)!=0))<=n;
                        (p+=k*x)%=(tot+=x));
                p+=(n-tot)*k;
                Ans=++p;
            }
        }
        fout<<Ans<<'\n';
    }
    return 0;
}