题解：CF1060H Sophisticated Device

· · 题解

现在支持两种操作：

考虑构造出更多的操作。

0：赋值到另一个位置

给定 x,z，实现 a_z\gets a_x。

这需要构造出 0，然后调用 x+0 即可移动。

使用龟速乘即可，代码如下：

int p = 4999, q = 5000;
for (int x = P - 1; x; x >>= 1) {
    if (x & 1) add(q, p, q);
    add(p, p, p);
}
p0 = 5000, p1 = 4998;

此后 a_{5000} 即为 0。

void copy(int x, int y) { // a[y]=a[x]
    add(x, p0, y);
}

1：乘以常数

给定 x,z 与常数 y，实现 a_z\gets a_x\times y。

龟速乘即可，代码如下：

void mulc(int x, int y, int z) { // a[z]+=a[x]*y
    int p = 4997; copy(x, p);
    for (; y; y >>= 1) {
        if (y & 1) add(z, p, z);
        add(p, p, p);
    }
}

这同时支持了减法、除法、赋值。

2：d=2 的解法

此时考虑 (x+y)^2=x^2+y^2+2xy，使用减法和除法即可。

3：d=3 的解法

考虑求出 (x+y)^2。令 p=x+y，展开 (p+1)^3=p^3+3p^2+3p+1，减去 p^3+3p+1 即可。

4：d=4 的解法

此时展开后有 (p+1)^4=p^4+4p^3+6p^2+4p+1，我们不知道 p^3，爆蛋了。

考虑把这个 4p^3 给消掉，比如展开一个 (p-1)^4=p^4-4p^3+6p^2-4p+1，两式相加就将 p^3 消掉了。

5: 构造平方

根据前面的方法，考虑用 (p+k)^d 相加求出 p^2。

也就是说，我们需要求出一个系数数组 b 和一个常数 c，使得 \sum b_i(p+i)^d=p^2+c。

将 (p+i)^d 展开，得到了关于 b 的方程，第 i 个方程为：

\sum_{j=1}^d\binom{d}{i}j^{d-i}b_j=[i=2]

构造矩阵 A_{i,j}=\binom{d}{i}j^{d-i}，我们需要证明 \det A\neq 0。组合数对行列式的贡献是固定的，提出。剩下是 A'_{i,j}=j^{d-i}，翻转之后是范德蒙德矩阵，因此 \det A\neq 0。

高斯消元解即可。

REP(i, 1, d) {
    A[i][d + 1] = (i == 2);
    REP(j, 1, d) A[i][j] = C(d, i) * qpow((MI)j, d - i);
}
REP(k, 1, d) {
    int t = 0;
    REP(i, 1, d) t = (A[i][k] != 0 ? i : t);
    REP(i, 1, d + 1) swap(A[k][i], A[t][i]);
    DEP(i, d + 1, k) A[k][i] /= A[k][k];
    REP(i, 1, d) {
        if (i == k) continue;
        DEP(j, d + 1, k) A[i][j] -= A[i][k] * A[k][j];
    }
}
REP(i, 1, d) c += qpow((MI)i, d) * A[i][d + 1];

求平方的代码：

void sqr(int x, int y) { // a[y]+=a[x]*a[x]
    REP(i, 1, d) b[i] = 4997 - i;
    add(x, p1, b[1]), mulc(p1, (-c).val(), y);
    REP(i, 2, d) add(b[i - 1], p1, b[i]);
    REP(i, 1, d) powd(b[i], b[i]);
    REP(i, 1, d) mulc(b[i], A[i][d + 1].val(), y);
}

6： 乘法

得到 (x+y)^2 之后减去 x^2+y^2 除以 2 即可。

代码：

void mul(int x, int y, int z) { // a[z]+=a[x]*a[y]
    int p = 4986, q = 4985, r = 4984;
    copy(p0, q), copy(p0, r), add(x, y, p), sqr(p, r);
    copy(x, p), sqr(p, q), copy(y, p), sqr(p, q);
    mulc(q, P - 1, r), mulc(r, (P + 1) / 2, z);
}

:::info[完整实现]

