不卡单 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)。

#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;
}