結果

問題 No.599 回文かい
ユーザー zscoderzscoder
提出日時 2017-11-30 20:45:14
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 236 ms / 4,000 ms
コード長 2,154 bytes
コンパイル時間 2,138 ms
コンパイル使用メモリ 177,360 KB
実行使用メモリ 5,168 KB
最終ジャッジ日時 2023-08-18 10:57:18
合計ジャッジ時間 3,578 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
5,024 KB
testcase_01 AC 3 ms
4,936 KB
testcase_02 AC 3 ms
4,940 KB
testcase_03 AC 3 ms
4,968 KB
testcase_04 AC 3 ms
4,964 KB
testcase_05 AC 3 ms
4,948 KB
testcase_06 AC 3 ms
5,032 KB
testcase_07 AC 3 ms
5,164 KB
testcase_08 AC 4 ms
4,948 KB
testcase_09 AC 4 ms
4,952 KB
testcase_10 AC 84 ms
5,168 KB
testcase_11 AC 50 ms
4,996 KB
testcase_12 AC 93 ms
5,040 KB
testcase_13 AC 54 ms
5,028 KB
testcase_14 AC 144 ms
5,132 KB
testcase_15 AC 157 ms
5,152 KB
testcase_16 AC 220 ms
5,084 KB
testcase_17 AC 236 ms
5,068 KB
testcase_18 AC 3 ms
4,948 KB
testcase_19 AC 3 ms
5,156 KB
testcase_20 AC 3 ms
4,952 KB
evil_0.txt AC 116 ms
5,044 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<ll>::iterator sit;
typedef map<ll,ll>::iterator mit;

const ll MOD = 3000003959;
const int ansMOD=int(1e9+7);
const int C = 2017;
ll add(ll a, ll b)
{
	a+=b;
	while(a>=MOD) a-=MOD;
	return a;
}
 
ll add2(ll a, ll b)
{
	a+=b;
	while(a>=ansMOD) a-=ansMOD;
	return a;
}
 
ll multbig(ll a, ll b)
{
	ll r=0;
	while(b)
	{
		if(b&1) r=add(r,a);
		a=add(a,a);
		b>>=1;
	}
	return r;
}
 
ll mult(ll a, ll b)
{
	ll ans=(a*b)%MOD;
	if(ans<0) ans+=MOD;
	return ans;
}
 
ll hsh(string &s)
{
	ll ans=0;
	for(int i=int(s.length())-1;i>=0;i--)
	{
		ans=mult(ans,C);
		ans+=s[i];
		while(ans>=MOD) ans-=MOD;
	}
	return ans;
}
 
ll modpow(ll a, ll b)
{
	ll r=1;
	while(b)
	{
		if(b&1) r=mult(r,a);
		a=mult(a,a);
		b>>=1;
	}
	return r;
}
 
ll inv(ll a)
{
	return modpow(a,MOD-2);
}
 
ll ipowC[111111];
ll dp[111111];
ll pre[111111];
ll powC[111111];

ll get(int l, int r)
{
	if(l==0) return pre[r];
	else return mult(add(pre[r],MOD-pre[l-1]),ipowC[l]);
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	powC[0]=1;
	ipowC[0]=1;
	ipowC[1]=inv(C); powC[1]=C;
	for(int i=2;i<=100001;i++)
	{
		powC[i]=mult(powC[i-1],C);
		ipowC[i]=mult(ipowC[i-1],ipowC[1]);
	}
	string s; cin>>s;
	for(int i=0;i<s.length();i++)
	{
		pre[i]=mult(powC[i],s[i]);
		if(i>0) pre[i]=add(pre[i],pre[i-1]);
	}
	int n=s.length();
	if(n%2==0)
	{
		dp[(n-1)/2] = 1 + (s[n/2-1]==s[n/2]);
	}
	else
	{
		dp[(n-1)/2] = 1;
	}
	dp[(n+1)/2] = 1;
	for(int i=(n-3)/2;i>=0;i--)
	{
		dp[i] = 1;
		int l = i; int r = n - 1 - i;
		for(int j=l;j<=(n-1)/2;j++)
		{
			if(j>=r-(j-l)) break;
			if(get(l,j)==get(r-(j-l),r))
			{
				dp[i]=add2(dp[i], dp[j+1]);
			}
		}
		//cerr<<i<<' '<<dp[i]<<'\n';
	}
	cout<<dp[0]<<'\n';
}
0