menu ZigZagK的博客

正在努力加载中QAQ

[思维+容斥]51Nod1317【相似字符串对】题解
apps 51Nod
local_offer 查看标签
comment 0 条评论
remove_red_eye 14 次访问

题目概述

字符串对 $(A,B)$ 是相似的需要满足两个串等长,且存在 $C$ 使得 $A+C=C+B$ 。求长度为 $n$ ,出现字母是小写字母前 $K$ 个的相似字符串对的个数。

解题报告

其实马上就想到了,但就是抽风了……考虑一个串,如果把他的某个前缀移到后面,那么显然这两个串就相似。很明显这就是循环同构,所以某个串的方案数就是和他循环同构的串的个数也就是该串最短循环节的长度。

循环节长度肯定是 $n$ 的因子,到这里就想到经典容斥了,考虑到 $n$ 的因子个数并不多,最多是 $1000$ 个左右,所以令 $f_i$ 表示 $n$ 的因子 $i$ 为最短循环节的方案数,那么 $f_i=K^i-\sum_{j|i}f_j$ 。最后答案就是 $\sum_{i|n}i\cdot f_i$ 。

示例程序

#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxm=2000,MOD=1e9+7;

int n,K,m,D[maxm+5],f[maxm+5],ans;

inline void AMOD(int &x,int y) {if ((x+=y)>=MOD) x-=MOD;}
inline int Pow(int w,int b) {int s=1;for (;b;b>>=1,w=(LL)w*w%MOD) if (b&1) s=(LL)s*w%MOD;return s;}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d",&n,&K);for (int i=1,s=sqrt(n);i<=s;i++) if (!(n%i)) {D[++m]=i;if (i<n/i) D[++m]=n/i;}
    sort(D+1,D+1+m);for (int i=1;i<=m;i++) {f[i]=Pow(K,D[i]);for (int j=1;j<i;j++) if (!(D[i]%D[j])) AMOD(f[i],MOD-f[j]);}
    for (int i=1;i<=m;i++) AMOD(ans,(LL)D[i]*f[i]%MOD);printf("%d\n",ans);return 0;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!
名称不能为空
邮箱不能为空,请填写正确格式
网址请用http://或https://开头
评论不能为空
资瓷Markdown和LaTex数学公式
keyboard_arrow_up