Preface
补题，话说这场题目数量好少的说……
除了E题有点新花样前面题目都很简单的说，不过最后一天疯狂卡自然溢出的Hash，WA了一页可还行
A. Prefix and Suffix Array
SB题，我们把前缀对应的长度为\(n-1\)的串找出来之后，把剩下一个字母接在后面直接判断即可
#include<cstdio>
#include<iostream>
#include<string>
#define RI register int
#define CI const int&
using namespace std;
int t,n,c[25]; string s[25][2],tmp;
inline bool ispfx(const string& A,const string& B)
{
for (RI i=0;i<B.size();++i) if (A[i]!=B[i]) return 0; return 1;
}
inline bool issuf(const string& A,const string& B)
{
for (RI i=0;i<B.size();++i) if (A[1+i]!=B[i]) return 0; return 1;
}
inline bool check(string pre,string suf)
{
tmp=suf; for (RI i=2;i<n;++i)
if (ispfx(s[i][0],pre)&&issuf(s[i][1],suf)) pre=s[i][0],suf=s[i][1]; else
if (ispfx(s[i][1],pre)&&issuf(s[i][0],suf)) pre=s[i][1],suf=s[i][0]; else return 0;
return tmp=pre+tmp,1;
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (cin>>t;t;--t)
{
RI i; for (cin>>n,i=1;i<=n;++i) c[i]=0;
for (i=1;i<=2*n-2;++i) cin>>tmp,s[tmp.size()][c[tmp.size()]++]=tmp;
if (!check(s[1][0],s[1][1])) check(s[1][1],s[1][0]);
bool flag=1; for (i=0;i<tmp.size()&&flag;++i)
if (tmp[i]!=tmp[tmp.size()-i-1]) flag=0; puts(flag?"YES":"NO");
}
return 0;
}
B. Not Dividing
不难发现，若\(a_i|a_{i+1}\)，则\(a_i\nmid a_{i+1}+1\)，因此直接贪心地判断每个数要不要加\(1\)即可
但注意一个坑点，必须先把所有的\(1\)都变成\(2\)再操作，不会会卡死一直TLE的说
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=10005;
int t,n,a[N];
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]);
if (a[1]==1) ++a[1]; for (i=2;i<=n;++i)
{
if (a[i]==1) ++a[i];
while (a[i]%a[i-1]==0) ++a[i];
}
for (i=1;i<=n;++i) printf("%d%c",a[i]," \n"[i==n]);
}
return 0;
}
C. Scoring Subsequences
首先利用单调不降的性质，我们知道对于\(k=i\)的答案，其右端点一定为\(i\)，只要考虑左端点最多延申到哪里即可
把贡献关于下标的式子写出来，不难发现左端点的取法是单调的，因此用two pointers扫一下即可
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int t,n,a[N];
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i,p; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]);
for (p=i=1;i<=n;++i)
{
while (p<i&&a[p]<i-p+1) ++p;
printf("%d%c",i-p+1," \n"[i==n]);
}
}
return 0;
}
D. Counting Factorizations
简单数数题，但应该有多项式优化的方法把复杂度变成\(O(n\log n)\)的，懒得想了
首先我们统计出\(2n\)个数中不相同的质数个数\(m\)，若\(m<n\)则直接无解
否则我们考虑从这\(m\)个数中选出\(n\)个数，不难发现每一种方案之间的答案肯定是互异的，因为只要一个质数不同两个数肯定不同
那么只要考虑底数相同时的方案数即可，不难发现这就是个可重全排列，计算起来十分方便
我们先考虑排除这\(m\)个质数后剩下的可重全排列的方案数为\(ret\)，再考虑这\(m\)个质数中，设\(p_i\)出现的总次数为\(c_{p_i}\)，若不选择它为底数，则对应的\(ret\)要乘上\(\frac{c_{p_i}-1}{c_{p_i}}\)
因此我们可以很容易地想到一个DP，设\(f_{i,j}\)表示前\(i\)个不同的质数中选择\(j\)个为底数时的总贡献，转移就非常trivial了
总复杂度\(O(n^2)\)
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=4100,S=1e6+5,mod=998244353;
int n,a[N],f[N][N],c[S],p[N],coef[N],cnt,fact[N],inv[N],ret; bool vis[S];
inline bool isprime(CI x)
{
if (x==1) return 0; for (RI i=2;i*i<=x;++i) if (x%i==0) return 0; return 1;
}
inline int quick_pow(int x,int p=mod-2,int mul=1)
{
for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul;
}
inline void init(CI n)
{
RI i; for (fact[0]=i=1;i<=n;++i) fact[i]=1LL*fact[i-1]*i%mod;
for (inv[n]=quick_pow(fact[n]),i=n-1;~i;--i) inv[i]=1LL*inv[i+1]*(i+1)%mod;
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i,j; for (scanf("%d",&n),i=1;i<=2*n;++i) scanf("%d",&a[i]);
for (i=1;i<=2*n;++i) if (++c[a[i]],isprime(a[i])) if (vis[a[i]]=1,c[a[i]]==1) p[++cnt]=a[i];
if (cnt<n) return puts("0"),0;
for (init(2*n),ret=fact[n],i=1;i<S;++i)
if (c[i]) ret=1LL*ret*inv[c[i]-vis[i]]%mod;
for (i=1;i<=cnt;++i) coef[i]=1LL*fact[c[p[i]]-1]*inv[c[p[i]]]%mod;
for (f[0][0]=ret,i=1;i<=cnt;++i) for (j=0;j<=n;++j)
if (f[i][j]=1LL*f[i-1][j]*coef[i]%mod,j) (f[i][j]+=f[i-1][j-1])%=mod;
return printf("%d",f[cnt][n]),0;
}
E. Labeling the Tree with Distances
利用基于深度的多项式Hash来快速统计，算是个很有启发性的trick了
虽然被卡自然溢出很气，但又学到了一种新的写Hash的综合性技巧，还是收获满满
我们考虑对于每一个点维护一个Hash值，\(g_i=\sum_0^{n-1} c_i\times seed^i\)，其中\(c_i\)为当该点为根节点时深度为\(i\)的点的个数，\(seed\)是Hash种子
这样写不仅可以很方便地统计关于这道题的答案信息，而且在假定\(1\)号点为根求出所有点子树内的Hash值之后可以用换根操作找出所有点的Hash值
最后考虑有一个点的标记是任意的，不难发现最终的不同的可能取值只有\(n\)种，我们暴力枚举最后一个标记的取值，然后用set维护
最后对于每个点，直接查询set中是否有与之Hash值相等的值即可，总复杂度\(O(n\log n)\)
然后讲一下Hash部分，前面我用的自然溢出的双Hash一直被卡爆，然后改普通Hash（但模数取值范围还是int内的），改三Hash什么的都不行
于是只能去膜拜一手dalao的写法，遂令人大开眼界
首先是随机数种子的选取，我之前的方法就是大概这样
srand(time(0)); seed=1ull*rand()*rand()*rand()*rand();
但这种方法找出来的随机数并不均匀，很容易被卡
因此我们可以利用C++标准库中的random库里自带的std::mt19937_64来帮助生成随机数，在使用梅森算法的基础上，用这种方式生成随机数会更优秀，具体关于std::mt19937_64的姿势可以看这里
另外一个问题就是如果我们把模数选的很大，虽然撞车的概率大大降低，但是做乘法的时候就会溢出，但是用龟速乘又太慢
那么又涉及到一个好东西，直接开个unsigned __int128，记录乘积然后再取模即可（貌似之前见到的快速乘都是用long double的，但那东西说实话不太可靠的说）
利用上面两个科技我们就能通过这道200+个测试点的花式卡Hash的题了（注意开C++11及以上版本）
#include<cstdio>
#include<iostream>
#include<vector>
#include<set>
#include<random>
#define RI register int
#define CI const int&
using namespace std;
typedef unsigned long long u64;
const u64 mod=(1ull<<61)-1;
const int N=200005;
inline u64 sum(const u64& x,const u64& y)
{
return x+y>=mod?x+y-mod:x+y;
}
inline u64 mul(const u64& x,const u64& y)
{
__uint128_t z=__uint128_t(x)*y; return sum(z>>61,z&mod);
}
struct Hasher
{
u64 x,y;
inline Hasher(const u64& X=0,const u64& Y=0)
{
x=X; y=Y;
}
friend inline Hasher operator + (const Hasher& A,const Hasher& B)
{
return Hasher(sum(A.x,B.x),sum(A.y,B.y));
}
friend inline Hasher operator - (const Hasher& A,const Hasher& B)
{
return Hasher(sum(A.x,mod-B.x),sum(A.y,mod-B.y));
}
friend inline Hasher operator * (const Hasher& A,const Hasher& B)
{
return Hasher(mul(A.x,B.x),mul(A.y,B.y));
}
friend inline bool operator < (const Hasher& A,const Hasher& B)
{
return A.x!=B.x?A.x<B.x:A.y<B.y;
}
}pw[N],f[N],g[N],hsh; int n,x,y,a[N],cnt,ans[N];
vector <int> v[N]; set <Hasher> s;
mt19937_64 rnd(random_device{}());
uniform_int_distribution <u64> dist(100,mod-1);
const Hasher seed=Hasher(dist(rnd),dist(rnd));
inline void DFS1(CI now=1,CI fa=0)
{
f[now]=Hasher(1,1); for (int to:v[now]) if (to!=fa) DFS1(to,now),f[now]=f[now]+f[to]*seed;
}
inline void DFS2(CI now=1,CI fa=0,const Hasher& sum=Hasher())
{
g[now]=f[now]+sum*seed; for (int to:v[now]) if (to!=fa) DFS2(to,now,g[now]-f[to]*seed);
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i; for (scanf("%d",&n),pw[0]=Hasher(1,1),i=1;i<n;++i) pw[i]=pw[i-1]*seed;
for (i=1;i<n;++i) scanf("%d",&a[i]),hsh=hsh+pw[a[i]];
for (i=0;i<n;++i) s.insert(hsh+pw[i]);
for (i=1;i<n;++i) scanf("%d%d",&x,&y),v[x].push_back(y),v[y].push_back(x);
for (DFS1(),DFS2(),i=1;i<=n;++i) if (s.count(g[i])) ans[++cnt]=i;
for (printf("%d\n",cnt),i=1;i<=cnt;++i) printf("%d ",ans[i]);
return 0;
}
Postscript
现在一周的时间安排就很不均匀，周一到周三课特别满一点时间刷题都没有
但是周四到周日就挺多空闲时间的说，要狠狠地补题
标签：856,include,const,int,Codeforces,Hash,Div,Hasher,RI From： https://www.cnblogs.com/cjjsb/p/17197190.html