【SWTR-02】Sweet Round 02 T4 Magical Gates

Alex_Wei · 2019-11-10 10:33:34 · 题解

\color{#9400d3}T4.\ Magical\ Gates

\color{#9400d3}\text{题面}

\color{#9400d3}\text{官方题解}

欢迎爆踩 \mathrm{std} ！

你感受过明天就要比赛却在比赛前一天发现有相似类型的题目的绝望吗？

双倍经验，如果你过了这道题目就一定能 \mathrm{AC} 本题：P4317

可以将本题看成该题的超级加强版（但是我们出题的时候并不知道有该题的存在）

本题主要考察数位 \mathrm{DP}

暴力分 :10\%

下文中所有的 n 都代表该测试点的数据范围（可以理解为 n=\max r）
下文中所有的 \log 以 2 为底
下文中，\binom{i}{j} 表示从 j 个不同元素中选出 i 个元素的方案数，即我们通常说的组合数，也可表示为 C_{j}^{i}，计算公式为 \frac{j!}{i!(j-i)!}

Sol\ 1:10\%

将题目所给代码直接复制 + 暴力即可，可拿到前 2 个测试点的分数，共 10\%

Sol\ 2:20\%

发现题目中所给 get 函数就是求：一个数在二进制下有多少个 1

对 1-10^5 中的每个数 \Theta(\log n) 预处理出有多少个 1

然后暴力回答询问即可

时间复杂度：\Theta(n\log n)

Sol\ 3:35\%

前置知识：乘法逆元和有理数取余，如果不会请先移步 P3811 和 P2613

因为模数 $p$ 为质数，所以可以费马小定理求逆元您可能会因为空间/时间被卡而拿不到应得的分数时间复杂度：$\Theta(n+T\log p)=\Theta(n)

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#pragma GCC optimize(3)
int t,d[10000005],q[10000005];
ll k[10000005],p,n;
ll ksm(ll a,ll b,ll p){ll ans=1;while(b){if(b&1)ans=(ans*a)%p;b>>=1,a=(a*a)%p;}return ans;}
int lowbit(int x){return x&-x;}
int main()
{
    cin>>t>>p>>n;
    for(int i=1;i<=1e7;i++)
        d[i]=d[i-lowbit(i)]+1;
    k[0]=1;
    for(int i=1;i<=1e7;i++)
        q[i]=q[i-1]+d[i],k[i]=k[i-1]*d[i]%p;
    while(t--){
        int l,r;
        cin>>l>>r;
        cout<<q[r]-q[l-1]<<" "<<k[r]*ksm(k[l-1],p-2,p)%p<<endl;//费马小定理求逆元 
    }
    return 0;
}

Sol\ 4:31\%

前置知识：高精，找规律，欧拉定理，如果不会请先移步 P5091

找规律（或者推出结论），当 l=1,r=2^k 时

\sum_{i=l}^{r}d_i=k\times 2^{k-1}+1

\prod_{i=l}^{r}d_i=\prod_{i=1}^{k}i^{\binom{i}{k}}

可以 \Theta(\log^2 n) 预处理出 $\binom{i}{j}

- 根据欧拉定理，因为 $\binom{i}{j}$ 在指数的位置上，且 $p$ 为素数，所以应对 $\varphi(p)=p-1$ 取模时间复杂度 $\Theta(T(\log^2 n+\log n\log\log n))=\Theta(\log^2 n)

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll t,p,p2,n,C[3333][3333];
string l,r;
int x[1005];
ll ksm(ll a,ll b){ll s=1,m=a;while(b){if(b&1)s=s*m%p;m=m*m%p;b>>=1;}return s;}
int main()
{
    cin>>t>>p>>n,p2=p-1;
    int N=n<15?70:3332;
    for(int i=1;i<N;i++)
        for(int j=0;j<=i;j++)
            if(j==0||i==j)C[i][j]=1;
            else C[i][j]=(C[i-1][j]+C[i-1][j-1])%p2;
    for(int i=0;i<t;i++){
        cin>>l>>r;
        int top=r.size(),bit=0;
        for(int j=0;j<r.size();j++)
            x[j]=r[r.size()-j-1]-'0';
        while(top){
            bit++;
            int tmp=0;
            for(int j=top-1;j>=0;j--)
                tmp=tmp*10+x[j],x[j]=tmp/2,tmp%=2;
            if(!x[top-1])top--;
        }
        bit--;
        int mul=1;
        for(int j=1;j<=bit;j++)
            mul=mul*ksm(j,C[bit][j])%p;
        cout<<(bit*ksm(2,bit-1)+1)%p<<" "<<mul<<endl;
    }
    return 0;
}

Sol\ 5:54\%

结合 Sol\ 3，Sol\ 4 可拿到 54\% 的高分

代码就不贴了

Sol\ 6:100\%

前置知识：高精，欧拉定理，数位 \mathrm{DP}

在下文中，x_{(2)} 表示 x 在二进制下表示的数

我们考虑数位 \mathrm{DP}

dp_i$ 表示在 $[1,x]$ 中，**二进制下 $1$ 的个数为 $i$ 个的数有多少个**，然后将 $[1,r]$ 的结果减去 $[1,l)$ 的结果就是 $[l,r]$ 的结果，最后的答案就是 $\sum_{i=1}^{k}i\times dp_i$ 和 $\prod_{i=1}^{k}i^{dp_i}

\large Q1:

如何计算区间 [1,x] 的 dp_i？

\large A1:

设 x_{(2)} 一共有 k 位，从左往右遍历 x_{(2)} 的每一位（只有可能为 0 或 1）
如果该位为 0：跳过，不考虑
如果该位为 1 ：将该位为 0，右边的位为任意值 的情况讨论到答案中，这样保证了不会 少计算/多计算/重复计算，且在接下来的讨论中，将该位的值看作为 1

即设当前考虑到第 j(j\in[1,k]) 位（从右往左数），设该位左边共有 cnt 个 1

对于所有 dp_{i+cnt}(i\in[0,j))，加上 \binom{i}{j-1}，最后再将 cnt 加 1

遍历过所有位之后，还要将 x_{(2)} 本身的答案算进去，即 dp_{cnt} 加 1

Q2:

为什么我按照 A1 的方法做，却 \color{red}\mathrm{WA} 掉了？

\large A2:

因为求积的 dp_i 在指数的位置上，且 p 为质数，所以该部分的 dp_i 应对 \varphi(p)=p-1 取模，而不是 p

同样的，上式 dp_{i+cnt}(i\in[0,j))+\binom{i}{j-1} 中的 \binom{i}{j-1} 也应对 p-1 取模

\large Q3:

为什么我按照 A1,A2 的方法做，却 \color{#0000AA}\mathrm{TLE} 了？

\large A3:

可以先 \Theta(\log^2 n) 预处理出 \binom{i}{j} 对 p 和 p-1 取模的值，计算的时候就不需要再 \Theta(\log n) 处理了（虽然先预处理出阶乘和阶乘逆元也不错，但是常数较大）

千万别小看这个 \Theta(\log n)，因为 n 有可能到 10^{1000}，所以 \max\log n\approx 1000\times \log(10)\approx3322

\large Q4:

这个算法的时间复杂度是多少？

\large A4:

一次 A1 操作时间复杂度 \Theta(\log^2n)，共 2T 次操作且 T 为常数，预处理 \Theta(\log^2n)，总时间复杂度 \Theta(\log^2n)

\large Q5:

说了这么多废话，赶紧把代码拿出来

\large A5:

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=3333; 
ll ksm(ll a,ll b,ll p){ll ans=1;while(b){if(b&1)ans=(ans*a)%p;b>>=1,a=(a*a)%p;}return ans;}
ll t,p,p2,n,k,add[N][N],mult[N][N],prod[N],sum[N];
bool bit[N];//二进制
string l,r;
void change(string s,bool minus)//将字符串转成二进制数，minus 为是否减 1（计算l时需要）
{
    k=0;
    int l=s.size()-1,p[N],high=l;
    for(int i=l;i>=0;i--)p[i]=s[l-i]-'0';//高精度
    if(minus){
        p[0]--;
        int pos=0;
        while(p[pos]<0)p[pos+1]--,p[pos]+=10,pos++;
        if(!p[high])high--;
    }
    while(high>=0){
        k++;
        int res=0;
        for(int i=high;i>=0;i--){
            res=res*10+p[i];
            p[i]=res/2;
            res%=2;
        }
        bit[k]=res;
        if(!p[high])high--;
    }
}
void solve()//一组数据
{
    memset(sum,0,sizeof(sum));
    memset(prod,0,sizeof(prod));
    cin>>l>>r;
    change(r,0);
    int cnt=0;
    for(int j=k;j>0;j--)
        if(bit[j]){
            for(int i=0;i<j;i++)
                sum[i+cnt]=(sum[i+cnt]+add[j-1][i])%p,
                prod[i+cnt]=(prod[i+cnt]+mult[j-1][i])%p2;
            cnt++;
        }
    sum[cnt]++,prod[cnt]++;//计算[1,r]
    change(l,1),cnt=0;
    for(int j=k;j>0;j--)
        if(bit[j]){
            for(int i=0;i<j;i++)
                sum[i+cnt]=(sum[i+cnt]-add[j-1][i]+p)%p,
                prod[i+cnt]=(prod[i+cnt]-mult[j-1][i]+p2)%p2;
            cnt++;
        }
    sum[cnt]=(sum[cnt]-1+p)%p,prod[cnt]=(prod[cnt]-1+p2)%p2;//减去[1,l)
}
void init()
{
    cin>>t>>p>>n,p2=p-1;
    int lim;
    if(n<18)lim=64;
    else if(n<21)lim=333;
    else lim=3333;//避免浪费时间和空间
    add[0][0]=mult[0][0]=1;
    for(int i=1;i<lim;i++){
        add[i][0]=mult[i][0]=1;
        for(int j=1;j<=i;j++){
            add[i][j]=(add[i-1][j]+add[i-1][j-1])%p;
            mult[i][j]=(mult[i-1][j]+mult[i-1][j-1])%p2;
        }
    }//预处理出组合数
}
int main()
{
    init();
    for(ll i=1;i<=t;++i){
        solve();
        ll ans=0;
        for(ll j=1;j<N;j++)
            ans=(ans+sum[j]*j)%p;
        cout<<ans<<" ";
        ans=1;
        for(ll j=1;j<N;j++)
            ans=(ans*ksm(j,prod[j],p))%p;//这里是对 p 取模，因为已经在算最终的答案了
        cout<<ans<<endl;
    }
    return 0;
}

当然，解法并不唯一，如果有更好的思路也欢迎大家在题解区发布！

如果题解有误请私信我，或在右侧评论区指出