不卡单 log 这一块

我还寻思这题怎么是个 *2400 呢，合着我的做法就不是预期解啊。

注意到

7 = 2^3 - 1

，考虑二进制。

对于

x^k

项，其对于第

0

至

(k-1)

位的贡献为

0

，而对于第

k

位，第

k+1

位和第

k+2

位的贡献可以在

\{0,1\}

中任选，且互相独立。

因此，考虑从低到高讨论每一位。每一位最多有

3

个互相独立的数作出贡献。记

f(i,j)

表示考虑低

i

位，且在第

i

位上遗留进位为

j

的方案数。可以得到

j

为不超过

2

的自然数。

对于

i = 0

，有

f(0,0) = 1

，

f(0,1) = 0

，

f(0,2) = 0

。对于

i = 1

，若

m

这一位上是

0

，则两种可能的方案为两个位置均填

0

或填

1

。前者不进位，后者进

1

位，故

f(1,0) = 1

，

f(1,1) = 1

，

f(1,2) = 0

。若

m

这一位上是

1

，则这两个位置上必须一个

1

一个

0

，故

f(1,0) = 2

，

f(1,1) = 0

，

f(1,2) = 0

。

对于后面的位置，若

m

这一位上是

0

，则

f(i,0) = f(i-1,0)

（全部填

0

），

f(i,1) = 3f(i-1,0) + 3f(i-1,1) + f(i-1,2)

（分别为两个填

1

，一个填

1

，不填

1

），

f(i,2) = f(i-1,1) + 3f(i-1,2)

。（分别为都填

1

和填两个

1

）。否则，

f(i,0) = 3f(i-1,0) + f(i-1,1)

（分别为填一个

1

和不填

1

），

f(i,1) = f(i-1,0) + 3f(i-1,1) + 3f(i-1,2)

（分别为填三个

1

，填两个

1

和填一个

1

），

f(i,2) = f(i-1,2)

（都填

1

）。

记

m

的最高位为

n

，则最后取

f(n,0)

极为答案。

时间复杂度

O(\log m)

。

CPP

#include<bits/stdc++.h>
using namespace std;
const int Maxw=63,mod=1000000007;
int T;
long long m;
long long dp[Maxw+3][3],ans;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>T;
    while(T--)
    {
        cin>>m;
        if(m==1)
        {
            cout<<1<<"\n";
            continue;
        }
        dp[0][0]=1;
        if((m>>1)&1) dp[1][0]=2,dp[1][1]=0,dp[1][2]=0;
        else dp[1][0]=1,dp[1][1]=1,dp[1][2]=0;
        ans=dp[1][0];
        for(int i=2;(1ll<<i)<=m;i++)
        {
            if((m>>i)&1)
            {
                dp[i][0]=(dp[i-1][0]*3+dp[i-1][1])%mod;
                dp[i][1]=(dp[i-1][0]+dp[i-1][1]*3+dp[i-1][2]*3)%mod;
                dp[i][2]=dp[i-1][2];
            }
            else
            {
                dp[i][0]=dp[i-1][0];
                dp[i][1]=(dp[i-1][0]*3+dp[i-1][1]*3+dp[i-1][2])%mod;
                dp[i][2]=(dp[i-1][1]+dp[i-1][2]*3)%mod;
            }
            ans=dp[i][0];
        }
        cout<<ans<<"\n";
    }
    return 0;
}

不卡单 log 这一块

文章操作

相关推荐

评论

不卡单 log 这一块