题目大意

有n个石子堆，A和B轮流操作，从第一堆开始操作到第n堆，每次可以拿走至少一颗石子，如果这堆拿完了，那就到下一堆，拿完最后一个石子的胜利。给出n和每堆石子的个数，问有多少种排列使得先手必胜。 n<100000,每堆石子的个数<= 1010

先手必胜情况

我们首先要知道，先手必胜的情况有哪些： 1、如果石子堆的石子数全都是1，那么如果n是奇数，先手必胜，否则后手必胜（后面的情况都是建立在不满足第一种的基础上的） 2、第一堆的个数大于1先手必胜，先手可以将第一堆取剩1或者取完可以使得后手必败 3、一开始有连续偶数个1，先手必胜。

解法

然后就变得很简单了，首先我们先不管1的石子堆，将剩下的石子堆乱排，然后枚举最开始有多少个1的石子堆，将剩下的一的石子堆插到原来的之间。

code

#include<iostream> #include<algorithm> #include<cstdio> #include<cmath> #include<cstring> #define fo(i,a,b) for(int i=a;i<=b;i++) #define fd(i,a,b) for(int i=a;i>=b;i--) using namespace std; typedef long long LL; const int N = 100010; const int mo = 1e+9+7; struct pile{ LL x; int v; }a[N]; LL js[N],ny[N]; int t,n; LL quickmi(LL x,LL tim,LL mo){ LL ans=1; while(tim){ if (tim%2)ans=ans*x%mo; x=x*x%mo; tim/=2; } return ans; } bool cmp(pile x,pile y){ return x.x<y.x; } LL c(int n,int m){ return js[n]*ny[m]%mo*ny[n-m]%mo; } int main(){ js[0]=1; fo(i,1,100000)js[i]=LL(js[i-1])*i%mo; ny[100000]=quickmi(js[100000],mo-2,mo); fd(i,99999,0)ny[i]=LL(ny[i+1])*(i+1)%mo; scanf("%d",&t); fo(u,1,t){ scanf("%d",&n); fo(i,1,n)scanf("%lld",&a[i].x);a[++n].x=1; sort(a+1,a+1+n,cmp); LL k=1,last=1; fo(i,2,n) if (a[i].x>a[i-1].x){ a[k].v=i-last; a[++k].x=a[i].x; last=i; } a[k].v=n-last+1; a[1].v--; n--; if (a[1].v==n){ if (n%2)printf("1\n"); else printf("0\n"); continue; } n=k;k=0; LL ans=1; fo(i,2,n){ ans=ans*c(a[i].v+k,k)%mo; k+=a[i].v; } LL qv=ans; ans=0; fo(i,0,a[1].v/2){ int x=i*2,y=a[1].v-x; ans=(ans+qv*c(y+k-1,k-1)%mo)%mo; } printf("%lld\n",ans); } return 0; }