#define _USE_MATH_DEFINES #pragma region include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include //// //#include // #pragma endregion //#include ///////// #pragma region typedef typedef long long LL; typedef long double LD; typedef unsigned long long ULL; #pragma endregion //typedef ////定数 const int INF = (int)1e9; const LL MOD = (LL)1e9+7; const LL LINF = (LL)4e18+20; const LD PI = acos(-1.0); const double EPS = 1e-9; ///////// using namespace::std; ///////// #pragma region Math #pragma region long long ext_gcd(long long a,long long b,long long& x,long long& y){ if(b==0){ x=1;y=0;return a; } long long q = a/b; long long g = ext_gcd(b,a-q*b,x,y); x = x - q*y; swap(x,y); return g; } template inline T gcd(T a, T b){return b ? gcd(b, a % b) : a;} #pragma endregion // 最大公約数 gcd #pragma region template inline T lcm(T a, T b){return a / gcd(a, b) * b;} #pragma endregion // 最小公倍数 lcm #pragma region long long invMod(long long a,long long m=MOD){ long long x,y; ext_gcd(a,m,x,y); x %= m; if(x<0) x += m; return x; } /* LL powMod(LL x,LL e,LL mod=MOD){ LL prod = 1%mod; for(int i=63;i>=0;--i){ prod = prod*prod % mod; if(e&1LL<>= 1; } return ans; } /* LL mod_inverse(LL num,LL mod=MOD){ return powMod(num,MOD-2,MOD); }*/ #pragma endregion //繰り返し二乗法 powMod #pragma region template vector getDivisor(T n){ vector v; for(int i=1;i*i<=n;++i){ if( n%i == 0 ){ v.push_back(i); if( i != n/i ){//平方数で重複して数えないように v.push_back(n/i); } } } sort(v.begin(), v.end()); return v; } #pragma endregion //約数列挙 getDivisor(n):O(√n) #pragma endregion //math //Utility:便利な奴 #pragma region template void UNIQUE(vector& vec){ sort(vec.begin(),vec.end()); vec.erase(unique(vec.begin(),vec.end()),vec.end() ); } #pragma endregion // sort erase unique //////////////////////////////// #pragma region long long bitcount64(long long bits) { bits = (bits & 0x5555555555555555) + (bits >> 1 & 0x5555555555555555); bits = (bits & 0x3333333333333333) + (bits >> 2 & 0x3333333333333333); bits = (bits & 0x0f0f0f0f0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f0f0f0f0f); bits = (bits & 0x00ff00ff00ff00ff) + (bits >> 8 & 0x00ff00ff00ff00ff); bits = (bits & 0x0000ffff0000ffff) + (bits >>16 & 0x0000ffff0000ffff); return (bits & 0x00000000ffffffff) + (bits >>32 & 0x00000000ffffffff); } #pragma endregion //その他 //////////////////////////////// struct edge_base{int to;LL cost;}; edge_base make_edge_base(int to,LL cost){ edge_base ret = {to,cost}; return ret; } #pragma region GRL #pragma region //グラフ template void dijkstra(int root,int V,vector& dist,vector& prev, vector< vector > G ){ priority_queue,vector >,greater > > que; dist.assign(V,LINF); prev.assign(V,-1); dist[root] = 0; que.push(pair(0,root));//距離、頂点番号 while( !que.empty() ){ pair p = que.top();que.pop(); int v = p.second; if( dist[v] < p.first ) continue; for(int i=0;i < (int)G[v].size();++i){ EDGE e = G[v][i]; if( dist[e.to] > dist[v] + e.cost ){ dist[e.to] = dist[v] + e.cost; prev[e.to] = v; que.push(pair(dist[e.to],e.to)); } } } } //経路復元,dijkstraにprev入れた //http://ronly.hatenablog.com/entry/2017/06/17/161641 vector get_path(vector& prev,int t){ vector path; while(t!=-1){ path.push_back( t ); t = prev[t]; } reverse(path.begin(),path.end()); return path; } #pragma endregion //ダイクストラ法:O(|E|log|V|) #pragma region //グラフ void warshall_floyd(vector >& dist,int V,const LL inf=LINF){ for(int k=0;k= inf ) continue; for(int j=0;j= inf )continue; dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j]); } } } } #pragma endregion //ワーシャルフロイド:O(|V|**3) #pragma region namespace FLOW{ //vector< vector > G; struct edge_flow : public edge_base{ LL cap;//LD cap;// int rev; }; edge_flow make_edge_flow(int to,LL cap,int rev,LL cost=1){ //edge_flow make_edge_flow(int to,LD cap,int rev,LL cost=1){ edge_flow ret; ret.to = to; ret.cost = cost; ret.cap = cap; ret.rev = rev; return ret; } //* class Graph{ public: int V; vector< vector > G; vector< LL > dist; vector< int > iter; vector< bool > used; void init(int v){ V = v; G.resize(V); } void reset(){ iter.assign(V,0); used.assign(V,false); } //directed graph void add_edge(int from,int to,LL cap){ G[from].push_back( FLOW::make_edge_flow(to,cap,G[to].size()) ); G[to].push_back( FLOW::make_edge_flow(from,0,G[from].size()-1) ); } private: //sから最短距離をBFSで計算する void bfs(int s){//許容量もチェックしている queue que; dist = vector(V,-1); dist[s] = 0; que.push(s); while(!que.empty()){ int v = que.front();que.pop(); for(int i=0;i<(int)G[v].size();++i){ edge_flow &e = G[v][i]; if( e.cap > 0 && dist[e.to] < 0 ){ dist[e.to] = dist[v] + 1; que.push(e.to); } } } } private: //増加パスをDFSで探す LL dfs(int v,int t,LL f){ if( v==t ) return f; for(int &i = iter[v];i<(int)G[v].size();++i){//? FLOW::edge_flow &e = G[v][i]; if( e.cap>0 && dist[v] < dist[e.to]){ LL d = this->dfs(e.to, t, min(f,e.cap) ); if( d > 0){ e.cap -= d; G[e.to][e.rev].cap += d; return d; } } } return 0; } public: //sからtへの最大流量を求める LL max_flow(int s,int t){ LL flow = 0; for(;;){ this->bfs(s); if( dist[t] < 0 ) return flow; iter = vector(V,0); LL f = this->dfs(s,t,LINF); do{ flow += f; f = this->dfs(s,t,LINF); }while( f > 0 ); } } }; //*/ } #pragma endregion //dinic :O(|E||V|^2) #pragma region //グラフ bool is_bipartite(int v,int c,vector< vector >& G,vector& Color){ Color[v] = c; for(int i=0;i < (int)G[v].size();++i){//隣接グラフ if(Color[ G[v][i] ] == c ) return false; if(Color[ G[v][i] ] == 0 && !is_bipartite(G[v][i],-c,G,Color) ){ return false; } } return true; } bool is_bipartite(int Root,vector< vector >& Graph){ int GraphSize = Graph.size(); vector Color(GraphSize,0); const int ColorNo = 1; return is_bipartite(Root,ColorNo,Graph,Color); } #pragma endregion //二部グラフチェック is_bipartite(root,GraphList) #pragma region namespace matching{ //https://beta.atcoder.jp/contests/soundhound2018/tasks/soundhound2018_c int V; //頂点数 vector< vector > G;//グラフ vector match;//match[i]:頂点[i]がどことマッチされているか vector used;// void add_edge(int u,int v){ G[u].push_back(v); G[v].push_back(u); } bool dfs(int v){ /* https://mathtrain.jp/bipartitematching 未マッチ辺・マッチ辺・未マッチ辺 これを マッチ辺・未マッチ辺・マッチ辺 に変えると 1マッチが2マッチになる。 未[済未] 増加路を求めている。 */ used[v] = true;//dfsのroot前に初期化される int size = G[v].size(); for(int i=0;i(V,-1);//未マッチ状態に初期化 for(int v=0;v(V,false); if( dfs(v) ){ ++res; } } } return res; } } #pragma endregion //二部グラフの最大マッチング bipartite_matching() #pragma endregion // #pragma region vector< vector > NCK;//初期値:0 //http://sugarknri.hatenablog.com/entry/2016/07/16/165715 void makeinv(vector& inv,const LL P){ int i; //const int varMAX = max(100000,(int)inv.size()); const int varMAX = max(300010,(int)inv.size()); inv = vector( varMAX+1,0); inv[1]=1; for(i=2;i<=varMAX;i++){ inv[i] = (inv[P%i] * (P-P/i)%P ) % P;//OVF //inv[i] = powMod(i,P-2,P); } } LL nCk(LL N,LL k,LL mod = MOD){ static vector inv;//modの逆元 if( inv.size() == 0 ){ makeinv(inv,mod);//modは素数を入れる } k = min(k,N-k); if( k < 0 || k > N){return 0;} if( k == 0 ){return 1;} if( k == 1 ){return N%mod;} LL ret = 1; for(int i=1;i<=k;++i){ ret = (ret * ((N+1-i)%mod) )%mod;//ret*N:OVF ret = (ret * inv[i] )%mod; } return ret; } LL nCk_once(LL N,LL k,LL mod = MOD){//modは素数 k = min(k,N-k); if( k < 0 || k > N ){return 0;} if( k == 0 ){return 1;} if( k == 1 ){return N%mod;} LL ret = 1; LL A=1; for(LL i=0;i parent; vector count; vector< vector > GList; UnionFind(int n){ cNum = n; parent = vector(n); count = vector(n,1); GList.resize(n); for(int i=0;i bit; public: BITree(int n){ N = n; bit = vector(N+1,0);//1-index } void add(int a,LL w){//aにwを足す if( a <= 0 || N < a) return;//a:[1,N] for(int i=a;i<=N;i += i & -i){ bit[i] += w; } } LL sum(int a){//[1,a]の和,a:[1,N] /* 1番目からa番目までの和、1-index */ LL ret = 0; if( a > N ) a = N; for(int i=a; i > 0; i -= i & -i){ ret += bit[i]; } return ret; } }; #pragma endregion //BIndexTree #pragma region template class segmentTree{ int N;//要素数 vector< T > dat1; T VAL_E;//初期値 T VAL_NULL;//空の値 public: segmentTree(){}; /*segmentTree(int n,T val_E ):N(n),VAL_E(val_E){ dat1.resize(2*n); dat1.assign(2*n,val_E);//初期化 }*/ void init(int n,T val_E,T val_N){ N = n; VAL_E = val_E; VAL_NULL = val_N; int size = 2; while(size0){ i = (i-1)/2; dat1[i] = SELECT(dat1[i*2+1],dat1[i*2+2]); } } //区間[L,R)のSELECT /* 調べている範囲[a,b),階数k,見る場所[L,R) */ T query(int a,int b,int k,int L,int R){ if( R<=a || b<=L ){ return VAL_E;//交差しない } if( a<=L && R<=b && dat1[k] != VAL_NULL ){ return dat1[k]; } T res = VAL_E; int mid = (L+R)/2; if( a < mid ) res = SELECT(res,query(a,b,k*2+1,L,mid) ); if( mid < b ) res = SELECT(res,query(a,b,k*2+2,mid,R) ); return res; } T query(int L,int R){ return query(L,R,0,0,N); } }; #pragma endregion //segment_tree #pragma region //行列の積 namespace mymat{ LL matMOD = MOD;//初期値10^9 + 7 }; template vector< vector > operator*( vector >& A,vector< vector >& B){ LL mod = mymat::matMOD; int R = A.size(); int cen = A[0].size(); int C = B[0].size(); vector< vector > ans(R,vector(C,0) ); for(int row=0;row vector< vector > powMod(const vector< vector >& mat,LL N,LL mod=MOD){ mymat::matMOD = mod; int R = mat.size(); int C = mat[0].size(); //R==C vector< vector > I(R,vector(C,0));//単位元 for(int i=0;i > mul(R,vector(C)),ans(R,vector(C)); ans = I; mul = mat; while(N){ if( N & 1 ){ ans = ans*mul; } N >>= 1; mul = mul*mul; } return ans; } #pragma endregion //行列 #pragma region #include namespace TIME{ clock_t start,end; void time_start(){ start = clock(); } void time_set(int t){ end = start + t; } bool check(){ return clock() < end; } /* unsigned long long get_cycle(){ return __rdtsc(); } unsigned long long start,limit; void time_start(){ start = get_cycle(); } //あたいをーさぐらないとーだめー void time_set(unsigned long long num){limit = num;} bool check(){return (get_cycle() < start+limit);} */ } #pragma endregion //時間計測 #pragma region namespace RAND{ unsigned long xor128(){ static unsigned long x=123456789,y=362436069,z=521288629,w=88675123; unsigned long t; t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) ); } LL getRAND(LL P){ return ((xor128()%P)+P)%P; } } #pragma endregion //乱数 #pragma region #pragma endregion // //////////////////////// int R,C; int index(int r,int c){ return r*C+c; } void solve(){ cin>>R>>C; vector > fld(R,vector(C,0)); for(int r=0;r>fld[r][c]; } } UnionFind uf(R*C); for(int r=0;r useRoot(R*C,false); for(int r=0;r