#include <bits/stdc++.h>
#define REP(i, l, r) for (int i = (l); i <= (r); ++ i)
#define DEP(i, r, l) for (int i = (r); i >= (l); -- i)
#define CUP(i, l, r) for (int i = (l); i < (r); ++ i)
#define CDW(i, r, l) for (int i = (r) - 1; i >= (l); -- i)
#define fi first
#define se second
#define pb emplace_back
#define mems(x, v) memset((x), (v), sizeof(x))
#define memc(x, y) memcpy((x), (y), sizeof(x))
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(), (x).end()
#define ppc(x) __builtin_popcount(x)
using namespace std;
namespace math {
    typedef long long LL;
    template <class T> T qpow(T a, LL b) { if (!b) return {1}; T rs = a; b --; for (; b; b >>= 1, a = a * a) if (b & 1) rs = rs * a; return rs; }
    LL mul(LL a, LL b, LL p) { LL rs = a * b - LL(1.L * a * b / p) * p; rs %= p; if (rs < 0) rs += p; return rs; }
    template <unsigned P = 0> struct mint {
        unsigned v; static unsigned mod; mint() = default;
        template <class T> mint(T x) { x %= (int)getmod(), v = x < 0 ? x + getmod() : x; }
        constexpr static unsigned getmod() { if (P > 0) return P; else return mod; }
        static void setmod(unsigned m) { mod = m; }
        mint operator + () const { return *this; }
        mint operator - () const { return mint(0) - *this; }
        mint inv() const { return assert(v), qpow(*this, getmod() - 2); }
        int val() const { return v; }
        mint &operator += (const mint &q) { if (v += q.v, v >= getmod()) v -= getmod(); return *this; }
        mint &operator -= (const mint &q) { if (v -= q.v, v >= getmod()) v += getmod(); return *this; }
        mint &operator *= (const mint &q) { v = 1ull * v * q.v % getmod(); return *this; }
        mint &operator /= (const mint &q) { return *this *= q.inv(); }
        friend mint operator + (mint p, const mint &q) { return p += q; }
        friend mint operator - (mint p, const mint &q) { return p -= q; }
        friend mint operator * (mint p, const mint &q) { return p *= q; }
        friend mint operator / (mint p, const mint &q) { return p /= q; }
        friend bool operator == (const mint &p, const mint &q) { return p.v == q.v; }
        friend bool operator != (const mint &p, const mint &q) { return p.v != q.v; }
        friend bool operator < (const mint &p, const mint &q) { return p.v < q.v; }
        friend bool operator > (const mint &p, const mint &q) { return p.v > q.v; }
        friend bool operator <= (const mint &p, const mint &q) { return p.v <= q.v; }
        friend bool operator >= (const mint &p, const mint &q) { return p.v >= q.v; }
        friend istream &operator >> (istream &is, mint &a) { LL x; is >> x, a = x; return is; }
        friend ostream &operator << (ostream &os, const mint &a) { os << a.v; return os; }
    };
    template <> unsigned mint<0>::mod = 998244353;
    template <typename MI>
    struct Comb {
        #define P MI::getmod()
        vector<MI> fc, ifc;
        void init(int n) {
            fc.resize(n + 1), ifc.resize(n + 1), fc[0] = 1;
            REP(i, 1, n) fc[i] = fc[i - 1] * i;
            ifc[n] = fc[n].inv();
            DEP(i, n, 1) ifc[i - 1] = ifc[i] * i;
        }
        MI operator () (LL n, LL m) {
            if (m > n || m < 0 || n < 0) return 0;
            if (n < P && m < P) { assert(n < SZ(fc)); return fc[n] * ifc[m] * ifc[n - m]; }
            return (!n ? 1 : (*this)(n / P, m / P) * (*this)(n % P, m % P));
        }
        #undef P
    };
    namespace Z {
        const int mod = 0;
        using MI = mint<mod>; using math::qpow; Comb<MI> C;
        MI fac(int x) { assert(x >= 0 && x < SZ(C.fc)); return C.fc[x]; }
        MI ifc(int x) { assert(x >= 0 && x < SZ(C.ifc)); return C.ifc[x]; }
        MI inv(int x) { assert(x && x < SZ(C.fc)); return C.ifc[x] * C.fc[x - 1]; }
        MI sab(int x, int y) { return (!y ? !x : C(x + y - 1, y - 1)); }
    }
}
namespace Milkcat {
    using namespace math::Z;
    typedef long long LL;
    typedef pair<LL, LL> pii;
    const int N = 15;
    int d, P, p0, p1, b[N]; MI c, A[N][N];
    void add(int x, int y, int z) { // a[z]=a[x]+a[y]
        cout << "+ " << x << ' ' << y << ' ' << z << '\n';
    }
    void powd(int x, int y) { // a[z]=a[x]^d
        cout << "^ " << x << ' ' << y << '\n';
    }
    void copy(int x, int y) { // a[y]=a[x]
        add(x, p0, y);
    }
    void mulc(int x, int y, int z) { // a[z]+=a[x]*y
        int p = 4997; copy(x, p);
        for (; y; y >>= 1) {
            if (y & 1) add(z, p, z);
            add(p, p, p);
        }
    }
    void sqr(int x, int y) { // a[y]+=a[x]*a[x]
        REP(i, 1, d) b[i] = 4997 - i;
        add(x, p1, b[1]), mulc(p1, (-c).val(), y);
        REP(i, 2, d) add(b[i - 1], p1, b[i]);
        REP(i, 1, d) powd(b[i], b[i]);
        REP(i, 1, d) mulc(b[i], A[i][d + 1].val(), y);
    }
    void mul(int x, int y, int z) { // a[z]+=a[x]*a[y]
        int p = 4986, q = 4985, r = 4984;
        copy(p0, q), copy(p0, r), add(x, y, p), sqr(p, r);
        copy(x, p), sqr(p, q), copy(y, p), sqr(p, q);
        mulc(q, P - 1, r), mulc(r, (P + 1) / 2, z);
    }
    void init() {
        int p = 4999, q = 5000;
        for (int x = P - 1; x; x >>= 1) {
            if (x & 1) add(q, p, q);
            add(p, p, p);
        }
        p0 = 5000, p1 = 4998, C.init(d);
        REP(i, 1, d) {
            A[i][d + 1] = (i == 2);
            REP(j, 1, d) A[i][j] = C(d, i) * qpow((MI)j, d - i);
        }
        REP(k, 1, d) {
            int t = 0;
            REP(i, 1, d) t = (A[i][k] != 0 ? i : t);
            REP(i, 1, d + 1) swap(A[k][i], A[t][i]);
            DEP(i, d + 1, k) A[k][i] /= A[k][k];
            REP(i, 1, d) {
                if (i == k) continue;
                DEP(j, d + 1, k) A[i][j] -= A[i][k] * A[k][j];
            }
        }
        REP(i, 1, d) c += qpow((MI)i, d) * A[i][d + 1];
    }
    int main() {
        cin >> d >> P, MI::setmod(P);
        init(), copy(p0, 3), mul(1, 2, 3);
        cout << "f 3\n";
        return 0;
    }
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    int T = 1;
    while (T --) Milkcat::main();
    return 0;
}

:::