题意
输入给定常数 \(d,p\)。
有 \(5000\) 个内存块，初始时 \(1\) 的值为 \(x\)，\(2\) 的值为 \(y\)，其余的值为 \(1\)。
你有三种操作：
+ a b c：将 \(a\) 内存块和 \(b\) 内存块的和放到 \(c\) 内存块中。^ a b：将 \(a\) 内存块的 \(d\) 次方放到 \(b\) 内存块中。f a：返回内存块 \(a\)，要求 \(a\) 内存块中的数恰好为 \(x\times y\)。
以上所有操作是在模 \(p\) 意义下完成的。
要求操作次数 \(\leq 5000\)。
基本操作
容易发现，我们可以做到将任意一个格子在 \(60\) 步操作之内乘一个任意常数。
类似地，也可以做到除以一个常数。
\(d=2\) 的情况
可以发现 \(xy=\frac{(x+y)^2-x^2-y^2}{2}\)。应用基本操作即可求出。
\(d>2\) 的情况
注意到如果可以对于任意一个 \(x\) 求出它的平方就能应用 \(d=2\) 的做法。
可以发现我们可以通过 \(x^d,(x+1)^d,\cdots,(x+d-2)^d\) 来线性组合出 \(x^2+k_1x+k_0\)，其中 \(k_1,k_0\) 为常数。
此时再将 \(k_1x\) 和 \(k_0\) 减掉即可。
高斯消元求出每个 \((x+i)^d\) 的系数即可。
更进一步
找规律可以发现：\((k+i)^d\) 的系数是 \((-1)^i\binom{d-2}{i}\)。
代码
//Author: Kevin5307
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
void add(int m1,int m2,int to){printf("+ %d %d %d\n",m1,m2,to);}
void power(int m,int to){printf("^ %d %d\n",m,to);}
ll mod;
void multiply(int mem,ll k)
{
if(!k) k=mod;
if(k%2)
{
add(mem,mem,4999);
for(int i=1;i<=30;i++) if((1ll<<i)<=k)
{
if(k>>i&1)
add(mem,4999,mem);
add(4999,4999,4999);
}
}
else
{
add(mem,mem,mem);
multiply(mem,k/2);
}
}
ll ksm(ll a,ll b)
{
if(!b) return 1ll;
if(b%2) return ksm(a*a%mod,b/2)*a%mod;
return ksm(a*a%mod,b/2);
}
int C[11][11];
int main()
{
int d;
ll p;
scanf("%d%lld",&d,&p);
mod=p;
for(int i=0;i<11;i++)
C[i][0]=C[i][i]=1;
for(int i=2;i<11;i++)
for(int j=1;j<i;j++)
C[i][j]=C[i-1][j-1]+C[i-1][j];
ll sum=0;
for(int i=0;i<=d-2;i++)
if(i%2)
sum=(sum-ksm(i,d)*C[d-2][i]%p+p)%p;
else
sum=(sum+ksm(i,d)*C[d-2][i])%p;
ll sum2=0;
for(int i=0;i<=d-2;i++)
if(i%2)
sum2=(sum2-ksm(i,d-1)*d*C[d-2][i]%p+p)%p;
else
sum2=(sum2+ksm(i,d-1)*d*C[d-2][i])%p;
ll sum3=0;
for(int i=0;i<=d-2;i++)
if(i%2)
sum3=(sum3-ksm(i,d-2)*C[d][2]*C[d-2][i]%p+p)%p;
else
sum3=(sum3+ksm(i,d-2)*C[d][2]*C[d-2][i])%p;
multiply(1145,(p-sum%p)%p);
add(1,2,3);
auto f=[&](int x)
{
if(d==2)
{
power(x,x);
return ;
}
power(x,5);
add(x,4,6);
for(int i=1;i<d-2;i++)
add(5+i,4,6+i);
for(int i=6;i<d+4;i++)
power(i,i);
for(int i=0;i<=d-2;i++)
if(i%2)
multiply(5+i,(p-C[d-2][i]%p)%p);
else
multiply(5+i,C[d-2][i]%p);
multiply(x,(p-sum2%p)%p);
for(int i=0;i<=d-2;i++)
add(x,5+i,x);
add(x,1145,x);
multiply(x,ksm(sum3,mod-2));
return ;
};
f(1);f(2);f(3);
multiply(1,p-1);
multiply(2,p-1);
add(1,3,1);
add(1,2,1);
multiply(1,ksm(2,p-2));
printf("f %d\n",1);
return 0;
}