QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#80420#4057. 子串统计LYC_musicCompile Error//C++143.7kb2023-02-23 17:07:312023-02-23 17:07:32

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-23 17:07:32]
  • 评测
查看
  • [2023-02-23 17:07:31]
  • 提交

answer

#include<bits/stdc++.h>
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define inf 1e9
#define mod 998244353
// #define int ll
#define N 500005
using namespace std;
ll fac[N],inv[N];
int Z[N];
string st;
int n;
ll ans;
int ss[N];
ll DP[5005][5005];
int lcp[5005][5005];
inline ll quickPower(ll x,int y)
{
	ll res=1;
	while (y)
	{
		if (y&1) res=res*x%mod;
		x=x*x%mod;
		y>>=1;
	}
	return res;
}
inline ll C(ll x,ll y)
{
	if (x<y||y<0) return 0;
	return fac[x]*inv[y]%mod*inv[x-y]%mod;
}
namespace SAM
{
	int tr[N][27];
	int L[N];
	int pre[N];
	int isc[N];
	int lst=0;
	int siz[N];
	int cnt=0;
	poly G[N];
	int ffa[N][21];
	void insert(int v)
	{
		int now=++cnt;
		// cout<<"ins "<<v<<" "<<lst<<" "<<now<<'\n';
		siz[now]=1;
		L[now]=L[lst]+1;
		Z[L[now]]=now;
		while (1)
		{
			if (!tr[lst][v])
			{
				tr[lst][v]=now;
				if (lst==0) 
				{
					break;
				}
			} else
			{
				int p=tr[lst][v];
				if (L[p]==L[lst]+1)
				{
					pre[now]=p;
					break;
				}
				int np=++cnt;
				pre[np]=pre[p];
				for (int i=0;i<26;i++) tr[np][i]=tr[p][i];
				L[np]=L[lst]+1;
				pre[p]=np;
				while (tr[lst][v]==p)
				{
					tr[lst][v]=np;
					if (lst==0) break;
					lst=pre[lst];
				}
				pre[now]=np;
				break;
			}
			lst=pre[lst];
		}
		lst=now;
	}
	void dfs(int k)
	{
		for (auto u:G[k])
		{
			dfs(u);
			siz[k]+=siz[u];
		}
	}
	void calc()
	{
		for (int i=0;i<=cnt;i++) 
		{
			if (i)
				G[pre[i]].push_back(i);
		}
		dfs(0);
	}
	void work()
	{
		for (int i=1;i<=cnt;i++)
			ffa[i][0]=pre[i];
		for (int i=1;i<=18;i++)
			for (int j=1;j<=cnt;j++)
				ffa[j][i]=ffa[ffa[j][i-1]][i-1];
	}
}
using namespace SAM;
int query(int l,int r)
{
	int now=Z[r];
	for (int i=18;i>=0;i--)
		if (L[ffa[now][i]]>=r-l+1)
		{
			now=ffa[now][i];
		}
	return siz[now];
}	
void BellaKira()
{
	fac[0]=1;
	for (int i=1;i<N;i++) fac[i]=fac[i-1]*i%mod;
	inv[N-1]=quickPower(fac[N-1],mod-2);
	for (int i=N-1;i>=1;i--) inv[i-1]=inv[i]*i%mod;
	cin>>st;
	n=st.size();
	if (n>5000)
	{
		for (auto u:st) SAM::insert(u-'a');
		SAM::calc();
		SAM::work();
		queue<pa>q;
		unordered_map<pa,ll>dp,vis;
		for (int i=1;i<=n;i++) q.push(mp(i,i)),dp[mp(i,i)]=vis[mp(i,i)]=1;
		while (!q.empty())
		{
			pa now=q.front();
			q.pop();
			int v=query(now.fi,now.se);
			if (v==1)
			{
				ans=(ans+dp[now]*C(now.fi-1+n-now.se,now.fi-1)%mod)%mod;
				continue;
			} else
			{
				dp[now]=dp[now]*v%mod;
			}
			
			if (now.fi-1>=1) 
			{
				dp[mp(now.fi-1,now.se)]=(dp[mp(now.fi-1,now.se)]+dp[now])%mod;
				if (!vis[mp(now.fi-1,now.se)])
					q.push(mp(now.fi-1,now.se)),vis[mp(now.fi-1,now.se)]=1;
			}
			if (now.se+1<=n) 
			{
				dp[mp(now.fi,now.se+1)]=(dp[mp(now.fi,now.se+1)]+dp[now])%mod;
				if (!vis[mp(now.fi,now.se+1)])
					q.push(mp(now.fi,now.se+1)),vis[mp(now.fi,now.se+1)]=1;
			}
		}
		cout<<ans<<'\n';
	} else
	{
		for (int i=n;i>=1;i--)	
			for (int j=n;j>=1;j--)
				if (st[i-1]==st[j-1])
					lcp[i][j]=(lcp[i+1][j+1]+1);
		for (int i=1;i<=n;i++)
		{
			for (int j=0;j<=n;j++) ss[j]=0;
			for (int j=1;j<=n;j++)
				ss[lcp[i][j]]++;
				for (int j=n;j>=0;j--)
				ss[j]+=ss[j+1];
			for (int j=i;j<=n;j++)
				lcp[i][j]=ss[j-i+1];	
		}
		queue<pa>q;
		for (int i=1;i<=n;i++)
			DP[i][i]=lcp[i][i];
		for (int len=2;len<=n;len++)
			for (int i=1;i+len-1<=n;i++)
			{
				int j=i+len-1;
				DP[i][j]=(DP[i+1][j]+DP[i][j-1])*lcp[i][j]%mod;
			}
		cout<<DP[1][n]<<'\n';
	}
		
		
}
signed main()
{
	IOS;
	cin.tie(0);
	int T=1;
	while (T--)
	{
		BellaKira();
	}
}
Source code, Language: C++14

