岛村之刃

· · 题解

因为 n \ge 2，所以翻倍带来的贡献显然比加一要大。

所以要尽可能选翻倍，共有 k=\min _{i=1}^{n}\lfloor \log_2\dfrac{b_i}{a_i} \rfloor 次。

在翻倍 k 次的情况下考虑，每个 a_i 距离达到 b_i 还有 (b_i-2^{k}a_i)。

对于一次加一，如果在它后面存在 c 次翻倍，则其到最后可以使 a_i 变大 2^c。

则我们在所有翻倍前加一实际加的是 2^k。

我们可以在开始时给每处 a_i 加上 \lfloor \dfrac{b_i-2^{k}a_i}{2^{k}} \rfloor=\lfloor\dfrac{b_i}{2^{k}}\rfloor-a_i。

现在，每个 a_i 距离达到 b_i 还有 (b_i-2^{k}a_i) \bmod 2^k=b_i \bmod 2^k。

将 b_i 的前 k 为二进制拆分，第 c 位为一就表示我们需要在还有 c 次翻倍没用的时候给他加一。

所以后面一共要有 \sum _{i=1}^{n}\limits \operatorname{popcount}(b_i \bmod 2^k) 次加一，与前面的操作累加即可解决第一问。其中 \operatorname{popcount}(x) 表示 x 的二进制表示下 1 的个数。

对于第二问，考虑两次翻倍之间的加一操作，它们显然可以随便排列。这就是多重集组合数，如果 a_i 有 c_i 次加一在这两个翻倍之间，则这里可以使答案乘上 \dfrac{(\sum _{i=1}^{n}c_i)!}{\prod _{i=1}^{n}c_i!}。

对于除第一次翻倍之前的加一，后面的两次翻倍之间显然有 c_i \in \{0,1\}，所以 \prod _{i=1}^{n}c_i!=1。

只需计算 \sum _{i=1}^{n}c_i，阶乘可以预处理。

直接模拟即可做到 \mathcal{O}(nk)=\mathcal{O}(n \log V)。

#include<bits/stdc++.h>
#define int long long
#define vc vector<int>
#define rd read()
#define gc pa == pb && (pb = (pa = buf) + fread(buf, 1, 100000, stdin), pa == pb) ? EOF : *pa++
using namespace std;
static char buf[100000], * pa(buf), * pb(buf);
inline int read()
{
    register int x=0,s=gc;while(!isdigit(s))s=gc;
    while(isdigit(s))x=(x<<1)+(x<<3)+(s^48),s=gc;
    return x;
}
const int N=200005,mod=1000003,w=21;
int n,k,a[N],b[N],cnt[N],fac[mod],inv[mod],fnv[mod],c[w];
inline int fpow(int x,int y=mod-2)
{
    int res=1,f=x;
    for(;y;y>>=1,(f*=f)%=mod)
        if(y&1)(res*=f)%=mod;
    return res;
}
inline void sol(){
    n=rd;for(int i=1;i<=n;++i)a[i]=rd;for(int i=1;i<=n;++i)b[i]=rd;
    k=60;for(int i=1;i<=n;++i)k=min(k,__lg(b[i]/a[i]));
    for(int i=1;i<=n;++i)cnt[i]=(b[i]>>k)-a[i],b[i]&=((1<<(k+1))-1);memset(c,0,sizeof(c));
    for(int j=0;j<k;++j)for(int i=1;i<=n;++i)if(b[i]>>j&1)++c[j];
    int x=0,ans=1;for(int i=1;i<=n;++i)x+=cnt[i];if(x<mod)ans*=fac[x];else ans=0;
    for(int i=0;i<k;++i)x+=c[i],(ans*=fac[c[i]])%=mod;x+=k;
    for(int i=1;i<=n;++i)(ans*=fnv[cnt[i]])%=mod;
    cout<<x<<' '<<ans<<'\n';
}
signed main(){
    fnv[0]=fac[0]=1,inv[1]=1;
    for(int i=2;i<mod;++i)inv[i]=(mod-mod/i*inv[mod%i]%mod+mod)%mod;
    for(int i=1;i<mod;++i)fac[i]=fac[i-1]*i%mod,fnv[i]=fnv[i-1]*inv[i]%mod;
    int T=rd;while(T--)sol();return 0;}

