結果

問題 No.1916 Making Palindrome on Gird
ユーザー じゅんにーじゅんにー
提出日時 2022-04-29 22:39:56
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 89 ms / 3,000 ms
コード長 4,107 bytes
コンパイル時間 2,021 ms
コンパイル使用メモリ 192,028 KB
実行使用メモリ 69,492 KB
最終ジャッジ日時 2023-09-11 14:02:00
合計ジャッジ時間 4,615 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 1 ms
4,376 KB
testcase_06 AC 2 ms
4,380 KB
testcase_07 AC 2 ms
4,380 KB
testcase_08 AC 2 ms
4,376 KB
testcase_09 AC 2 ms
4,380 KB
testcase_10 AC 2 ms
4,380 KB
testcase_11 AC 2 ms
4,500 KB
testcase_12 AC 2 ms
4,380 KB
testcase_13 AC 29 ms
26,684 KB
testcase_14 AC 19 ms
19,556 KB
testcase_15 AC 37 ms
33,352 KB
testcase_16 AC 24 ms
20,940 KB
testcase_17 AC 67 ms
60,076 KB
testcase_18 AC 80 ms
69,436 KB
testcase_19 AC 81 ms
69,424 KB
testcase_20 AC 81 ms
69,368 KB
testcase_21 AC 80 ms
69,420 KB
testcase_22 AC 80 ms
69,452 KB
testcase_23 AC 48 ms
68,384 KB
testcase_24 AC 47 ms
68,124 KB
testcase_25 AC 48 ms
68,072 KB
testcase_26 AC 49 ms
69,368 KB
testcase_27 AC 48 ms
68,584 KB
testcase_28 AC 89 ms
69,424 KB
testcase_29 AC 88 ms
69,364 KB
testcase_30 AC 88 ms
69,376 KB
testcase_31 AC 89 ms
69,380 KB
testcase_32 AC 89 ms
69,492 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(int)(n);i++)
using namespace std;
using ll=long long;
using ld=long double;
using pai=pair<int,int>;
using pall=pair<ll,ll>;
using vint=vector<int>;
using vll=vector<ll>;
using pquel=priority_queue<ll,vector<ll>,greater<ll>>;
using pquei=priority_queue<int,vector<int>,greater<int>>;

