题解：P14642 【OIMO Round 1】十二宫标志

· · 题解

P14642 【OIMO Round 1】十二宫标志 题解

人比较傻，数学比较差，所以来写点萌新友好的题解。

我们设第 i 步走的方向是 \theta_i，第 i 步走的单位向量是 \vec{v_i}。

则答案就是：

E(|\vec{s}|^2))=E(|\sum_{i=1}^n\vec{v_i}|^2)\\ =E(\sum_{i=1}^n|\vec{v_i}|^2)+2\sum_{1\le i<j\le n} E(\vec{v_i} \vec{v_j})\\ =n+2\sum_{1\le i<j\le n}E(\cos(\theta_j-\theta_i))

有公式：

ℜ(e^{i\theta})=\cos \theta

（ℜ是取实部） 所以我们有：

E(\cos(\theta_j-\theta_i))=ℜ(E(e^{i(\theta_j-\theta_i)}))\\

而我们有：

e^{i(\theta_j-\theta_i)}=\prod_{t=i+1}^j e^{i\delta_t}

（\delta_t 是每一步旋转的角度） 我们发现 \delta_t 彼此之间是独立的，所以这个期望是可以拆的即：

E(\prod_{t=i+1}^j e^{i\delta_t})=E(e^{i\delta_t})^{j-i}

令

r=E(e^{i\delta_t})=(1-p)+pe^{\frac{i\pi}{6}}

那么

E(\cos(\theta_j-\theta_i))=ℜ(r^{j-i})

然后我们要求的答案改成按照 i-j 的值枚举，即：

\sum_{1\le i<j\le n}E(\cos(\theta_j-\theta_i))\\ =\sum_{k=1}^{n-1}(n-k)ℜ(r^{k})\\ =ℜ(\sum_{k=1}^{n-1}(n-k)r^{k})

这是个等差乘等比的形式，就不啰嗦了，错位相减一下的大概就能求出来答案为：

n\frac{r-r^n}{1-r}-\frac{r-nr^n+(n-1)r^{n+1}}{(1-r)^2}

算一下就好了。

放下代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mo=998244353;
int fp(int x,int y){
    int res=1;
    for(;y;y>>=1,x=x*x%mo){
        if(y&1){
            res=res*x%mo;
        }
    }
    return res;
}
struct node{
    int a,b;
    node(){
        a=b=0;
    }
    node(const node &x){
        a=x.a,b=x.b;
    }
    node(int x,int y){
        a=x,b=y;
    }
    node operator +(node c){
        node res((a+c.a)%mo,(b+c.b)%mo);
        return res;
    }
    node operator -(node c){
        node res((a-c.a+mo)%mo,(b-c.b+mo)%mo);
        return res;
    }
    node operator*(node c){
        node res((a*c.a+3*b*c.b)%mo,(b*c.a+a*c.b)%mo);
        return res;
    }
    node operator*(int n){
        node res((a*n%mo+mo)%mo,(b*n%mo+mo)%mo);
        return res;
    }
    node operator/(node c){
        node d(c.a,mo-c.b);
        node res=(*this)*d;
        int iv=fp(((c.a*c.a-3*c.b*c.b)%mo+mo)%mo,mo-2);
        return res*iv;
    }
};

struct cp{
    node a,b;
    cp(node x,node y){
        a=x,b=y;
    }
    cp operator +(cp c){
        cp res(a+c.a,b+c.b);
        return res;
    }
    cp operator -(cp c){
        cp res(a-c.a,b-c.b);
        return res;
    }
    cp operator*(cp c){
        cp res(a*c.a-b*c.b,b*c.a+a*c.b);
        return res;
    }
    cp operator*(int n){
        cp res(a*n,b*n);
        return res;
    }
    cp operator/(cp c){
        cp d(c.a,c.b*-1);
        cp res=(*this)*d;
        node iv(c.a*c.a+c.b*c.b);
        res.a=res.a/iv;
        res.b=res.b/iv;
        return res;
    }
};
cp qpow(cp x,int y){
    cp res({1,0},{0,0});
    for(;y;y>>=1,x=x*x){
        if(y&1) res=res*x;
    }
    return res;
}
void solve(){
    int p,n;
    cin>>p>>n;
    if(p==0){
        cout<<n*n%mo<<" "<<0<<"\n";
        return;
    }
    p=p*fp(100000000,mo-2)%mo;
    node ra((mo+1-p)%mo,p*fp(2,mo-2)%mo);
    node rb(p*fp(2,mo-2)%mo,0);
    cp r(ra,rb),k1({1,0},{0,0});
    cp ans=((r-qpow(r,n))/(k1-r)*n)-((r-qpow(r,n)*n+qpow(r,n+1)*(n-1))/((k1-r)*(k1-r)));
    ans=ans*2;
    cout<<(n+ans.a.a)%mo<<" "<<ans.a.b<<"\n";
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin>>T;
    while(T--){
        solve();
    }
}