这题其实还可以做到 \mathcal{O}(n)。

上面做法的瓶颈在于需要对于每个 <k 的二进制位统计 1 的个数。

考虑将 k 个二进制位的统计同步。因为 \sum _{i=1}^{n} c_i 是可加的，不妨考虑分治。

设 f_x 为第 x 位的 \sum _{i=1}^{n}c_i。

则对于大的 f 可以用两边小的区间的 f 相加得到。每次合并 \mathcal{O}(k)，复杂度不变。

将 f 拆位，记 F_{x,y} 为 f_y 的第 x 个二进制位。显然，对于第一维有 x \le \lfloor \log n\rfloor，第二维有 y \le k \le w=64。

枚举 x 一维，将 y 一维压位模拟二进制加法，则单次合并复杂度为 \mathcal{O}(\log n)。

此时复杂度为 T(n)=2 T(n/2)+\mathcal{O}(\log n)。

将 \log n 看作 n^{\epsilon}，由主定理知道 T(n)=\mathcal{O}(n)。

当然，数据范围很小，所以并不比 \mathcal{O}(n \log V) 快很多。

#include<bits/stdc++.h>
#define int long long
#define vc vector<int>
#define rd read()
#define gc pa == pb && (pb = (pa = buf) + fread(buf, 1, 100000, stdin), pa == pb) ? EOF : *pa++
using namespace std;
static char buf[100000], * pa(buf), * pb(buf);
inline int read()
{
    register int x=0,s=gc;while(!isdigit(s))s=gc;
    while(isdigit(s))x=(x<<1)+(x<<3)+(s^48),s=gc;
    return x;
}
const int N=200005,mod=1000003,w=21;
int n,k,a[N],b[N],cnt[N],fac[mod],inv[mod],fnv[mod],c[w];
inline int fpow(int x,int y=mod-2)
{
    int res=1,f=x;
    for(;y;y>>=1,(f*=f)%=mod)
        if(y&1)(res*=f)%=mod;
    return res;
}
inline vc merge(vc x,vc y){
    if(x.size()<y.size())swap(x,y);int p=0,P,i=0;
    for(;i<y.size();p=P,++i)
        P=(x[i]&y[i])|((x[i]^y[i])&p),x[i]^=(y[i]^p);
    for(;i<x.size();p=P,++i)P=x[i]&p,x[i]^=p;
    if(p)x.push_back(p);return x;
}
inline vc sol(int l,int r){
    if(l==r)return {b[l]};int mid=l+r>>1;
    return merge(sol(l,mid),sol(mid+1,r));
}
inline void sol(){
    n=rd;for(int i=1;i<=n;++i)a[i]=rd;for(int i=1;i<=n;++i)b[i]=rd;
    k=60;for(int i=1;i<=n;++i)k=min(k,__lg(b[i]/a[i]));
    for(int i=1;i<=n;++i)cnt[i]=(b[i]>>k)-a[i],b[i]&=((1<<(k+1))-1);
    vc K=sol(1,n);memset(c,0,sizeof(c));
    for(int i=0;i<K.size();++i)for(int j=0;j<k;++j)if(K[i]>>j&1)c[j]+=(1<<i);
    int x=0,ans=1;for(int i=1;i<=n;++i)x+=cnt[i];if(x<mod)ans*=fac[x];else ans=0;
    for(int i=0;i<k;++i)x+=c[i],(ans*=fac[c[i]])%=mod;x+=k;
    for(int i=1;i<=n;++i)(ans*=fnv[cnt[i]])%=mod;
    cout<<x<<' '<<ans<<'\n';
}
signed main(){
    fnv[0]=fac[0]=1,inv[1]=1;
    for(int i=2;i<mod;++i)inv[i]=(mod-mod/i*inv[mod%i]%mod+mod)%mod;
    for(int i=1;i<mod;++i)fac[i]=fac[i-1]*i%mod,fnv[i]=fnv[i-1]*inv[i]%mod;
    int T=rd;while(T--)sol();return 0;}

