正解

比赛时在刚第二题，所以根本没有时间思考……

模型可以转化为从\((x_1,x_2,..,x_n)\)出发到\((1,1)\)的方案数模\(2\)。

方案数就用有重复的排列公式：\(\frac{(\sum{x_i})!}{\prod x_i!}\)

考虑它的奇偶性。显然可以将上面的\(2\)因子个数求出来，减去下面的个数，如果为\(0\)则是奇数。

这个东西也就是下面这条式子：\(\sum_{w=2^i} (\lfloor \frac{\sum_{x_i}}{w} \rfloor-\sum{\lfloor \frac{x_i}{w}\rfloor})\)

显然这条式子是大于等于\(0\)的。我们考虑它是否等于\(0\)。

然后我们就发现，如果有相加的时候有进位，那么它就会对下一位有贡献，而这一位的贡献不变。这意味着上式的值至少加\(1\)。

所以，若要它等于\(0\)，一定要保证相加的时候没有进位，也就是每一位上为\(1\)的数至多有\(1\)个。

于是就开始DP：设\(f_{i,S}\)表示从高到低到\(i\)位，\(S\)为贴着上限的状态。

由于有上下界的限制，所以容斥一下就可以了。

代码

using namespace std;#include 
    
     #include 
     
      #include 
      
       #define mo 990804011#define ll long long#define N 9int n;ll l[N],r[N],lim[N];ll ans;ll f[51][512];inline void upd(ll &a,ll b){a=(a+b)%mo;}inline ll calc(){    memset(f,0,sizeof f);    f[50][(1<
       
        =1;--i)        for (int j=0;j<1<
        
         >l&1 && !(lim[l]>>i-1&1))                    s|=1<
         
          >k&1 && lim[k]>>i-1&1 || !(j>>k&1)){ int s_=s&((-1)^1<
          
           >k&1 && lim[k]>>i-1&1)?1<
           
            =0){ lim[k]=l[k]-1; dfs(k+1,-flag); }}int main(){ freopen("c.in","r",stdin); freopen("c.out","w",stdout); int T; scanf("%d",&T); while (T--){ scanf("%d",&n); for (int i=0;i