Problem statement: http://www.codechef.com/COOK59/problems/ANKGAME
Problem Analysis:
How can we know who wins the game if we already know the order of the piles?
Let denote who wins the game if we consider only the last piles. By convention if the first player always wins and otherwise.
Note that . because the first player can remove all stones and win. So now let’s analyse what happens when . There are two cases:
Case 1.
If the number of stones in the pile is equal to , then the first player always loses (because he will be the second player on pile i+1). On the other hand, if the number of stones on pile is greater than , then the first player can erase all stones minus one (In this way he will be the first player on pile i+1).
Case 2.
The optimal strategy for the first player is to remove all stones of pile (in this way he will be the second player on pile i+1)
With that in mind, we can construct a recurrence that calculates the number of pile permutations in which the first player always wins.
The only case in which the first player loses is when the number of stones of the first pile is 1, and (note that this is valid only when , indeed I didn’t notice this in my first submission)
Let denote the number of ways in which the first player wins, if we have already used piles of one stone. It is easy to calculate by complementation: is the total permutations of piles if we don’t use piles of one stone (this can be easily calculated with the multinomial) minus the number of ways in which the first player loses. The nice fact is that the number of ways in which the first player loses is equal to the number of ways in which the first player wins if we have used one more pile of one stone.
In Iverson notation:
, where is the number of piles with stones.
I got AC on this question 40 seconds before the end of the contest 🙂
p.s Be careful,
As usual, my awesome implementation:
#include<bits/stdc++.h> using namespace std; typedef long long int uli; const uli mod=1e9+7; const int mx=1e5+10; uli fa[mx],fi[mx],d[mx]; int n,n1; uli ivs; uli fxp(uli b,uli x,uli m){ uli a=1; for(;x!=0;b=b*b%m,x>>=1) if(x&1ll)a=a*b%m; return a; } inline uli solve(int u){ uli cmb=fa[n-u]*fi[n1-u]%mod*ivs%mod; if(u==n1){ if(n==u)return 0; return cmb; } return (cmb-solve(u+1)+mod)%mod; } int main(){ fa[0]=fi[0]=1; for(int i=1;i<mx;i++){ fa[i]=fa[i-1]*uli(i)%mod; fi[i]=fxp(fa[i],mod-2,mod); } int t; scanf("%d",&t); while(t--){ scanf("%d",&n); n1=0; for(int i=0;i<n;i++){ scanf("%lld",d+i); if(d[i]==1)n1++; } sort(d,d+n); ivs=1; for(int i=0;i<n;){ uli v=d[i]; int qv=0; while(i<n && d[i]==v) i++,qv++; if(v!=1)ivs=ivs*fi[qv]%mod; } uli ans=solve(0); printf("%lld\n",ans); } return 0; }