結果
問題 | No.599 回文かい |
ユーザー |
|
提出日時 | 2017-11-24 23:10:09 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 88 ms / 4,000 ms |
コード長 | 786 bytes |
コンパイル時間 | 1,432 ms |
コンパイル使用メモリ | 160,672 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-27 08:00:06 |
合計ジャッジ時間 | 2,197 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
ソースコード
#include <bits/stdc++.h> #define MOD 1000000007LL using namespace std; typedef long long ll; typedef pair<int,int> P; ll dp[10001]; ll Bp[10001]; ll hash2[10001]; ll B=103; int main(void){ int n; string str; cin >> str; n=str.size(); Bp[0]=1; for(int i=0;i<n;i++){ hash2[i+1]=hash2[i]*B%MOD; hash2[i+1]+=(ll)(str[i]-'a'); hash2[i+1]%=MOD; Bp[i+1]=Bp[i]*B%MOD; } memset(dp,0,sizeof(dp)); dp[0]=1; ll ans=0; for(int i=0;i<n;i++){ if(dp[i]>0LL){ ans=(ans+dp[i])%MOD; int rest=n-i*2; for(int len=0;len<rest/2;len++){ ll ah=(hash2[i+len+1]-hash2[i]*Bp[len+1]%MOD+MOD)%MOD; ll bh=(hash2[n-i]-hash2[n-i-len-1]*Bp[len+1]%MOD+MOD)%MOD; if(ah==bh){ dp[i+len+1]+=dp[i]; dp[i+len+1]%=MOD; } } } } printf("%lld\n",ans); return 0; }