Submission #637865

#	Time	Username	Problem	Language	Result	Execution time	Memory
637865		TAMREF	흑백 이미지 찾기 (kriii3_G)	C++17	101 / 101	2327 ms	126552 KiB

G

#include <bits/stdc++.h>
#define va first
#define vb second
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
#define pp push_back
#define ep emplace_back
#define all(v) (v).begin(),(v).end()
#define szz(v) ((int)(v).size())
#define bi_pc __builtin_popcount
#define bi_pcll __builtin_popcountll
#define bi_tz __builtin_ctz
#define bi_tzll __builtin_ctzll
#define fio ios_base::sync_with_stdio(0);cin.tie(0);
#ifdef TAMREF
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#define debug(...) 42
#endif
using namespace std;
using ll = long long; using lf = long double; 
using pii = pair<int,int>; using ppi = pair<int,pii>;
using pll = pair<ll,ll>; using pff = pair<lf,lf>;
using ti = tuple<int,int,int>;
using base = complex<double>;
const lf PI = 3.14159265358979323846264338L;
template <typename T>
inline T umax(T& u, T v){return u = max(u, v);}
template <typename T>
inline T umin(T& u, T v){return u = min(u, v);}
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class> struct is_container : false_type {};
template<class... Ts> struct is_container<vector<Ts...>> : true_type {};
template<class... Ts> struct is_container<map<Ts...>> : true_type {};
template<class... Ts> struct is_container<unordered_map<Ts...>> : true_type {};
template<class... Ts> struct is_container<set<Ts...>> : true_type {};
template<class... Ts> struct is_container<unordered_set<Ts...>> : true_type {};
template<class... Ts> struct is_container<multiset<Ts...>> : true_type {};
template<class... Ts> struct is_container<unordered_multiset<Ts...>> : true_type {};
template<class T, class = typename enable_if<is_container<T>::value>::type>
ostream& operator<<(ostream &o, T x) {
  #ifndef TAMREF
  return o;
  #endif
  int f = 1;
  o << "{";
  for (auto y : x) {
    o << (f ? "" : ", ") << y;
    f = 0;
  }
  return o << "}\n";
}
template<class T, class U>
ostream& operator<<(ostream &o, pair<T, U> x) {
  #ifndef TAMREF
  return o;
  #endif
  return o << "(" << x.first << ", " << x.second << ")";
}

template<ll mod>
struct NTT{
  using ll = long long;
      inline ll pw(ll x, ll n) {
      ll ret = 1, pv = x;
      for(; n; n >>= 1){
          if(n & 1) ret = ret * pv % mod;
          pv = pv * pv % mod;
      }
      return ret;
  }

  inline ll multInv(ll x){
      return pw(x, mod - 2);
  }
  void ntt(vector<ll>& a, bool inv){
      const int w = 3; //for mod = 998244353
      int n = szz(a), j = 0;
      vector<ll> roots(n/2);
      for(int i = 1; i < n; i++){
          int b = (n >> 1);
          while(j >= b) {
              j -= b; b >>= 1;
          }
          j += b;
          if(i < j) swap(a[i], a[j]);
      }
      ll ang = pw(w, (mod - 1) / n);
      if(inv) ang = pw(ang, mod - 2);
      for(int i = 0; i < n / 2; i++){
          roots[i] = (i ? roots[i-1] * ang % mod : 1);
      }
      for(int i = 2; i <= n; i <<= 1){
          int step = n / i;
          for(int j = 0; j < n; j += i){
              for(int k = 0; k < i / 2; k++){
                  ll u = a[j + k], v = a[j + k + i/2] * roots[step * k] % mod;
                  a[j + k] = (u + v) % mod;
                  a[j + k + i/2] = (u + mod - v) % mod;
              }
          }
      }
      ll ninv = multInv(n);
      if(inv) for(int i = 0; i < n; i++) a[i] = a[i] * ninv % mod;
  }

