Solution: CF1060H Sophisticated Device

· · 题解

CF1060H Sophisticated Device

前言

主体思路借鉴于@破壁人五号的题解，菜鸡在此之上做了一些小改动和优化（？），并且感谢同机房大佬@Surround_By_Gugugu提供的优化思路。%%%%%%%

题目传送门

Step 1 转化

我们只能进行两个操作：加法和 d 次幂。而我们要求的是 xy(mod\ p)。我们自然而然地想到龟速乘，但显然龟速乘无法适用于两个未知量相乘。似乎已经无处下手了。

我们再来看看我们要求的式子，面对如此熟悉的式子，很自然我们就能想到它能转化成 \frac{(x + y) ^ 2 - x^2 - y^2}{2} ，并且这个式子满足对称性，所以问题就转化为了如何构造指令，使得 \frac{(x + y) ^ 2 - x^2 - y^2}{2} 出现在其中一个格子里。

Step 2 乘法

龟速乘。

Step 3 减法

a +(p-1)b ≡ a-b(mod\ p)

Step 4 除法

乘法逆元。楼上用的是扩欧求逆元，但 p 给定的是质数，显然可以用费马小定理求逆元。

Step 5 平方

思路来自于@破壁人五号。

当无法直接求出一个数的幂时，我们考虑构造一个多项式来求解。也就是瞎凑

我们将 x^2 用 \Sigma^d_{i=0} a_i(x+i)^{d - i} 来表示，展开后即为

x^2=\Sigma^d_{i=0} C(d,i)x^{d-i}\Sigma^d_{j = 0}a_jj^i

显然，对于 x^i(i \ne 2) 项时，我们要使 C(d,i)\Sigma^d_{j = 0}a_jj^i 为 0（此时可以顺便把 C(d,i) 约掉），而对于二次项时为1。我们便可以推出一个 d+1 项线性方程组，用高斯消元求解即可。

Step 6 “0”

其实不用非要求0，但是求0后可以更快并且更清晰地构造代码。

加 p-1 次1即可。

AC Code

//CF1060H
//构造+高斯消元+逆元 
#include <bits/stdc++.h>
#define ll long long
#define re register
using namespace std;
inline ll read(){//快读 
    ll s = 0, w = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9'){s = (s << 1) + (s << 3) + (ch ^ 48); ch = getchar();}
    return s * w;
}
ll d, p, a[15][15], tot = 2, m[15];
void zero(){    //在5000位存0 
    ll b = p - 1;
    while(b){
        if(b & 1)   printf("+ 5000 4999 5000\n");
        printf("+ 4999 4999 4999\n");
        b >>= 1;
    }
}
ll quickpow(ll x, ll y){    //快速幂
    ll ans = 1;
    while(y){
        if(y & 1)   ans = ans * x % p;
        x = x * x % p;
        y >>= 1;
    }
    return ans % p;
}
void guass(){ //高斯-约旦消元 
//约旦消元对于高斯消元的优点在于不用回带。高斯消元解完后为一个上三角行列式，约旦消元解完后为对角型行列式。
    for(re ll i = 0; i <= d; i++){
        for(re ll j = 0; j <= d; j++){
            a[i][j] = quickpow(j, i);
            if(i == d - 2)  a[i][j] = a[i][j] * d  * (d - 1) / 2 % p;
        }       
        if(i == d - 2)  a[i][d + 1] = 1;
        else    a[i][d + 1] = 0;
    }
    for(re ll i = 0; i <= d; i++){
        ll mmax = i;
        for(re ll j = i + 1; j <= d; j++)   if(fabs(a[j][i]) > fabs(a[mmax][i]))    mmax = j;
        for(re ll j = 0; j <= d + 1; j++)   swap(a[i][j], a[mmax][j]);
        for(re ll j = 0; j <= d; j++){
            if(j == i)  continue;
            double b = a[j][i] * quickpow(a[i][i], p - 2) % p;
            for(ll k = 0; k <= d + 1; k++){
                a[j][k] -= a[i][k] * b;
                a[j][k] = (a[j][k] % p + p) % p;
            }
        }
    }
    for(re ll i = 0; i <= d; i++)   m[i + 1] = a[i][d + 1] * quickpow(a[i][i], p - 2) % p;//将解存入数组
}
ll multi(ll x, ll y){//乘法 
    ll b = y % p;   
    ll a = ++tot;
    ll ans = ++tot;
    printf("+ 5000 5000 %lld\n", ans);
    printf("+ 5000 %lld %lld\n", x, a);
    while(b){
        if(b & 1)   printf("+ %lld %lld %lld\n", a, ans, ans);
        printf("+ %lld %lld %lld\n", a, a, a);
        b >>= 1;
    }
    return ans;
} 
ll getpow(ll x){//平方 
    ll a = ++tot;
    ll b = ++tot;
    ll ans = ++tot;
    printf("+ 5000 %lld %lld\n", x, a);
    printf("+ 5000 5000 %lld\n", b);
    printf("+ 5000 5000 %lld\n", ans);
    for(re ll i = 1; i <= d + 1; i++){
        printf("+ %lld %lld %lld\n", a, b, ++tot);
        printf("^ %lld %lld\n", tot, tot + 1);
        tot++;
        ll tmp = multi(tot, m[i]);
        printf("+ 4998 %lld %lld\n", b, b);
        printf("+ %lld %lld %lld\n", ans, tmp, ans);
    }
    return ans;
}
ll Minus(ll a, ll b){//减法 
    b = multi(b, p - 1);
    ll ans = ++tot;
    printf("+ %lld %lld %lld\n", a, b, ans);
    return ans;
}
int main(){
    d = read(), p = read();
    zero(); guass();    
    printf("+ 1 2 %lld\n", ++tot);
    ll xplusy2 = getpow(tot), x2 = getpow(1), y2 = getpow(2);
    ll fz = Minus(Minus(xplusy2, x2), y2);
    ll ans = multi(fz, quickpow(2, p - 2));
    printf("f %lld", ans);
    return 0;
}