Codeforces

Luogu

分析

首先确定基本的计算方式
$$
xy=\frac{(x+y)^2-x^2-y^2}{2}
$$
则我们需要平方、减法、乘法(除以 $2$ 就是乘逆元)这三种运算。

既然要造计算机,那么一定要先求出一个 $0$ 来。因为 $1+1\times(p-1)\equiv 0\pmod p$,所以可以快速乘一下。

for (int i=p-1;i;i>>=1) { // 0 -> o[16]
    if (i&1) puts("+ 15 16 16");
    puts("+ 15 15 15");
}

有了 $0$ 就可以实现赋值和清零了。

接下来先考虑乘法。因为乘的是常数所以可以想到快速乘。

void mul(int a,int b,int c) { // o[a] * b -> o[c]
    printf("+ 16 16 %d\n",c);
    printf("+ %d 16 15\n",a);
    for (;b;b>>=1) {
        if (b&1) printf("+ %d 15 %d\n",c,c);
        puts("+ 15 15 15");
    }
}

然后考虑减法,可以想到 $-b\equiv (p-1)b\pmod p$。

void sub(int a,int b,int c) { // o[a] - o[b] -> o[c]
    mul(b,p-1,14);
    printf("+ %d 14 %d\n",a,c);
}

剩下的是平方。设 $x^2=a_0(x+0)^d+a_1(x+1)^d+\cdots+a_d(x+d)^d$,可以二项式定理展开,则仅有 $[x^2]$ 项系数为 $1$,从而可以高斯消元解出 $a_{0..d}$。这样子平方只要模拟一下上面这个式子就好了。

void pow2(int a,int b) { // o[a] ^ 2 -> o[b]
    printf("+ 16 16 %d\n",b);
    printf("+ 16 %d 13\n",a);
    for (int i=0;i<=d;++i) {
        puts("^ 13 12");
        mul(12,M[i][d+1],11);
        printf("+ %d 11 %d\n",b,b);
        puts("+ 10 13 13");
    }
}

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

int d,p,C[20][20],M[20][20];

int qpow(int a,int b) { int c=1;
    for (;b;b>>=1,a=1ll*a*a%p) if (b&1) c=1ll*c*a%p;
    return c;
}

void Gauss(int n) {
    for (int i=0;i<=n;++i) {
        if (!M[i][i]) {
            for (int j=i+1;j<=n;++j)
                if (M[j][i]) { swap(M[i],M[j]); break; }
        }
        int inv=qpow(M[i][i],p-2);
        for (int j=i+1;j<=n;++j) {
            int t=1ll*M[j][i]*inv%p;
            for (int k=0;k<=n+1;++k)
                M[j][k]=(M[j][k]-1ll*t*M[i][k]%p+p)%p;
        }
    }
    for (int i=n;~i;--i) {
        M[i][n+1]=1ll*M[i][n+1]*qpow(M[i][i],p-2)%p;
        for (int j=0;j<i;++j)
            M[j][n+1]=(M[j][n+1]-1ll*M[i][n+1]*M[j][i]%p+p)%p;
    }
}

int qmul(int a,int b) { int c=0;
    for (;b;b>>=1,a=(a+a)%p) if (b&1) c=(c+a)%p;
    return c;
}

// used 15
void mul(int a,int b,int c) { // o[a] * b -> o[c]
    printf("+ 16 16 %d\n",c);
    printf("+ %d 16 15\n",a);
    for (;b;b>>=1) {
        if (b&1) printf("+ %d 15 %d\n",c,c);
        puts("+ 15 15 15");
    }
}

// used 14
void sub(int a,int b,int c) { // o[a] - o[b] -> o[c]
    mul(b,p-1,14);
    printf("+ %d 14 %d\n",a,c);
}

//used 10 & 11 & 12 & 13
void pow2(int a,int b) { // o[a] ^ 2 -> o[b]
    printf("+ 16 16 %d\n",b);
    printf("+ 16 %d 13\n",a);
    for (int i=0;i<=d;++i) {
        puts("^ 13 12");
        mul(12,M[i][d+1],11);
        printf("+ %d 11 %d\n",b,b);
        puts("+ 10 13 13");
    }
}

void solve() {
    puts("+ 1 2 3"); // o[3] = x + y
    pow2(3,4); // o[4] = (x + y) ^ 2
    pow2(1,5); // o[5] = x ^ 2
    pow2(2,6); // o[6] = y ^ 2
    puts("+ 5 6 7"); // o[7] = x ^ 2 + y ^ 2
    sub(4,7,8); // o[8] = (x + y) ^ 2 - x ^ 2 - y ^ 2
    mul(8,qpow(2,p-2),9);
    puts("f 9");
}

int main() {
    d=read(),p=read();
    for (int i=p-1;i;i>>=1) {
        if (i&1) puts("+ 15 16 16");
        puts("+ 15 15 15");
    }
    for (int i=C[0][0]=1;i<=d;++i)
        for (int j=C[i][0]=1;j<=i;++j)
            C[i][j]=(C[i-1][j-1]+C[i-1][j])%p;
    for (int i=0;i<=d;++i)
        for (int j=0;j<=d;++j)
            M[i][j]=1ll*C[d][d-i]*qpow(j,d-i)%p;
    M[2][d+1]=1;
    Gauss(d);
    solve();
    return 0;
}
最后修改:2020 年 07 月 30 日 03 : 52 PM