「HDU 5632」Rikka with Array

发表于

给定一个数 nn ，问有多少个数对 (i,j)(i,j) ，满足 1≤i<j≤n1\leq i<j \leq n 且 f[i]>f[j]f[i]>f[j] ，f[x]f[x] 为 xx 二进制表示下 11 的个数。

Constraints

n≤10300n \leq 10^{300}

Solution

（在打模拟赛时写到的题目……好像写了一种跟所有人都不一样的写法）

首先考虑一个数 xx ，我们需要统计满足 1≤i<x1\leq i<x 且 f[i]>f[x]f[i]>f[x] 的 ii 的个数。考虑数位 dpdp ，将 xx 转为二进制形式，从低位往高位推。假设当前在第 ii 位，从第 11 位到第 ii 位共有 kk 个 11 ：若当前位为 00 ，则直接跳过进行下一位的统计；否则钦定当前要统计进答案的数字的比第 ii 位高的位置与 xx 相同，且第 ii 位为 00 ，则此时最低的第 i−1i-1 位至少要有 k+1k+1 个 11 ，可任意选取，即需要统计进答案里的方案数为 ∑j=k+1i−1(i−1j)\sum _{j=k+1}^{i-1} \binom{i-1}{j} ，令 s(i,j)=∑d=0j(id)s(i,j)=\sum _{d=0}^{j}\binom{i}{d} ，则公式简化为 s(i−1,i−1)−s(i−1,k)s(i-1,i-1)-s(i-1,k) 。

现在我们需要统计总答案，且因为 nn 很大，无法直接枚举。考虑将 nn 转成二进制形式，共有 cntcnt 位，aia_{i} 为 nn 在二进制下第 ii 位上的数字。统计每一个 s(i−1,i−1)−s(i−1,k)s(i-1,i-1)-s(i-1,k) 被统计进答案的贡献。若 s(i−1,i−1)−s(i−1,k)s(i-1,i-1)-s(i-1,k) 会在数字 xx 时被统计进答案里， xx 需要满足以下几个条件：1. 1≤x≤n1\leq x\leq n ，2. xx 的第 ii 位为 11 ，3. xx 的前 ii 位恰好有 kk 个 11 。答案转化为统计满足条件的 xx 的个数。

我们递推一个数组 ff ，f(i,j)f(i,j) 表示数值小于等于 nn 最低的 ii 位，且二进制下恰好含有 jj 个 11 的数字的方案数。可得：

f(i,j)={f(i−1,j)                       (ai=0)f(i−1,j−1)+(i−1j)   (ai=1)f(i,j)=\begin{cases}f(i-1,j)~~~~~~~~~~~~~~~~~~~~~~~(a_{i}=0)\\f(i-1,j-1)+\binom{i-1}{j}~~~(a_{i}=1)\end{cases}

特殊的，f(i,0)=1(0≤i≤cnt)f(i,0)=1(0\leq i\leq cnt) 。然后就可以数位 dpdp 出对于每一个 (i−1,k)(i-1,k) 的组合，所有符合条件的数 xx 了。

枚举当前在第 ii 位，前 i−1i-1 位总共有 kk 个 11 ，我们令 num=∑d=i+1cnt2d−(i+1)⋅adnum=\sum _{d=i+1}^{cnt} 2^{d-(i+1)}\cdot a_{d} ，即大于第 ii 位的部分的 00 到 num−1num-1 的方案，则 s(i−1,i−1)−s(i−1,k+1)s(i-1,i-1)-s(i-1,k+1) 的系数 tt 计算方式如下：

t={num⋅(i−1k)                         (ai=0)num⋅(i−1k)+f(i−1,k)   (ai=1)t=\begin{cases}num\cdot \binom{i-1}{k}~~~~~~~~~~~~~~~~~~~~~~~~~(a_{i}=0)\\num\cdot \binom{i-1}{k}+f(i-1,k)~~~(a_{i}=1)\end{cases}

然后就可以得到最终的答案了。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<cstdio>
#include<algorithm> 
#include<cstring>
#define LL long long
using namespace std;
const int N=1e3+5;
const int mod=998244353;
int T,n,cnt,ans,tmp,num,now,t;
int x[N],a[N],C[N][N],s[N][N],f[N][N];
char ch[N];
int read()
{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
void Mod(int& a,int b){a+=b;if(a>=mod)a-=mod;}
int main()
{
    for(int i=0;i<=1000;i++)C[i][0]=1;
    for(int i=1;i<=1000;i++)
        for(int j=1;j<=i;j++)
            C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
    for(int i=0;i<=1000;i++)
        for(int j=0;j<=1000;j++)
            if(j)s[i][j]=(s[i][j-1]+C[i][j])%mod;
            else s[i][j]=C[i][j];
    T=read();
    while(T--)
    {
        cnt=ans=0;
        scanf("%s",ch+1);
        n=strlen(ch+1);
        for(int i=1;i<=n;i++)x[n-i+1]=ch[i]-'0';
        if(n==1&&(x[1]==0||x[1]==1)){printf("0\n");continue;}
        while(n)
        {
            if(x[1]&1)a[++cnt]=1,x[1]--;
            else a[++cnt]=0;
            for(int i=n;i>=1;i--)
                if(x[i]&1)x[i]/=2,x[i-1]+=10;
                else x[i]/=2;
            while(n&&x[n]==0)n--;
        }
        memset(f,0,sizeof(f));
        for(int i=0;i<=cnt;i++)f[i][0]=1;
        for(int j=1;j<=cnt;j++)
            for(int i=j;i<=cnt;i++)
                if(!a[i])Mod(f[i][j],f[i-1][j]);
                else
                {
                    Mod(f[i][j],f[i-1][j-1]);
                    Mod(f[i][j],C[i-1][j]);
                }
        for(int i=1;i<=cnt;i++)
        {
            num=0;
            for(int j=cnt;j>i;j--)num=(num*2+a[j])%mod;
            for(int j=0;j<i;j++)
            {
                t=1ll*num*C[i-1][j]%mod;
                Mod(ans,1ll*(s[i-1][i-1]-s[i-1][j+1]+mod)%mod*t%mod);
                if(!a[i])continue;
                Mod(ans,1ll*(s[i-1][i-1]-s[i-1][j+1]+mod)%mod*f[i-1][j]%mod);
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}