51nod 1317 相似字符串对（容斥原理+思维）-白红宇

51nod 1317 相似字符串对（容斥原理+思维）

阅读量：6412 次

发布时间：2019-06-23

本文共 1639 字，大约阅读时间需要 5 分钟。

题意：

称一对字符串（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=2，k=2，一共有6种不同的相似字符串对，它们是： ("aa", "aa"), ("ab", "ab"),

("ab", "ba"), ("ba", "ab"), ("ba", "ba"), ("bb", "bb").

题解：

先考虑相似字符串意味着什么，如果满足了A+C=C+B

如果C的长度大于n，那么就可以写成AAAA....AP = QB....BBBB

我们会发现中间的A和B都是不必要的，实际上还是转换成A'AP = BB， AA=QBB'

这个条件实际上就是指A的前缀等于B的后缀，且A和B有一段相同。

再进一步想，其实就是指A和B可以循环匹配。问题就转换成找有多少串可以循环匹配。

那么接下来如果知道一个串的循环节长度是p，那么它循环产生的p个新的串实际上都和它相似，所以它产生的贡献就是p

如果这种串有f(p)个，实际上答案就是p*f(p)。

循环节长度只能是n的约数，所以求出所有的p

最后把答案求和即可（这里用容斥+记忆化搜索解决，实际上p最多只有10^3左右个，所以复杂度最多是10^6）

#include 
      
       #include 
       
        #include 
        #include 
         
          #include 
          
           using namespace std;typedef long long LL;const LL MOD = 1e9 + 7;map
           
             dp;vector
            
              G;int n, k;LL mypow(LL a, LL b){ LL ans = 1; for(; b; b >>= 1, (a *= a) %= MOD) if(b&1) (ans *= a) %= MOD; return ans; }LL dfs(LL n){ if(dp[n]) return dp[n]; dp[n] = mypow(k, n); for(auto x : G) { if(x >= n) break; if(n % x == 0) (dp[n] = dp[n] - dfs(x) + MOD) %= MOD; } return dp[n];}int main(){ cin>>n>>k; for(int i = 1; i*i <= n; i++) if(n % i == 0) { G.push_back(i); if(n/i != i) G.push_back(n/i); } sort(G.begin(), G.end()); dfs(n); long long ans = 0; for(auto x : G) (ans += (LL)x*dp[x]) %= MOD; cout<
             
              <

转载于:https://www.cnblogs.com/Saurus/p/7647164.html

你可能感兴趣的文章