51nod1317 相似字符串对

Vexoben

Apr 10, 2019

It takes 4 minutes to read this article.

题目链接：51nod1317 相似字符串对

题意

称一对字符串（A，B）是相似的，当且仅当满足以下条件：

（1）字符串A和B都恰好包含N个字符；

（2）A和B串中的每个字符都是小写字母的前k个字符，即A、B中只可能出现’a’,’b’,’c’,…，（’a’+k-1）这k个字符；

（3）存在一个字符串C，满足：A+C=C+B。这里的“+”号表示字符串间的链接，即str1+str2 = str1str2，如：“aaa”+“csd”=“aaacsd”。

例如，N=3，k=4那么（”aad”,”daa”）就是相似字符串对。

因为C=”aa”时，有”aad”+”aa”=”aadaa”=”aa”+”daa”.

现在给出N与k，问有多少种不同的相似字符串对，输出这个结果 mod 1,000,000,007的值。

说明：两个字符串对(A,B)与(C,D)是不同的，只要 A!=C 或 B!= D。

数据范围：n≤1e9,k≤26

题解

这题有两个十分重要的结论：

1、字符串 (A, B) 相似当且仅当 A 与 B 循环同构

证明只需要考虑两种情况，看下面的图应该就很显然了。

2、一个最小循环节长度为 k 的字符串 A ，可以有 k 个对应的 B 与之循环同构

于是只要 dp[i] 表示长度为 i 且最小循环长度为 i 的字符串数量，那么答案是 sum( i * dp[i])，复杂度应该是 n 的因子个数的平方。

#include<bits/stdc++.h>
using namespace std;
const int N = 1505;
const int mod = 1e9 + 7;

int n, k;
int cnt, f[N], fat[N];

inline void upd(int &x, register int y) {
	static int z;
	x = ((z = x + y) >= mod) ? (z - mod) : z;
}

int Qpow(int x, int p) {
	int ans = 1;
	while (p) {
		if (p & 1) ans = 1LL * ans * x % mod;
		x = 1LL * x * x % mod;
		p >>= 1;
	}
	return ans;
}

int main() {
	scanf("%d%d", &n, &k);
	for (int i = 1; i * i <= n; ++i) {
		if (n % i != 0) continue;
		fat[++cnt] = i;
		if (i * i != n) fat[++cnt] = n / i;
	}
	sort(fat + 1, fat + cnt + 1);
	for (int i = 1; i <= cnt; ++i) {
		f[i] = Qpow(k, fat[i]);
		for (int j = 1; j < i; ++j) {
			if (fat[i] % fat[j] == 0) {
				upd(f[i], mod - f[j]);
			}
		}
	}
	int ans = 0;
	for (int i = 1; i <= cnt; ++i) {
		upd(ans, 1LL * fat[i] * f[i] % mod);
	}
	cout << ans << endl;
	return 0;
}