【题解】CF1060H Sophisticated Device

· · 题解

自己博客的广告，若以后有修改多半只写在自己博客中。

题目链接

这道题实在是毒瘤。以及洛谷上的翻译其实是我翻的，质量跟机翻差不多。

首先我们确定求出 xy 的整体思路——xy=\frac{(x+y)^2-x^2-y^2}{2}。

这个思路不难想到：我们能够比较容易实现的两个操作数的运算只有加、减，于是我们将运算转换为加、减与只有一个操作数的平方、除以 2。关键在于如何实现这些运算。

前置技能

我们先考虑几个简单的运算：

0

在求解过程中，有一个数字 0 是很方便的，利用 + zero zero x 就可以清空一格。

在这里需要用到快（慢？）速乘，实现：

int f=p-1;
while(f){
    if(f&1ll){
        cout<<"+ "<<4998<<" "<<zero<<" "<<zero<<endl;
    }
    cout<<"+ "<<4998<<" "<<4998<<" "<<4998<<endl;
    f/=2;
}
//zero=4999

这样 zero 格就有了一个常数 0。

乘以常数

同样是快速乘。要注意的是，每次必须清空所需格子。

int getmulti(int a,int b,int q){
    b=(b%p+p)%p;
    int ans=(q?q:++tot);
    int x=++tot;
    while(b){
        if(b&1ll){
            cout<<"+ "<<x<<" "<<ans<<" "<<ans<<endl;
        }
        cout<<"+ "<<x<<" "<<x<<" "<<x<<endl;
        b/=2;
    }
    return ans;
}
//如果有 q ，答案存在 q 当中。返回结果所在格子。

减法

a-b=a+(p-1)b 
int jian(int a,int b){
    b=getmulti(b,p-1);
    ++tot;
    cout<<"+ "<<a<<" "<<b<<" "<<tot<<endl;
    return tot;
}

除以常数

即乘以其逆元。

下面是重头戏：

求一个数的平方

很明显，x^2 并不能通过 x^d 直接求出。

我们考虑将 x^2 表达为 a_0(x+0)^d+a_1(x+1)^d+\dots +a_d(x+d)^d

将它展开，再按 x 合并同类项，得：

x^2=C_d^0(a_0+a_1+\dots +a_d)x^d+ C_d^1(a_0\times0^1+a_1\times1^1+\dots a_d\times d^1)x^{d-1}+ \dots C_d^d(a_0\times0^d+a_1\times1^d+\dots +a_d\times d^d)x^0

显然我们要求 x^2 项的系数为 1，其余为 0。于是我们可以列出线性方程组，通过高斯消元求出 a_0,a_1,\dots ,a_d。

c[1][1]=1;
for(int i=1;i<=d+1;i++){
    for(int j=1;j<=i;j++){
        if(i==1&&j==1)continue;
        c[i][j]=c[i-1][j]+c[i-1][j-1];
    }
}
for(int i=0;i<=d;i++){
    int q=1;
    for(int j=0;j<=d;j++){
        a[j][i]=c[d+1][j+1]*q%p;
        q*=i;
        q%=p;
    }
}
a[d-2][d+1]=1;
for(int i=0;i<=d;i++){
    bool ok=false;
    int j=0;
    for(;j<=d;j++){
        if(a[j][i]&&!u[j]){
            ok=true;
            u[j]=true;
            break;
        }
    }
    double orz=a[j][i];
    for(int k=0;k<=d+1;k++){
        a[j][k]*=getinv(orz,1,p);
        a[j][k]%=p;
    }
    for(int k=0;k<=d;k++){
        if(k==j)continue;
        orz=a[k][i]*=getinv(a[j][i],1,p);
        for(int l=0;l<=d+1;l++){
            a[k][l]-=orz*a[j][l];
            a[k][l]=(a[k][l]%p+p)%p;
        }
    }
}

实际求的时候，只需要用公式 x^2=a_0(x+0)^d+a_1(x+1)^d+\dots +a_d(x+d)^d 耐心算就可以了。

int getpow2(int x){
    int q=++tot;
    cout<<"+ "<<x<<" "<<zero<<" "<<q<<endl;
    int sum=++tot;
    cout<<"+ "<<zero<<" "<<zero<<" "<<sum<<endl;
    int po=++tot;
    int mul=++tot;
    for(int i=0;i<=d;i++){
        cout<<"^ "<<q<<" "<<po<<endl;
        getmulti(po,a[i][d+1],mul);
        cout<<"+ "<<mul<<" "<<sum<<" "<<sum<<endl;
        cout<<"+ "<<q<<" "<<4997<<" "<<q<<endl;
    }
    return sum;
}

