結果
| 問題 | No.1141 田グリッド |
| ユーザー |
 Ricky_pon
|
| 提出日時 | 2020-07-31 22:04:17 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,088 ms / 2,000 ms |
| コード長 | 7,091 bytes |
| コンパイル時間 | 2,282 ms |
| コンパイル使用メモリ | 207,160 KB |
| 最終ジャッジ日時 | 2025-01-12 10:10:40 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 31 |
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:226:34: warning: format ‘%lld’ expects argument of type ‘long long int*’, but argument 2 has type ‘mint*’ {aka ‘modint<1000000007>*’} [-Wformat=]
226 | rep(i, h)rep(j, w) scanf("%lld", &b[i][j]);
| ~~~^ ~~~~~~~~
| | |
| | mint* {aka modint<1000000007>*}
| long long int*
main.cpp:261:20: warning: format ‘%lld’ expects argument of type ‘long long int’, but argument 2 has type ‘modint<1000000007>::i64’ {aka ‘long int’} [-Wformat=]
261 | printf("%lld\n", ans.a);
| ~~~^ ~~~~~
| | |
| | modint<1000000007>::i64 {aka long int}
| long long int
| %ld
main.cpp:224:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
224 | scanf("%d%d", &h, &w);
| ~~~~~^~~~~~~~~~~~~~~~
main.cpp:226:29: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
226 | rep(i, h)rep(j, w) scanf("%lld", &b[i][j]);
| ~~~~~^~~~~~~~~~~~~~~~~~
main.cpp:249:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
249 | scanf("%d", &q);
| ~~~~~^~~~~~~~~~
main.cpp:252:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
252 | scanf("%d%d", &r, &c);
| ~~~~~^~~~~~~~~~~~~~~~
ソースコード
#include <bits/stdc++.h>#define For(i, a, b) for(int (i)=(int)(a); (i)<(int)(b); ++(i))#define rFor(i, a, b) for(int (i)=(int)(a)-1; (i)>=(int)(b); --(i))#define rep(i, n) For((i), 0, (n))#define rrep(i, n) rFor((i), (n), 0)#define fi first#define se secondusing namespace std;typedef long long lint;typedef unsigned long long ulint;typedef pair<int, int> pii;typedef pair<lint, lint> pll;template<class T> bool chmax(T &a, const T &b){if(a<b){a=b; return true;} return false;}template<class T> bool chmin(T &a, const T &b){if(a>b){a=b; return true;} return false;}template<class T> T div_floor(T a, T b){if(b < 0) a *= -1, b *= -1;return a>=0 ? a/b : (a+1)/b-1;}template<class T> T div_ceil(T a, T b){if(b < 0) a *= -1, b *= -1;return a>0 ? (a-1)/b+1 : a/b;}constexpr lint mod = 1000000007;constexpr lint INF = mod * mod;constexpr int MAX = 500010;template<int_fast64_t MOD> struct modint{using i64=int_fast64_t;i64 a;modint(const i64 a_=0): a(a_){if(a>MOD) a%=MOD;else if(a<0) (a%=MOD)+=MOD;}modint inv(){i64 t=1, n=MOD-2, x=a;while(n){if(n&1) (t*=x)%=MOD;(x*=x)%=MOD;n>>=1;}modint ret(t);return ret;}bool operator==(const modint x) const{return a==x.a;}bool operator!=(const modint x) const{return a!=x.a;}modint operator+(const modint x) const{return modint(*this)+=x;}modint operator-(const modint x) const{return modint(*this)-=x;}modint operator*(const modint x) const{return modint(*this)*=x;}modint operator/(const modint x) const{return modint(*this)/=x;}modint operator^(const lint x) const{return modint(*this)^=x;}modint &operator+=(const modint &x){a+=x.a;if(a>=MOD) a-=MOD;return *this;}modint &operator-=(const modint &x){a-=x.a;if(a<0) a+=MOD;return *this;}modint &operator*=(const modint &x){(a*=x.a)%=MOD;return *this;}modint &operator/=(modint x){(a*=x.inv().a)%=MOD;return *this;}modint &operator^=(lint n){i64 ret=1;while(n){if(n&1) (ret*=a)%=MOD;(a*=a)%=MOD;n>>=1;}a=ret;return *this;}modint operator-() const{return modint(0)-*this;}modint &operator++(){return *this+=1;}modint &operator--(){return *this-=1;}bool operator<(const modint x) const{return a<x.a;}};using mint=modint<1000000007>;vector<mint> fact;vector<mint> revfact;void setfact(int n){fact.resize(n+1); revfact.resize(n+1);fact[0] = 1;rep(i, n) fact[i+1] = fact[i] * mint(i+1);revfact[n] = fact[n].inv();for(int i=n-1; i>=0; i--) revfact[i] = revfact[i+1] * mint(i+1);}mint getC(int n, int r){if(n<r) return 0;return fact[n] * revfact[r] * revfact[n-r];}template<typename T, typename E, typename F, typename G>struct SegTree{int sz = 1, seq_sz;T et;F f;G g;vector<T> node;SegTree(int sz_, T et, F f, G g): seq_sz(sz_), et(et), f(f), g(g){while(sz<sz_) sz <<= 1;node.resize(sz<<1, et);}void build(vector<T> &a){rep(i, a.size()) node[i+sz] = a[i];rFor(i, sz, 1) node[i] = f(node[i<<1], node[(i<<1)+1]);}void build(T x){rep(i, seq_sz) node[i+sz] = x;rFor(i, sz, 1) node[i] = f(node[i<<1], node[(i<<1)+1]);}void update(int i, E x){i += sz;node[i] = g(node[i], x);i >>= 1;while(i){node[i] = f(node[i<<1], node[(i<<1)+1]);i >>= 1;}}T query(int l, int r){T vl = et, vr = et;for(l+=sz, r+=sz; l<r; l>>=1, r>>=1){if(l&1) vl = f(vl, node[l++]);if(r&1) vr = f(node[--r], vr);}return f(vl, vr);}int search_left(int l, const T val, function<bool(T, T)> cmp, function<bool(T, T)> check){T sum = et;for(l+=sz; ; l>>=1){if(check(f(sum, node[l]), val)){while(l < sz){if(check(f(sum, node[l<<1]), val)) l <<= 1;else{sum = f(sum, node[l<<1]);l = (l<<1) + 1;}}return l-sz;}if(__builtin_popcount(l+1) == 1) return seq_sz;if(l&1) sum = f(sum, node[l++]);}}int search_right(int r, const T val, function<bool(T, T)> cmp, function<bool(T, T)> check){T sum = et;for(r+=sz; ; r>>=1){if(check(f(sum, node[r]), val)){while(r < sz){if(check(f(node[(r<<1)+1], sum), val)) r = (r<<1) + 1;else{sum = f(node[(r<<1)+1], sum);r<<=1;}}return r-sz;}if(__builtin_popcount(r) == 1) return -1;if(!(r&1)) sum = f(node[r--], sum);}}int lower_bound_left(int l, const T val, function<bool(T, T)> cmp=less<>()){auto check = [&cmp](auto a, auto b){return !cmp(a, b);};return search_left(l, val, cmp, check);}int upper_bound_left(int l, const T val, function<bool(T, T)> cmp=less<>()){auto check = [&cmp](auto a, auto b){return cmp(b, a);};return search_left(l, val, cmp, check);}int lower_bound_right(int l, const T val, function<bool(T, T)> cmp=greater<>()){auto check = [&cmp](auto a, auto b){return !cmp(b, a);};return search_right(l, val, cmp, check);}int upper_bound_right(int l, const T val, function<bool(T, T)> cmp=greater<>()){auto check = [&cmp](auto a, auto b){return cmp(a, b);};return search_right(l, val, cmp, check);}};int main(){int h, w;scanf("%d%d", &h, &w);mint b[h][w];rep(i, h)rep(j, w) scanf("%lld", &b[i][j]);bool trans = (h > w);vector<vector<mint>> a;if(trans){a.resize(w);rep(i, w){a[i].resize(h);rep(j, h) a[i][j] = b[j][i];}swap(h, w);}else{a.resize(h);rep(i, h){a[i].resize(w);rep(j, w) a[i][j] = b[i][j];}}vector<SegTree<mint, mint, decltype(multiplies<>()), decltype(multiplies<>())>> st(h, {w, 1, multiplies<>(), multiplies<>()});rep(i, h) st[i].build(a[i]);int q;scanf("%d", &q);rep(_, q){int r, c;scanf("%d%d", &r, &c);--r; --c;if(trans) swap(r, c);mint ans = 1;rep(i, h)if(i != r){ans *= st[i].query(0, c);ans *= st[i].query(c+1, w);if(ans == 0) break;}printf("%lld\n", ans.a);}}