解题报告

陈老师的题解和没讲一样……考虑每一个二进制位的贡献，发现只要存在 $a_i$ 有 $j$ 这个二进制位，这个二进制位就有 $2^{n-1}2^{j}$ 的贡献，因为可以通过 $a_i$ 选不选使得 $j$ 这个二进制位存不存在。

那么 $f(\{a_n\})$ 的贡献其实就是 $2^{n-1}(a_1\ or\ a_2\ or\cdots or\ a_n)$ 。

这样的话显然 $n>2$ 的情况和 $n=2$ 是一样的，我们只需要考虑 $n=2​$ 。

由于 $L$ 和 $R$ 高位相同的地方是确定的，所以我们可以从 $L$ 和 $R$ 高位下来第一个不同的地方开始考虑。

去掉高位相同的地方，假设 $R$ 的最高位是 $p$ ，我们要考虑的是 $[L,2^{p+1})$ 中的数，假设 $x=a_1\ or\ a_2$ ：

• $L\le x\le R​$ ：让 $a_1=a_2=x​$ 即可。

• $R<x<2^{p+1}$ ：

  此时让 $a_1=2^p$ ，这样我们只需要考虑 $a_2$ ，假设 $R$ 的次高位为 $q$（没有次高位则 $q=-1$ ）：

  • $R<x<2^{p}+2^{q+1}$ ：让 $a_2=2^p+x$ 在 $q$ 后面的一截，这样 $L\le a_2\le R$ ，合法。

  • $2^p+2^{q+1}\le x<2^{p+1}$ ：

    • $2^p+2^{q+1}\le x<2^p+L​$ ：不可能构造 $a_2​$ ，因为 $x-2^p<L​$ 且 $2^p+2^{q+1}>R​$ 。
    • $2^p+L\le x<2^{p+1}​$ ：让 $a_2=x-2^{p}​$ ，这样 $L\le a_2\le R​$ ，合法。

根据上面的讨论可以看出只有 $2^p+2^{q+1}\le x<2^p+L$ 的时候才会出现违法，所以如果 $2^{q+1}<L$ ，那么就有违法区间 $[2^{q+1},L)$ ，需要减去该区间的长度。

示例程序

#include<cstdio>
using namespace std;
typedef long long LL;
const int maxn=100,MOD=1e9+7,Log=60;

int te,n;LL L,R,ans;

int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    for (scanf("%d",&te);te;te--){
        scanf("%d%lld%lld",&n,&L,&R);if (n==1||L==R) {printf("%lld\n",(R-L+1)%MOD);continue;}
        int p;for (int i=Log;~i;i--) if ((L>>i&1)^(R>>i&1)) {p=i;break;}
        L&=((LL)1<<p+1)-1;R&=((LL)1<<p+1)-1;ans=((LL)1<<p+1)-L;
        int q=-1;for (int i=p-1;~i;i--) if (R>>i&1) {q=i;break;}
        if (((LL)1<<q+1)<L) ans-=L-((LL)1<<q+1);printf("%lld\n",ans%MOD);
    }return 0;
}