結果

問題 No.936 Are
コンテスト
ユーザー leafirby
提出日時 2019-11-30 01:13:01
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 6,303 bytes
コンパイル時間 2,068 ms
コンパイル使用メモリ 178,244 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-11-21 00:33:01
合計ジャッジ時間 12,594 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 2 WA * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include"bits/stdc++.h"
#define REP(i,n) for(int i=0,i##_len=(n);i<i##_len;++i)
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
#define All(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
constexpr ll mod = 1e9+7;

class mint {
 private:
  ll _num,_mod;
  mint set(ll num){ 
      _num = num ;
      if(_num>=0) _num%=_mod;
      else _num+=(1-(_num+1)/_mod)*_mod; 
      return *this;
  }
  ll _mpow(ll x, ll n){ 
    ll ans = 1;
    while(n != 0){
        if(n&1) ans = ans*x % _mod;
        x = x*x % _mod;
        n = n >> 1;
    }
    return ans;
  }
  ll imod(ll n){return _mpow(n , _mod-2);}
 public:
  mint(){ _num = 0;_mod=mod; }
  mint(ll num){ _mod = mod; _num = (num+(1LL<<25)*mod) % mod; }
  mint(ll num,ll M){ _mod=M;_num=(num+(1LL<<25)*mod)%_mod; }
  mint(const mint &cp){_num=cp._num;_mod=cp._mod;}
  mint operator= (const ll x){ return set(x); }
  mint operator+ (const ll x){ return mint(_num + (x % _mod) , _mod); }
  mint operator- (const ll x){ return mint(_num - (x % _mod), _mod); }
  mint operator* (const ll x){ return mint(_num * (x % _mod) , _mod); }
  mint operator/ (ll x){ return mint(_num * imod(x) , _mod);}
  mint operator+=(const ll x){ return set(_num + (x % _mod)); }
  mint operator-=(const ll x){ return set(_num - (x % _mod)); }
  mint operator*=(const ll x){ return set(_num * (x % _mod)); }
  mint operator/=(ll x){ return set(_num * imod(x));}
  mint operator+ (const mint &x){ return mint(_num + x._num , _mod); }
  mint operator- (const mint &x){ return mint(_num - x._num , _mod);}
  mint operator* (const mint &x){ return mint(_num * x._num , _mod); }
  mint operator/ (mint x){ return mint(_num * imod(x._num) , _mod);}
  mint operator+=(const mint &x){ return set(_num + x._num); }
  mint operator-=(const mint &x){ return set(_num - x._num); }
  mint operator*=(const mint &x){ return set(_num * x._num); }
  mint operator/=(mint x){ return set(_num * imod(x._num));}

  bool operator<(const mint &x)const{return _num<x._num;}
  bool operator==(const mint &x)const{return _num==x._num;}
  bool operator>(const mint &x)const{return _num>x._num;}

  friend mint operator+(ll x,const mint &m){return mint(m._num + (x % m._mod) , m._mod);}
  friend mint operator-(ll x,const mint &m){return mint( (x % m._mod) - m._num , m._mod);}
  friend mint operator*(ll x,const mint &m){return mint(m._num * (x % m._mod) , m._mod);}
  friend mint operator/(ll x,mint m){return mint(m.imod(m._num) * x , m._mod);}

  explicit operator ll() { return _num; }
  explicit operator int() { return (int)_num; }

  friend ostream& operator<<(ostream &os, const mint &x){ os << x._num; return os; }
  friend istream& operator>>(istream &is, mint &x){ll val; is>>val; x.set(val); return is;}
};

bool lose(int l,int r){
    return (l%5==0)&&(r%5==0);
}

void solve(){
    int N,K;
    cin>>N>>K;
    int L[2],R[2];
    cin>>L[0]>>R[0]>>L[1]>>R[1];
    mint dp[2][5][5][5][5]={};
    mint ans=0;
    dp[N][L[1]][R[1]][L[0]][R[0]]=1;
    REP(i,K+1){
        REP(a,5) REP(b,5) REP(c,5) REP(d,5){//a,b:高橋の左右、c,d:lotの左右
            if((a==0&&b==0)||(c==0&&d==0)) continue;
            mint now=dp[N][a][b][c][d];
            if(N&1){
                if(lose(a+c,d)||lose(b+c,d)||lose(c,a+d)||lose(c,b+d)) continue;//勝ち確定なので考えなくていい
                bool divible=false;
                REP(l,5){//詰んでないときは常に分割できる
                    int r=a+b-l;
                    if(r<0) continue;
                    r%=5;
                    if(lose(l,r)||lose(l+c,r)||lose(l+d,r)||lose(l,r+c)||lose(l,r+d))  continue;//分割した結果負けるのはダメ
                    if(r==a&&l==b) continue;//分割の結果入れ替わるのはダメ
                    if(l==a&&r==b) continue;//分割の結果変わらないのはダメ
                    divible=true;
                    dp[0][l][r][c][d]+=now;
                }
                bool attackable=false;
                //行動の結果負けないなら攻撃してよい
                if(a!=0){
                	if(!lose(a+d,b)&&!lose(a+c+a,b)){ 
                		dp[0][a][b][(a+c)%5][d]+=now;
                		attackable=true;
                	}
                    if(!lose(a+c,b)&&!lose(a+d+a,b)){
                    	dp[0][a][b][c][(a+d)%5]+=now;
                    	attackable=true;
                    }
                }
                if(b!=0){
                    if(!lose(a,b+d)&&!lose(a,b+c+b)){
                    	dp[0][a][b][(b+c)%5][d]+=now;
                    	attackable=true;
                    }
                    if(!lose(a,b+c)&&!lose(a,b+d+b)){
                    	dp[0][a][b][c][(b+d)%5]+=now;
                    	attackable=true;
                    }
                }
                //攻撃しかできないし、どう攻撃しても詰んでるなら全ての行動を取る
                if(!divible&&!attackable){
                	if(a!=0){
                		dp[0][a][b][(a+c)%5][d]+=now;
                    	dp[0][a][b][c][(a+d)%5]+=now;
                	}
                	if(b!=0){
                    	dp[0][a][b][(b+c)%5][d]+=now;
                    	dp[0][a][b][c][(b+d)%5]+=now;
                	}
                }
            }
            else{//lot君はあらゆる手を取る
                if(c!=0){
                  if(a)dp[1][(a+c)%5][b][c][d]+=now;
                  if(b)dp[1][a][(b+c)%5][c][d]+=now;
                }
                if(d!=0){
                  if(a)dp[1][(a+d)%5][b][c][d]+=now;
                  if(b)dp[1][a][(b+d)%5][c][d]+=now;
                }
                REP(l,5){
                    int r=c+d-l;
                    if(r<0) continue;
                    r%=5;
                    if(l==0&&r==0) continue;
                    if(r==c&&l==d) continue;//分割の結果
                    if(l==c&&r==d) continue;//分割の結果変わらないのはダメ
                    dp[1][a][b][l][r]+=now;
                }
            }
        }
        REP(a,5) REP(b,5) REP(c,5) REP(d,5){//lot君が勝つときを加算して使いまわすために初期化
            if(a==0&&b==0) ans+=dp[N][a][b][c][d];
            dp[N][a][b][c][d]=0;
        }
        N=1-N;
    }
    cout<<ans<<endl;
}

int main(){
    solve();
}
0