結果

問題 No.1404 誕生日プレゼント
ユーザー cn_449
提出日時 2020-12-09 00:52:05
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 239 ms / 3,153 ms
コード長 4,112 bytes
コンパイル時間 1,454 ms
コンパイル使用メモリ 143,604 KB
最終ジャッジ日時 2025-01-16 20:18:34
ジャッジサーバーID
（参考情報） 		judge5 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cassert>
#include <complex>
#include <stdio.h>
#include <time.h>
#include <numeric>
#include <random>
#include <unordered_map>
#include <unordered_set>
#define all(a) a.begin(),a.end()
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define pb push_back
#define debug(x) cerr << __LINE__ << ' ' << #x << ':' << (x) << '\n'
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> P;
typedef complex<ld> com;
template<class T> using prique = priority_queue<T, vector<T>, greater<T>>;
constexpr int inf = 1000000010;
constexpr ll INF = 1000000000000000010;
constexpr int mod1e9 = 1000000007;
constexpr int mod998 = 998244353;
constexpr ld eps = 1e-12;
constexpr ld pi = 3.141592653589793238;
constexpr ll ten(int n) { return n ? 10 * ten(n - 1) : 1; };
int dx[] = { 1,0,-1,0,1,1,-1,-1 }; int dy[] = { 0,1,0,-1,1,-1,1,-1 };
void fail() { cout << "-1\n"; exit(0); } void no() { cout << "No\n"; exit(0); }
template<class T, class U> inline bool chmax(T &a, const U &b) { if (a < b) { a = b; return true; } return false; }
template<class T, class U> inline bool chmin(T &a, const U &b) { if (a > b) { a = b; return true; } return false; }
template<class T> istream &operator >> (istream &s, vector<T> &v) { for (auto &e : v) s >> e; return s; }
template<class T> ostream &operator << (ostream &s, const vector<T> &v) { for (auto &e : v) s << e << ' '; return s; }
struct fastio {
    fastio() {
        cin.tie(0); cout.tie(0);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(20);
        cerr << fixed << setprecision(20);
    }
}fastio_;
ll modinv(ll a, ll mod) {
    a %= mod;
    if (a == 0) abort();
    ll b = mod, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= mod;
    if (u < 0) u += mod;
    return u;
}
int main() {
    int n, p;
    cin >> n >> p;
    vector<ll> a(n), b(n);
    rep(i, n) cin >> a[i];
    rep(i, n) cin >> b[i];
    int check = 0;
    check += count(a.begin(), a.end(), 0) == n;
    check += count(b.begin(), b.end(), 0) == n;
    vector<ll> d = a;
    if (check == 2) {
        cout << "0\n";
        return 0;
    }
    if (check == 1) {
        cout << "-1\n";
        return 0;
    }
    if (n == 1) {
        int dbl = 0;
        rep(_, p) {
            a[0] *= 2, a[0] %= p, dbl++;
            if (a[0] == b[0]) break;
        }
        if (a[0] != b[0]) {
            cout << "-1\n";
            return 0;
        }
        cout << dbl + 1 << '\n';
        rep(_, dbl) cout << "1 1 1\n";
        cout << "2\n";
        return 0;
    }
    vector<ll> powtwo;
    int memo = 1;
    rep(_, 2100) {
        powtwo.pb(memo);
        memo *= 2;
        memo %= p;
    }
    vector<P> table(p);
    rep(i, 2100) {
        for (int j = i; j < 2100; j++) {
            table[(powtwo[i] + powtwo[j]) % p] = { i,j };
        }
    }
    vector<P> ans;
    int ax = -1, bx = -1;
    rep(i, n) {
        if (a[i] != 0) ax = i;
        if (b[i] != 0) bx = i;
    }
    if (ax == bx) {
        int ay = ax + 1;
        if (ay == n) ay = 0;
        if (a[ay] == 0) {
            ans.pb({ ay,ax });
            a[ay] += a[ax]; a[ay] %= p;
        }
        ax = ay;
    }
    ll cnt = (b[bx] * modinv(214472, p) % p - a[bx] + p) * modinv(a[ax], p) % p;
    if (cnt) {
        rep(_, table[cnt].first) {
            ans.pb({ ax,ax });
            a[ax] *= 2; a[ax] %= p;
        }
        ans.pb({ bx,ax }); a[bx] += a[ax]; a[bx] %= p;
        rep(_, table[cnt].second - table[cnt].first) {
            ans.pb({ ax,ax });
            a[ax] *= 2; a[ax] %= p;
        }
        ans.pb({ bx,ax }); a[bx] += a[ax]; a[bx] %= p;
    }
    vector<ll> plus(n);
    rep(i, n) plus[i] = (b[i] - a[i] + p) * modinv(a[bx], p) % p;
    vector<vector<ll>> change(2100);
    rep(i, n) {
        if (i == bx || !plus[i]) continue;
        change[table[plus[i]].first].pb(i);
        change[table[plus[i]].second].pb(i);
    }
    rep(i, 2100) {
        for (int j : change[i]) ans.pb({ j,bx });
        ans.pb({ bx,bx });
    }
    assert(ans.size() < p);
    cout << ans.size() + 1 << '\n';
    for (P pa : ans) cout << 1 << ' ' << pa.first + 1 << ' ' << pa.second + 1 << '\n';
    cout << "2\n";
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0