C - The Majority

将a种球放进k个不同的箱子，每种球ni个，第1号球在箱子中球的总数的一半以上问方案总数

因为第1种球的个数在每个箱子站一半以上，故同时去除一个1号球和一个其他球，每个箱子内必剩余有一号球

剩余的一号球个数为

这些球需要放满所有的箱子算出总情况数ans1

然后将剩余的球随意的放入箱子内，总情况数ans2

将两个相乘即可

箱子放球的总结（ans1，ans2的求法已经其他的不同情况

借鉴的是这个博客：排列组合 "n个球放入m个盒子m"问题 总结_qwb的博客-CSDN博客_n个球放入m个盒子定理

1.n个相同球放入m个不同箱子且没有空箱子（ans1）

将n个球分为m段（没有空段），也就是将m-1个隔板插入n-1个空隙中，故答案为

/

2.n个相同球放入m个不同箱子且可以有空箱子（ans2）

相当于将m-1个隔板插入n-1个空隙中并且可以同时插入到一个中

就是n-1个物品选m-1次并且选完放回

选m-1次必定放回m-2个，故相当于（n-1+m-2)个物品选m-1次，答案为

/

3.n个不同的球放入m个相同的箱子且没有空箱子

第二类斯特林数

dp[n][m]表示n个球放入m个箱子

对于新加入的一个球，可以在原来箱子已经满的情况下随意放入一个箱子，也可以新开一个箱子放入此球

/

4.n个不同的球放入m个相同的箱子且可以空箱

箱子数目随便，故为

/

5.n个不同球放入m个不同的箱子无空箱

每种箱子不一样，答案乘上箱子的全排列，故为

/

6.n个不同的球放入m个不同的箱子且可以空箱

将4中的每种情况乘上箱子的全排列即可

或者相当于每个球随便放结果为

/

E - Modulo Nim

进行一个游戏：每次取出数列中的一个数x，选取一个[1,x]个数并且使序列中每个数对其取模，第一次取出0的人获胜

现在有n个数第i个位ai，构造一个序列b使先手获胜并且ai>=bi

性质1：0的个数对整个序列结果无影响

性质2：相同的数对序列结果无影响

先来判断剩余序列有1，2的情况

{1},{2}先手必败，{1,2}先手必胜（对2取模）

再来判断其他的问题（序列中元素全部大于2）

若序列中有奇数先手必胜（对2取模，剩余为{1})

否则，若序列存在除以4余2的数，先手必胜（对4取模，剩余为{2})

因为只有{1},{2}后手必败，故除数更大时没有其他先手必胜的情况

故序列必败的必要条件是每个数都整除以4

再来判断对3取模的情况

若所有数都余1或都余2，先手必胜

还剩两种情况：余数为{1，2}或余数为0

第一种余数为{1，2}的情况：

要求所有不成立的数量，故集合中每个数需要是4的倍数

可以化简为{12n+4,12k+8}

可以发现,{4,8}是先手必败的

对于n，k中有一个数不为0的情况，可以对其与12取模化为{4,8},故是先手必胜的

还有一种为余数都为0的情况

因为同时为3和4的倍数，故这个数一定是12的倍数

200以内的12的倍数有16个，加上{4，8}一共有18个数，当且仅当出现的数字为这18个数中间的，才有可能是先手必败情况

	memset(id,-1,sizeof(id));can.push_back(4),can.push_back(8);for(int i=12;i<=200;i+=12) can.push_back(i);
//处理出来所有可能数字int gs=can.size();for(int i=0;i<gs;i++) id[can[i]]=i;win[0]=1;for(int x=0;x<(1<<gs);x++){//枚举情况now.clear();int mx=0;for(int i=0;i<gs;i++){if(x&(1<<i)) now.push_back(can[i]),mx=max(mx,can[i]);}//这种情况使用的数字for(int i=1;i<=mx;i++){int s1=0,s2=0;for(int j=0;j<now.size();j++){int res=now[j]%i;if(!res) continue;if(res==1){s1|=(1<<1);continue;}if(res==2){s1|=(1<<2);continue;}if(id[res]==-1){s2=-1;break;}s2|=(1<<id[res]);}//先手必胜，意味着后手必败，所以需要找出来对i取模后有没有剩余情况必败if(!s2&&(s1==(1<<1)||s1==(1<<2))){//剩余的是1or2win[x]=true;break;}if(!s1&&(s2!=-1&&!win[s2])){//剩余的是必败win[x]=true;break;}}}

用数位dp的方法，先预处理出来这其中的哪些情况先手必败，再做数位dp求出来这种情况出现的总次数，用所有的情况数减去必败的情况数

这是说有数都大于2的情况

对于有数字小于等于2的情况，当且仅当全为1或者全为2时先手必败，特判处理

	dp[0][0]=1;ans=1;int cs=1;for(int x=1;x<=a;x++){ans=1ll*ans*n[x]%mod;for(int i=0;i<(1<<gs);i++){if(!dp[x-1][i]) continue;for(int j=0;j<gs&&can[j]<=n[x];j++){dp[x][i|(1<<j)]=(dp[x][i|(1<<j)]+dp[x-1][i])%mod;}}cs=cs*(n[x]>=2?1:0);//}//求出每种情况出现总次数for(int i=0;i<(1<<gs);i++){if(!win[i]) ans=(ans-dp[a][i]+mod)%mod;}ans-=cs;//全为2ans--;//全为1