ll one=1,zero=0;
const string yes="Yes",no="No";
const ll bip=1000000007,sap=998244353;
const ld pi=3.1415926535897932384626433832;
const int inty=(one<<31)-1;
const ll lly=(one<<63)-1;
unordered_map<ll,ll>uf;
unordered_map<ll,ll>ufo;
void ufi(ll &x){
  if(ufo[x]==0){
    ufo[x]=1;
    uf[x]=x;
  }
  return;
}
void ufm(ll &x,ll &y){
  ufi(x);
  ufi(y);
  queue<ll>q;
  q.push(x);
  q.push(y);
  while(uf[x]!=x){
    x=uf[x];
    q.push(x);
  }
  while(uf[y]!=y){
    y=uf[y];
    q.push(y);
  }
  while(!(q.empty())){
    y=q.front();
    q.pop();
    uf[y]=x;
  }
  return;
}
void uft(ll &x){
  ufi(x);
  ll y;
  queue<ll>q;
  q.push(x);
  while(uf[x]!=x){
    x=uf[x];
    q.push(x);
  }
  while(!(q.empty())){
    y=q.front();
    q.pop();
    uf[y]=x;
  }
  return;
}
ll divi(ll a,ll b){
  b=abs(b);
  a=(a%b+b)%b;
  if(2*a<b)return a;
  return a-b;
}
ll modinv(ll a,ll b){
  if(abs(a)==1)return a;
  return (-b*modinv(divi(b,a),a)+1)/a;
}
ll modpow(ll a,ll b,ll c){
  ll s=1,t=1;
  a%=c;
  for(int i=0;i<64;i++){
    if(b&t){
      s=(s*a)%c;
    }
    a=(a*a)%c;
    t*=2;
  }
  return s;
}
bool issq(ll n){
  if(n<0)return false;
  ll i=sqrt(n);
  while(i*i<=n){
    if(n==i*i)return true;
    i++;
  }
  return false;
}
vector<pair<double,double>>fft(int &n,vector<pair<double,double>>&pol){
  if(n==1)return pol;
  n/=2;
  vector<pair<double,double>>f1(n),f2(n),f3(n*2);
  for(int i=0;i<n;i++){
    f1[i]=pol[2*i];
    f2[i]=pol[2*i+1];
  }
  f1=fft(n,f1);
  f2=fft(n,f2);
  for(int i=0;i<n;i++){
    f3[i].first=f1[i].first+cos(i*pi/n)*f2[i].first-sin(i*pi/n)*f2[i].second;
    f3[i].second=f1[i].second+sin(i*pi/n)*f2[i].first+cos(i*pi/n)*f2[i].second;
  }
  for(int i=0;i<n;i++){
    f3[i+n].first=f1[i].first-cos(i*pi/n)*f2[i].first+sin(i*pi/n)*f2[i].second;
    f3[i+n].second=f1[i].second-sin(i*pi/n)*f2[i].first-cos(i*pi/n)*f2[i].second;
  }
  n*=2;
  return f3;
}
vector<pair<double,double>>invfft(int &n,vector<pair<double,double>>&pol){
  if(n==1)return pol;
  n/=2;
  vector<pair<double,double>>f1(n),f2(n),f3(n*2);
  for(int i=0;i<n;i++){
    f1[i]=pol[2*i];
    f2[i]=pol[2*i+1];
  }
  f1=invfft(n,f1);
  f2=invfft(n,f2);
  for(int i=0;i<n;i++){
    f3[i].first=f1[i].first+cos(i*pi/n)*f2[i].first+sin(i*pi/n)*f2[i].second;
    f3[i].second=f1[i].second-sin(i*pi/n)*f2[i].first+cos(i*pi/n)*f2[i].second;
  }
  for(int i=0;i<n;i++){
    f3[i+n].first=f1[i].first-cos(i*pi/n)*f2[i].first-sin(i*pi/n)*f2[i].second;
    f3[i+n].second=f1[i].second+sin(i*pi/n)*f2[i].first-cos(i*pi/n)*f2[i].second;
  }
  n*=2;
  return f3;
}

int main(){
	int h,w;
	ll ans=0;
	cin>>h>>w;
	vector<string>v(h+2);
	rep(i,h){
		cin>>v[i];
	}
	vector<vector<vll>>dp(h+2,vector<vll>(w+2,vll(h+2)));
	if(v[0][0]==v[h-1][w-1]){
		dp[0][0][0]=1;
	}
	else{
		cout<<0<<endl;
		return 0;
	}
	for(int i=0;i<=(h+w)/2-1;i++){
		for(int j=0;j<=i;j++){
			if(j>=h)break;
			if(i-j>=w)continue;
			for(int k=0;k<=i;k++){
				if(k>=h)break;
				if(i-k>=w)continue;
				if(v[j][i-j]==v[h-1-k][w-1-i+k]){
					if(j>0){
						if(k>0){
							dp[j][i-j][k]=(dp[j][i-j][k]+dp[j-1][i-j][k-1])%bip;
						}
						if(i-k>0){
							dp[j][i-j][k]=(dp[j][i-j][k]+dp[j-1][i-j][k])%bip;
						}
					}
					if(i-j>0){
						if(k>0){
							dp[j][i-j][k]=(dp[j][i-j][k]+dp[j][i-j-1][k-1])%bip;
						}
						if(i-k>0){
							dp[j][i-j][k]=(dp[j][i-j][k]+dp[j][i-j-1][k])%bip;
						}
					}
				}
			}
		}
	}
	if((h+w)%2==0){
		for(int i=0;i<h+w;i++){
			if((i<h)&&((h+w)/2-1-i<w)&&((h+w)/2-1-i>=0)){
				ans=(ans+dp[i][(w+h)/2-1-i][h-1-i])%bip;
			}
		}
	}
	else{
		for(int i=0;i<=h+w;i++){
			if((i<h)&&((h+w-1)/2-1-i<w)&&((h+w-1)/2-1-i>=0)){
				ans=(ans+dp[i][(w+h-1)/2-1-i][h-1-i])%bip;
				if(i<h-1){
					ans=(ans+dp[i][(w+h-1)/2-1-i][h-i-2])%bip;
				}
			}
		}
		
	}
	cout<<ans<<endl;
}
0