分析
首先确定基本的计算方式
$$
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;
}