【BZOJ3329】Xorequ

2015.08.10 10:10 Mon | 32次阅读 | 旧日oi | 固定链接 | 源码

题目大意

给定正整数n,求满足小于等于n,2^n中 x^(3x)=2x的正整数x的个数。n<=10^18

题解

把n二进制表示,令f[i][j]表示i位数,开头为j的数的总方案数。
则f[i][0]=f[i-1][0]+f[i-1][1],f[i][1]=f[i-1][0]
可以发现这个数列是个斐波那契数列。
对于<=2^n的,可以直接矩阵乘法求出第n+1项
对于<=n的,先++n,然后数位dp做就行了,当碰到连续两个1相连时,加上右面那个位置的f[i][0],然后break掉,最后记得要减掉0这个数。

我的程序

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
#define mod 1000000007
struct mtx
{
    ll a[2][2];
}mul,ret,c;
int T;
ll n,ans[70];
mtx mmul(mtx &a,mtx &b)
{
    for(int i=0;i<2;i++)
    for(int j=0;j<2;j++)
    {
        c.a[i][j]=0;
        for(int k=0;k<2;k++)
        c.a[i][j]+=a.a[i][k]*b.a[k][j];
        c.a[i][j]%=mod;
    }
    return c;
}
void mpow(ll x)
{
    while(x)
    {
        if(x&1) ret=mmul(ret,mul);
        x>>=1;mul=mmul(mul,mul);
    }
}
ll work(ll x)
{
    mul.a[0][0]=mul.a[0][1]=mul.a[1][0]=1;mul.a[1][1]=0;
    ret.a[0][0]=ret.a[1][1]=1;ret.a[0][1]=ret.a[1][0]=0;
    mpow(x);
    return ret.a[0][0];
}
int main()
{
    cin>>T;
    ans[0]=1;ans[1]=2;
    for(int i=2;i<=65;i++) ans[i]=ans[i-1]+ans[i-2];
    while(T--)
    {
        scanf("%lld",&n);n++;
        ll tmp=0; bool flag=1;int i;
        for(i=60;i>=0;i--)
        {
            if((n&(1ll<<i))) 
            {
                tmp=tmp+ans[i];
                if(flag) break;
                flag=1;
            }
            else flag=0;
        }
        printf("%lld\n",tmp-1);
        printf("%lld\n",work(n));
    }
}```