結果

問題 No.599 回文かい
コンテスト
ユーザー zscoder
提出日時 2017-11-30 20:45:14
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 233 ms / 4,000 ms
コード長 2,154 bytes
コンパイル時間 3,218 ms
コンパイル使用メモリ 181,980 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-27 15:16:24
合計ジャッジ時間 3,325 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

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