Details 

answer.code: In function ‘void BellaKira()’:
answer.code:143:37: error: use of deleted function ‘std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map() [with _Key = std::pair<int, int>; _Tp = long long int; _Hash = std::hash<std::pair<int, int> >; _Pred = std::equal_to<std::pair<int, int> >; _Alloc = std::allocator<std::pair<const std::pair<int, int>, long long int> >]’
  143 |                 unordered_map<pa,ll>dp,vis;
      |                                     ^~
In file included from /usr/include/c++/11/unordered_map:47,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:117,
                 from answer.code:1:
/usr/include/c++/11/bits/unordered_map.h:141:7: note: ‘std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map() [with _Key = std::pair<int, int>; _Tp = long long int; _Hash = std::hash<std::pair<int, int> >; _Pred = std::equal_to<std::pair<int, int> >; _Alloc = std::allocator<std::pair<const std::pair<int, int>, long long int> >]’ is implicitly deleted because the default definition would be ill-formed:
  141 |       unordered_map() = default;
      |       ^~~~~~~~~~~~~
/usr/include/c++/11/bits/unordered_map.h:141:7: error: use of deleted function ‘std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::_Hashtable() [with _Key = std::pair<int, int>; _Value = std::pair<const std::pair<int, int>, long long int>; _Alloc = std::allocator<std::pair<const std::pair<int, int>, long long int> >; _ExtractKey = std::__detail::_Select1st; _Equal = std::equal_to<std::pair<int, int> >; _Hash = std::hash<std::pair<int, int> >; _RangeHash = std::__detail::_Mod_range_hashing; _Unused = std::__detail::_Default_ranged_hash; _RehashPolicy = std::__detail::_Prime_rehash_policy; _Traits = std::__detail::_Hashtable_traits<true, false, true>]’
In file included from /usr/include/c++/11/unordered_map:46,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:117,
                 from answer.code:1:
/usr/include/c++/11/bits/hashtable.h:512:7: note: ‘std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::_Hashtable() [with _Key = std::pair<int, int>; _Value = std::pair<const std::pair<int, int>, long long int>; _Alloc = std::allocator<std::pair<const std::pair<int, int>, long long int> >; _ExtractKey = std::__detail::_Select1st; _Equal = std::equal_to<std::pair<int, int> >; _Hash = std::hash<std::pair<int, int> >; _RangeHash = std::__detail::_Mod_range_hashing; _Unused = std::__detail::_Default_ranged_hash; _RehashPolicy = std::__detail::_Prime_rehash_policy; _Traits = std::__detail::_Hashtable_traits<true, false, true>]’ is implicitly deleted because the default definition would be ill-formed:
  512 |       _Hashtable() = default;
      |       ^~~~~~~~~~
/usr/include/c++/11/bits/hashtable.h:512:7: error: use of deleted function ‘std::__detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _Traits>::_Hashtable_base() [with _Key = std::pair<int, int>; _Value = std::pair<const std::pair<int, int>, long long int>; _ExtractKey = std::__detail::_Select1st; _Equal = std::equal_to<std::pair<int, int> >; _Hash = std::hash<std::pair<int, int> >; _RangeHash = std::__detail::_Mod_range_hashing; _Unused = std::__detail::_Default_ranged_hash; _Traits = std::__detail::_Hashtable_traits<true, false, true>]’
In file included from /usr/include/c++/11/bits/hashtable.h:35,
                 from /usr/include/c++/11/unordered_map:46,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:117,
                 from answer.code:1:
/usr/include/c++/11/bits/hashtable_policy.h:1602:7: note: ‘std::__detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _Traits>::_Hashtable_base() [with _Key = std::pair<int, int>; _Value = std::pair<const std::pair<int, int>, long long int>; _ExtractKey = std::__detail::_Select1st; _Equal = std::equal_to<std::pair<int, int> >; _Hash = std::hash<std::pair<int, int> >; _RangeHash = std::__detail::_Mod_range_hashing; _Unused = std::__detail::_Default_ranged_hash; _Traits = std::__detail::_Hashtable_traits<true, false, true>]’ is implicitly deleted because the default definition would be ill-formed:
 1602 |       _Hashtable_base() = default;
      |       ^~~~~~~~~~~~~~~
/usr/include/c++/11/bits/hashtable_policy.h:1602:7: error: use of deleted function ‘std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Hash, _RangeHash, _Unused, __cache_hash_code>::_Hash_code_base() [with _Key = std::pair<int, int>; _Value = std::pair<const std::pair<int, int>, long long int>; _ExtractKey = std::__detail::_Select1st; _Hash = std::hash<std::pair<int, int> >; _RangeHash = std::__detail::_Mod_range_hashing; _Unused = std::__detail::_Default_ranged_hash; bool __cache_hash_code = true]’
/usr/include/c++/11/bits/hashtable_policy.h:1209:7: note: ‘std::__detail::_Hash_code_...
English 繁體中文 简体中文

Server Time: 2024-12-02 07:45:31 | OpenSource Project