Solution

$2025$ 第一篇题解。水一道简单紫题。 /qd

题目中位运算的限制显然等价于 $a_i \subseteq a_{i+1}$（这里的包含于是在二进制意义下理解的）

如果 $a_i \neq a_{i-1}$，称 $i$ 是好的——则 $a_i \neq a_j$ 等价于 $(i,j]$ 中有一个好的下标。钦定 $n+1$ 也是好的。

容易发现，如果确定了好下标的个数，以及最后一个数的 $\text{popcount}$，则合法序列个数是相同的（可以简单 DP 求出），所以我们只需要求出：

1. 好下标有 $x$ 个的方案数。
2. $i \in [0,k]$ 且 $\text{popcount}(i)=y$ 的 $i$ 的个数。

后者是经典的数位 DP 问题，不做赘述。

对于前者，考虑这样一个 DP：设 $dp_{i,j,k}$ 表示考虑了前 $i$ 个位置，放了 $k$ 个好下标，最近一次放下标的位置是 $j$ 的方案数。

容易发现，$dp_{i+1,j,k}$ 和 $dp_{i,j,k}$ 相比（$j \le i$）要么不变，要么被清空为 $0$；而 $dp_{i,i,k}$ 是从 $dp_{i-1,*,k-1}$ 转移而来的，其中 $*$ 表示了一个连续的区间。

显然可以前缀和优化 DP。

复杂度 $O(n \log V + \log^2 V)$。

#include<bits/stdc++.h>
#define int long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=3e5+10,MAXM=60+10,MOD=1e9+7;
int n,m,k,lim[MAXN],t=65,C[MAXM][MAXM];
int mul[MAXM][MAXM],dp[MAXN][MAXM],pre[MAXN][MAXM],cnt[MAXM];
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m>>k;
	if(n==1) return cout<<(k+1)%MOD,0;
	ffor(i,0,t) {C[i][0]=1;ffor(j,1,i) C[i][j]=(C[i-1][j]+C[i-1][j-1])%MOD;}
	ffor(i,1,m) {
		int l,r;
		cin>>l>>r;
		if(l==r) return cout<<0,0;
		l++,lim[r]=max(lim[r],l);	
	}
	ffor(i,0,t) mul[i][1]=1;
	ffor(j,2,t) ffor(i,0,t) ffor(oi,0,i-1) mul[i][j]=(mul[i][j]+mul[oi][j-1]*C[i][oi])%MOD;
	dp[1][0]=1,pre[1][0]=1;
	int tot=1,ans=0;
	ffor(i,2,n+1) {
		ffor(j,1,t) dp[i][j]=(pre[i-1][j-1]-pre[tot-1][j-1])%MOD;
		ffor(j,0,t) pre[i][j]=(pre[i-1][j]+dp[i][j])%MOD;
		tot=max(tot,lim[i]);
	}
	roff(i,60,0) if(k&(1ll<<i)) {
		int v=k>>i; v--;
		ffor(j,0,i) cnt[__builtin_popcountll(v)+j]+=C[i][j];	
	}
	cnt[__builtin_popcountll(k)]++;
	ffor(i,0,60) ffor(j,1,60) ans=(ans+cnt[i]%MOD*dp[n+1][j]%MOD*mul[i][j])%MOD;
	cout<<(ans%MOD+MOD)%MOD;
	return 0;	
}