結果
問題 | No.1916 Making Palindrome on Gird |
ユーザー | じゅんにー |
提出日時 | 2022-04-29 22:14:17 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,126 bytes |
コンパイル時間 | 2,211 ms |
コンパイル使用メモリ | 194,584 KB |
実行使用メモリ | 67,840 KB |
最終ジャッジ日時 | 2024-06-29 03:45:16 |
合計ジャッジ時間 | 6,868 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,940 KB |
testcase_02 | AC | 2 ms
6,944 KB |
testcase_03 | WA | - |
testcase_04 | RE | - |
testcase_05 | RE | - |
testcase_06 | RE | - |
testcase_07 | RE | - |
testcase_08 | RE | - |
testcase_09 | RE | - |
testcase_10 | AC | 2 ms
6,944 KB |
testcase_11 | RE | - |
testcase_12 | RE | - |
testcase_13 | RE | - |
testcase_14 | RE | - |
testcase_15 | RE | - |
testcase_16 | RE | - |
testcase_17 | RE | - |
testcase_18 | AC | 79 ms
67,712 KB |
testcase_19 | AC | 79 ms
67,840 KB |
testcase_20 | AC | 82 ms
67,584 KB |
testcase_21 | AC | 80 ms
67,712 KB |
testcase_22 | AC | 80 ms
67,712 KB |
testcase_23 | AC | 52 ms
66,432 KB |
testcase_24 | AC | 51 ms
66,304 KB |
testcase_25 | AC | 51 ms
66,432 KB |
testcase_26 | AC | 53 ms
67,712 KB |
testcase_27 | AC | 55 ms
66,816 KB |
testcase_28 | AC | 90 ms
67,712 KB |
testcase_29 | AC | 90 ms
67,584 KB |
testcase_30 | AC | 89 ms
67,712 KB |
testcase_31 | AC | 89 ms
67,712 KB |
testcase_32 | AC | 89 ms
67,712 KB |
ソースコード
#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); rep(i,h){ cin>>v[i]; } vector<vector<vll>>dp(h,vector<vll>(w,vll(h))); 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(j>h)break; if(i-j>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][(w+h)/2-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][(w+h-1)/2-1-i])%bip; if((h+w+1)/2-1-i<w){ ans=(ans+dp[i][(w+h-1)/2-1-i][(w+h+1)/2-1-i])%bip; } } } } cout<<ans<<endl; }