  void ntt_row(vector<vector<ll>> &a, bool inv) {
    const int w = 3; //for mod = 998244353
    int n = szz(a), j = 0, m = szz(a[0]);
    vector<ll> roots(n/2);
    for(int i = 1; i < n; i++){
        int b = (n >> 1);
        while(j >= b) {
            j -= b; b >>= 1;
        }
        j += b;
        if(i < j) a[i].swap(a[j]);
    }
    ll ang = pw(w, (mod - 1) / n);
    if(inv) ang = pw(ang, mod - 2);
    for(int i = 0; i < n / 2; i++){
        roots[i] = (i ? roots[i-1] * ang % mod : 1);
    }
    for(int i = 2; i <= n; i <<= 1){
        int step = n / i;
        for(int j = 0; j < n; j += i){
            for(int k = 0; k < i / 2; k++){
                for(int h = 0; h < m; h++) {
                  ll u = a[j + k][h], v = a[j + k + i/2][h] * roots[step * k] % mod;
                  a[j + k][h] = (u + v) % mod;
                  a[j + k + i/2][h] = (u + mod - v) % mod;
                }
            }
        }
    }
    ll ninv = multInv(m);
    if(inv) for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) a[i][j] = a[i][j] * ninv % mod;
  }

  void ntt2d(vector<vector<ll>> &a, bool inv) {
    int n = szz(a);
    for(int i = 0; i < n; i++) ntt(a[i], inv);
    ntt_row(a, inv);
  }

  vector<vector<ll>> mult2d(vector<vector<ll>> a, vector<vector<ll>> b) {
    int n = 2; while(n < szz(a) + szz(b)) n <<= 1;
    int m = 2; while(m < szz(a[0]) + szz(b[0])) m <<= 1;
    a.resize(n); b.resize(n);
    for(int i = 0; i < n; i++) a[i].resize(m);
    for(int i = 0; i < n; i++) b[i].resize(m);
    ntt2d(a, false); ntt2d(b, false);
    for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) a[i][j] = a[i][j] * b[i][j] % mod;
    ntt2d(a, true);
    return a;
  }

  vector<ll> mult(vector<ll> &a, vector<ll> &b){
      vector<ll> fa(all(a)), fb(all(b));
      int n = 2; while(n < szz(a) + szz(b)) n <<= 1;
      fa.resize(n); fb.resize(n);
      ntt(fa, false); ntt(fb, false);
      for(int i = 0; i < n; i++) fa[i] = fa[i] * fb[i] % mod;
      ntt(fa, true);
      return fa;
  }
};

constexpr ll mod1 = 998244353, mod2 = 7 << 26 | 1;
NTT<mod1> n1;
NTT<mod2> n2; 
vector<vector<ll>> a, b;
int n, m, r, c;
const ll tmods[5] = {1000000007, 1000000009, 998244353, 1000000033, 1000000021};
using L = __int128_t;

void merge_by_crt(vector<vector<ll>> &a, vector<vector<ll>> &b) {
  ll inv1 = n2.multInv(mod1), inv2 = n1.multInv(mod2), pmod = mod1 * mod2;
  for(int i = 0; i < szz(a); i++) {
    for(int j = 0; j < szz(b); j++) {
      a[i][j] = (
        __int128_t(a[i][j]) * mod2 * inv2 + __int128_t(b[i][j]) * mod1 * inv1
      ) % pmod;
    }
  }
}

int main(){
  fio;
  cin >> n >> m;
  a = vector<vector<ll>>(n, vector<ll>(m));
  for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) cin >> a[i][j];
  cin >> r >> c;
  b = vector<vector<ll>>(r, vector<ll>(c));
  for(int i = 0; i < r; i++) for(int j = 0; j < c; j++) cin >> b[r-1-i][c-1-j];
  auto ab = n1.mult2d(a, b);
  auto ab2 = n2.mult2d(a, b);
  merge_by_crt(ab, ab2);

  #ifdef TAMREF
  cerr << ab << '\n';
  #endif
  __int128_t asum = 0, a2sum = 0, bsum = 0, b2sum = 0;

  for(int i = 0; i < r; i++) {
    for(int j = 0; j < c; j++) {
      bsum += b[i][j];
      b2sum += b[i][j] * b[i][j];
    }
  }

  ll ans = 0;


  auto compare = [&](int i, int j) {
    bool isConstA = !(a2sum * r * c - asum * asum), 
         isConstB = !(b2sum * r * c - bsum * bsum);

    if(isConstA && !isConstB) return;
    if(isConstA && isConstB) {
      ++ans;
      return;
    }


    L bvar = (b2sum * r * c - bsum * bsum);
    L cov = (L(ab[i + r - 1][j + c - 1]) * r * c - asum * bsum);
    L avar =(a2sum * r * c - asum * asum);
    if(!avar && bvar) return;
    if(!avar && !bvar) {
      ++ans;
      return;
    }

    bool flag = true;
    for(const ll mod : tmods) {
        ll _c = (mod + cov % mod) % mod;
        ll _a = avar % mod, _b = bvar % mod;
        ll diff = (mod + (_c * _c - _a * _b) % mod) % mod;
        if(diff) {
            flag = false;
            break;
        }
    }
    if(flag) ++ans;
    debug("ans = %lld\n", ans);
  };

  for(int k = 0; k + r - 1 < n; k++) {
    asum = a2sum = 0;
    for(int i = 0; i < r; i++) {
      for(int j = 0; j < c; j++) {
        asum += a[k+i][j];
        a2sum += a[k+i][j] * a[k+i][j];
      }
    }

    compare(k, 0);
    for(int j = 1; j + c - 1 < m; j++) {
      for(int i = 0; i < r; i++) {
        asum += a[k+i][j+c-1] - a[k+i][j-1];
        a2sum += a[k+i][j+c-1] * a[k+i][j+c-1] - a[k+i][j-1] * a[k+i][j-1];
      }
      compare(k, j);
    }
  }

  cout << ans << '\n';
}

Compilation message (stderr)

G.cpp: In lambda function:
G.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
G.cpp:247:5: note: in expansion of macro 'debug'
  247 |     debug("ans = %lld\n", ans);
      |     ^~~~~

• Subtask 1: 33 / 33
• Subtask 2: 68 / 68