HDU 2197 本原串（数学+容斥）

朱雀 2022-06-15 12:07 147阅读 0赞

题目链接：  
[HDU 2197][]

题意：  
由0和1组成的串中，不能表示为由几个相同的较小的串连接成的串，称为本原串，有多少个长为n（n<=100000000)的本原串？  
答案mod2008.  
例如，100100不是本原串，因为他是由两个100组成，而1101是本原串。

题解：  
我们考虑一下容斥原理，长度为n的01串的总数为2n。要求本原串，只要将01串的总数减掉非本原串就可以啦。  
而非本原串可以由本原串得到。  
易得，f\[n\]=2n−∑(f\[i\])−2 ， 其中i是n的大于等于2的约数。  
因为非本原串肯定是由长度为a的字串不断重复b次得到的，那么a必然是b的约数。减二是要除去全是0或1<script type="math/tex" id="MathJax-Element-633">1</script>的情况。

代码：

#include <bits/stdc++.h>
    using namespace std;
    const int mod=2008;
    int f[10010];
    typedef long long ll;
    int q_mod(int a,int b)
    {
        int ans=1;
        while(b)
        {
            if(b&1)
            {
                ans=ans*a%mod;
            }
            a=a*a%mod;
            b>>=1;
        }
        return ans;
    }
    int solve(int n)
    {
        if(n==1)return 2;
        int ans=q_mod(2,n);
        ans-=2;
        ans%=mod;
        for(int i=2;i*i<=n;i++)
        {
            if(n%i!=0)continue;
            if(i*i==n)
            {
                ans-=solve(i);
                ans%=mod;
            }
            else
            {
                ans-=solve(i);
                ans-=solve(n/i);
                ans%=mod;
            }
        }
        return (ans+mod)%mod;
    }
    int main()
    {
        int n;
        while(~scanf("%d",&n))
        {
            cout<<solve(n)<<endl;
        }
        return 0;
    }

[HDU 2197]: http://acm.hdu.edu.cn/showproblem.php?pid=2197

发表评论取消回复

表情：

评论列表（有 0 条评论，147人围观）

还没有评论，来说两句吧...

相关阅读

相关 hdu1695（容斥原理）

求（1，b）区间和（1，d）区间里面gcd(x, y) = k的数的对数（1<=x<=b , 1<= y <= d）。 b和d分别除以k之后的区间里面，只需要求gcd(x,

一时失言乱红尘/ 2024年02月17日 23:41/ 0 赞/ 14 阅读

相关 Hdu 4451 Dressing (简单容斥)

题意：有N种衣服，M种裤子和K种鞋子，已知哪些衣服和哪些裤子不能搭配，哪些裤子和哪些鞋子不能搭配，现在要选择一套(衣服+裤子+鞋子)，问有多少种搭配方法。思路：所有的不和谐

逃离我推掉我的手/ 2022年08月26日 08:04/ 0 赞/ 100 阅读

相关 HDU 1695 GCD （容斥原理）

[HDU 1695][] 题意：求有多少对(x,y), (1<=x<=b,1<=y<=d), 满足gcd(x,y)=k。题解：注意到gcd(x,y)=k,说明x,y

男娘i/ 2022年07月12日 09:55/ 0 赞/ 195 阅读

相关 HDU 2197 本原串（数学+容斥）

题目链接： [HDU 2197][] 题意：由0和1组成的串中，不能表示为由几个相同的较小的串连接成的串，称为本原串，有多少个长为n（n<=100000000)的本

朱雀/ 2022年06月15日 12:07/ 0 赞/ 148 阅读

相关 HDU-4135 Co-prime(容斥原理)

Co-prime Given a number N, you are asked to cou

野性酷女/ 2022年06月10日 13:55/ 0 赞/ 167 阅读

相关组合数学容斥原理

![20180410143512519][]如图中划线所示，容斥原理就是运用集合中具有性质的对象来算出不具有所有性质的对象个数。 [20180410143512519]:

男娘i/ 2022年05月27日 02:55/ 0 赞/ 221 阅读

相关 hdu4135Co-prime——容斥定理

Given a number N, you are asked to count the number of integers between A and B inclusiv

灰太狼/ 2022年05月18日 00:10/ 0 赞/ 141 阅读

相关 HDU 6397 Character Encoding（容斥）

[传送门][Link 1] 挑选m个数，和为k，数的取值为0~n-1，相当于将每个数加1，使挑的m个数和是k+m，可以看成k+m个1，用m-1个隔板，隔成m分，所以总数为C

╰半橙微兮°/ 2022年05月16日 04:36/ 0 赞/ 122 阅读

相关 HDU1695GCD 容斥

原来用莫比乌斯写过这个[传送门][Link 1]，发现这个用容斥挺好理解，就是跑的比莫比乌斯慢，莫比乌斯跑了40ms，这个跑了400ms。估计复杂度是O(n\6\2^6)大

Love The Way You Lie/ 2022年05月16日 02:55/ 0 赞/ 198 阅读

相关 HDU 5514 巧妙的容斥

题意：给你一些数，对于每一个数a，可以得到t=(t+a)%m,t可以无限制算下去，问0~m-1之间能被得到的数的和。思路：根据欧几里得原理，a能得到的数就是a和m的最大公约

迈不过友情╰/ 2022年05月08日 08:36/ 0 赞/ 143 阅读