結果
| 問題 | No.936 Are |
| ユーザー |
 otamay6
|
| 提出日時 | 2019-11-28 01:41:00 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 6,906 bytes |
| コンパイル時間 | 2,178 ms |
| コンパイル使用メモリ | 182,324 KB |
| 実行使用メモリ | 6,824 KB |
| 最終ジャッジ日時 | 2024-11-21 00:25:46 |
| 合計ジャッジ時間 | 12,249 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | WA | - |
| testcase_01 | AC | 941 ms
6,820 KB |
| testcase_02 | WA | - |
| testcase_03 | WA | - |
| testcase_04 | WA | - |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | WA | - |
| testcase_08 | AC | 4 ms
6,816 KB |
| testcase_09 | WA | - |
| testcase_10 | WA | - |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | WA | - |
| testcase_14 | WA | - |
| testcase_15 | WA | - |
| testcase_16 | WA | - |
| testcase_17 | WA | - |
| testcase_18 | WA | - |
| testcase_19 | WA | - |
| testcase_20 | WA | - |
| testcase_21 | WA | - |
| testcase_22 | WA | - |
| testcase_23 | WA | - |
| testcase_24 | WA | - |
ソースコード
#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){ //x^n(mod) ←普通にpow(x,n)では溢れてしまうため，随時mod計算 2分累乗法だから早い
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;//勝ち確定なので考えなくていい
if((a==0&&lose(a,b+c)&&lose(a,b+d))||(b==0&&lose(a+c,b)&&lose(a+d,b))){//負けが確定している
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;
}
REP(l,5){
int r=a+b-l;
if(r<0) continue;
r%=5;
if(l==0&&r==0) continue;//分割した結果負けるのはダメ
if(r==a&&l==b) continue;//分割の結果入れ替わるのはダメ
if(l==a&&r==b) continue;//分割の結果変わらないのはダメ
dp[0][l][r][c][d]+=now;
}
}
else if((a==0&&lose(a,b+c))||(b==0&&lose(a+c,b))){//lotの左手を叩けば負けを免れる
if(a!=0) dp[0][a][b][(a+c)%5][d]+=now;
if(b!=0) dp[0][a][b][(b+c)%5][d]+=now;
}
else if((a==0&&lose(a,b+d))||(b==0&&lose(a+d,b))){//lotの右手を叩けば負けを免れる
if(a!=0) dp[0][a][b][c][(a+d)%5]+=now;
if(b!=0) dp[0][a][b][c][(b+d)%5]+=now;
}
else{//変なこと(例えばlotの左手を叩いた結果次のターンで負ける)をしなければ負けない
//0攻撃は問題文中に未定義で、保留
if(!lose(a+c+a,b)&&a!=0) dp[0][a][b][(a+c)%5][d]+=now;
if(!lose(a,b+c+b)&&b!=0) dp[0][a][b][(b+c)%5][d]+=now;
if(!lose(a+d+a,b)&&a!=0) dp[0][a][b][c][(a+d)%5]+=now;
if(!lose(a,b+d+b)&&b!=0) dp[0][a][b][c][(b+d)%5]+=now;
REP(l,5){
int r=a+b-l;
if(r<0) continue;
r%=5;
if(l==0&&r==0) continue;//分割した結果負けるのはダメ
if(r==a&&l==b) continue;//分割の結果入れ替わるのはダメ
if(l==a&&r==b) continue;//分割の結果変わらないのはダメ
dp[0][l][r][c][d]+=now;
}
}
}
else{//lot君はあらゆる手を取る
if(c!=0){
dp[1][(a+c)%5][b][c][d]+=now;
dp[1][a][(b+c)%5][c][d]+=now;
}
if(d!=0){
dp[1][(a+d)%5][b][c][d]+=now;
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();
}