::::info["What a pain..."]

「你去了祭典吧？和我不认识的女生一起。」

「那个女生是谁？为什么要跟她一起去？你怎么没有告诉我？我跟她的确不是朋友，可是我想了解岛村啊，我最想解岛村，最希望待在岛村身边的人，我希望我是最亲近你的人，而且我不希望自己不是最亲近你的那个人。明明我就想和你变得更要好你为什么要这么做？」

「我！讨厌、岛村在我不知道的地方笑！还有、和其他人牵手也是！只和我就好！我特别希望是和我在一起！庆典我也是好想去的！岛村看上去很开心的，笑著的，在你旁边有我！那样的才好！头好痛的、好难受的！我一直就只思考岛村的事，思考得、快不正常了……我还一直等著岛村给我打来电话的！偶尔和我聊聊嘛，找我来说说话嘛，我讨厌老是就我那么做，岛村你也、稍微……有没有稍微在意点我的事？一点点也？完全不？什么都没想过吗？只是朋友？普通的朋友吗？我想变得不普通，比普通再多一个就好，所以我要不普通的、好……喂、岛村，我该怎么办才好呢、喂。岛村你有在听吗？听我说。听到我的声音你会想些什么？有为我想些什么吗？觉得安心也可以呀，什么都行，想些什么嘛。我想要那样的，我不能渴望要求那样的吗？岛村！就得是岛村呀啊，我啊，就觉得岛村好。我不需要岛村以外的，不需要……只要岛村就够了。我没在说任性的话喔，因为就一个，就要一个嘛。大家什么的都无所谓我也不需要而且也希望她们都到一边待著去的，可为什么岛村要跟著去那边呢，来这边，来我这边，待在我身边，不要离开我。我不喜欢，我要待在岛村身边的人是我，是我就好，我想待在你身边，让我待在你身边……谁啊那人，我可不认识呀，我讨厌岛村变成我不了解的，我想知道岛村全部的事情，而且我也讨厌有我不想知道的事情，可是我更不要我不知道，好难受的。好难受，好痛、好痛……岛村～。我是想说和岛村一起去玩的呀，庆典也是有想过要一起去的呀，我好想去的，但是岛村和那个人去的，在玩吗？岛村你现在在哪，和谁在一起，岛村、岛村～……喂你有在听吗？从刚才开始就一直只有我在讲话，要是平时的岛村会多说些什么的吧，哪、为什么？这不是和平时一样嘛？我很怪？是很怪吧，我知道我现在很怪但是，我太想知道岛村的事了，太想知道的，变得奇怪了。我不想和岛村分开我想一直和你待在一起的待在哪里都好的只要是在一起在哪里都行，我还没和岛村见面呢，好想见你可现在要是见到了我可能会哭，而且我已经在哭著了，你和那人后来怎么了到底是什么啊我一直在意著这些喂你有在听吗？比起和我待在一起那人要更好些吗？我就不行吗？我哪里不好？我改你说呀，改过来绝对改所以求求你告诉我，我想听的。说到岛村你啊，我，因为是岛村……有因为是岛村这句话，就算有人和岛村长得特别像也跟我没关系的不过应该也没有那样的人，哪我想说的不是这个，是、不是岛村就不行的，所以我是想和你关系变得更好的，怎么说……我本来不想说这些的，更想说些与这些不同的，可却一直在意著……因为那时岛村可是一脸的笑容喔？我讨厌你对我以外的笑，不讨厌？不是那样的？岛村没有过吗？岛村你喜欢谁？有喜欢的人吗？能喜欢上吗？喜欢是什么你知道吗？偶尔，我会好害怕的。为什么岛村可以在我身边的呢，岛村和我本身是朋友的对吧？我们确实起码算是朋友了对吧。你认为我是你朋友吗？岛村，对那种的……呜呜呜，哎啊，岛村，让我听听你的声音，我想听你的声音，说说我的事。岛村是最明白我的……我希望你明白我，我也想要你明白希望你明白。希望成为你的之最，我想成为的。做你的第一，但是……一遇到点不好的事我就会变得好沮丧……因为岛村你，我感觉不到你有很重视我……重视，说重视很怪吧，但是我希望你重视我，重视我就好！我不要和其他人一样被对待，真的只一点点、一点点就好……岛村你有想过我的事吗？在暑假虽然我们一直都没有见到面，但你有至少一次想到过吗？我啊，是一直在想著的，只思考过岛村的事喔。全部都是岛村，所以、岛村也！多思考思考我的事……岛村你是和我不同的喔？是不一样的吧，我知道的，可是！我会期待，会想去期待，像这样被背、叛也……会想给岛村打电话的。可是打了电话还是会变成这个样子，完全没办法的，我该怎么办才好啊。喂，岛村，岛村？电话还接通著吧？我有和岛村接通著吧？可是好远，好远，我好想见到你，我好想直接去见你岛村。想看著你笑，让岛村你摸摸我的头，想听你说没事的。你现在在哪？在哪？和谁？那个人？那个人谁？我从刚才就问了你好几遍了，她是你回答不了的人？关系怎样？比我还要好？不要，我不要那样，竟比我还要、不要。不要……不是的，你快说不是的！我可是想了好多好多岛村的事的呀！还不够？那还不行？再更多的？我该做什么才可以？我又不懂，就只会一直思考却还总是会失败，什么样的我才可以你告诉我，告诉我了，我会努力的呀，我一定会努力的呀，所以那个人其实是谁都不重要，只要我想见到的岛村再更、区别对待、只要我改变就可以了，我明白的但是……岛村，喂，岛村。你现在在想些什么？我很奇怪？我怪？给我说说岛村你吧，由岛村你来找我讲话，由岛村你来接近我。一直总是我、总是、总是……我单方面的，才会变成这个样子的呀！才会变成像现在这个样子的，岛村你也来我、这边。岛村你讨厌我吗？不是的吧？不要呀，不要讨厌我，我不要讨厌。我不要你讨厌我……喜欢，我希望你喜欢上我。去喜欢上，谁。不我喜欢上的是岛村(去喜欢上不一样的岛村)……你不喜欢我吗？像我母亲似的讨厌我吗？会渐渐地不再理我了吗？一副不认识了我的面孔吗？我该说些什么才可以呢？该做些什么才可以呢，飞起来就行了吗，跳起来就行了吗，牵手就行了吗，本想全都做的可是我做了后又不看……我那时到底该怎么做才好的，该怎么办，谁也……岛村，我想听你的、声音……你说点什么，让我安心，但是我不要你对其他人笑，对我笑，笑吧……头好痛，肚子也好痛……明明我那么在意（那件事来著）的为什么你不、联系我呢，告诉我吧，我好想知道。我好想知道岛村的事，从刚才开始，感觉自己的情绪转来转去的……我一直在说同样的话，可这也是没办法的呀，没办法嘛，因为我一直想著的只是岛村……因为只有岛村所以，就算变成、想的一直是岛村也……我很重视岛村，很想重视，我不要不重视，所以，看著我。岛村，我不要你不看著我……看其他人，我才不要～……我讨厌那样。又要走了？要去哪里？一起去街上？在和我一起玩的地方，和其他的人！我讨厌那样的。不要覆盖上呀！我一直都记得的，却被覆盖上……再去的话，这回就不一样了？让我看同一个地方然后去看不一样的东西？我不要那样，不要、不要。和岛村一起，分享一样的东西，知道一样的东西……好奇怪啊那样，不是的对吧是我太奇怪了，我知道自己好怪，可是我变得好怪……岛村怎么都离不开我的脑海里……现在也是……岛村、岛村、岛、村……呜呜哎、呜、呜呜呜呜，岛村，岛村……、哼、咳、呜呜……岛村的、岛村？岛村、岛村，岛村、岛村……就岛村好，我觉得好，所以岛村你也……喂求求你，岛村……岛村也、岛村……」

::::