最后就将这些 simple 的操作联合起来：

int x2=getpow2(1);
int y2=getpow2(2);
int q=jian(xysum2,x2);
jian(q,y2);
int ans=getmulti(tot,getinv(2,1,p));
cout<<"f "<<ans<<endl;

完整代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int getint(){
    int ans=0,f=1;
    char c=getchar();
    while(c>'9'||c<'0'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        ans=ans*10+c-'0';
        c=getchar();
    }
    return ans*f;
}

const int inf=19260817;
int extgcd(int a,int b,int& x,int& y){
    if(b){
        int r=extgcd(b,a%b,y,x);
        y-=x*(a/b); return r;
    } else { x=1; y=0; return a; }
}
int getinv(int a,int b,int M){
    int x,y,r=extgcd(a,M,x,y);
    if(b%r) return -1; else x=(x+M)%M*b/r;
    return x%(M/r);
} 

int tot=2,zero=4999;
int d,p;
int getinv(int x){
    int inv=getinv(d,p-2,p);
    ++tot;
    cout<<"^ "<<x<<" "<<tot<<endl;
    for(int i=0;i<inv-1;i++){
        cout<<"^ "<<tot<<" "<<tot<<endl;
    }
    return tot;
}

int a[20][20],c[20][20];

int getpow2(int x);
int getmulti(int a,int b,int q=0);
int jian(int a,int b);

int getpow2(int x){
    int q=++tot;
    cout<<"+ "<<x<<" "<<zero<<" "<<q<<endl;
    int sum=++tot;
    cout<<"+ "<<zero<<" "<<zero<<" "<<sum<<endl;
    int po=++tot;
    int mul=++tot;
    for(int i=0;i<=d;i++){
        cout<<"^ "<<q<<" "<<po<<endl;
        getmulti(po,a[i][d+1],mul);
        cout<<"+ "<<mul<<" "<<sum<<" "<<sum<<endl;
        cout<<"+ "<<q<<" "<<4997<<" "<<q<<endl;
    }
    return sum;
}

int getmulti(int a,int b,int q){
    b=(b%p+p)%p;
    int ans=(q?q:++tot);
    cout<<"+ "<<zero<<" "<<zero<<" "<<ans<<endl;
    int x=++tot;
    cout<<"+ "<<zero<<" "<<a<<" "<<x<<endl;
    while(b){
        if(b&1ll){
            cout<<"+ "<<x<<" "<<ans<<" "<<ans<<endl;
        }
        cout<<"+ "<<x<<" "<<x<<" "<<x<<endl;
        b/=2;
    }
    return ans;
}

int jian(int a,int b){
    b=getmulti(b,p-1);
    ++tot;
    cout<<"+ "<<a<<" "<<b<<" "<<tot<<endl;
    return tot;
}
bool u[20];
signed main(){
    d=getint(),p=getint();

    c[1][1]=1;
    for(int i=1;i<=d+1;i++){
        for(int j=1;j<=i;j++){
            if(i==1&&j==1)continue;
            c[i][j]=c[i-1][j]+c[i-1][j-1];
        }
    }

    for(int i=0;i<=d;i++){
        int q=1;
        for(int j=0;j<=d;j++){
            a[j][i]=c[d+1][j+1]*q%p;
            q*=i;
            q%=p;
        }
    }
    a[d-2][d+1]=1;
    for(int i=0;i<=d;i++){
        bool ok=false;
        int j=0;
        for(;j<=d;j++){
            if(a[j][i]&&!u[j]){
                ok=true;
                u[j]=true;
                break;
            }
        }
        double orz=a[j][i];
        for(int k=0;k<=d+1;k++){
            a[j][k]*=getinv(orz,1,p);
            a[j][k]%=p;
        }
        for(int k=0;k<=d;k++){
            if(k==j)continue;
            orz=a[k][i]*=getinv(a[j][i],1,p);
            for(int l=0;l<=d+1;l++){
                a[k][l]-=orz*a[j][l];
                a[k][l]=(a[k][l]%p+p)%p;
            }
        }
    }
    int f=p-1;
    while(f){
        if(f&1ll){
            cout<<"+ "<<4998<<" "<<zero<<" "<<zero<<endl;
        }
        cout<<"+ "<<4998<<" "<<4998<<" "<<4998<<endl;
        f/=2;
    }
    cout<<"+ "<<1<<" "<<2<<" "<<(++tot)<<endl;
    int xysum2=getpow2(tot);

    int x2=getpow2(1);
    int y2=getpow2(2);
    int q=jian(xysum2,x2);
    jian(q,y2);
    int ans=getmulti(tot,getinv(2,1,p));
    cout<<"f "<<ans<<endl;

    return 0;
}