C Optimal Strategy

[题目链接](https://pintia.cn/problem-sets/1459829212832296960/problems/1459829264400629762)

Ena and Mizuki are playing a game.

There are **n** items in front of them, numbered from **1** to **n**. The value of the **i**-th item is **a****i******. Ena and Mizuki take turns to move, while Ena moves first. In a move, the player chooses an item that has not been taken and takes it away. The game ends when all items are taken away. The goal of either player is to maximize the sum of values of items they have taken away.

Given that both players move optimally, how many possible game processes are there? Since the number may be too large, you should output it modulo **998****244****353**.

Two processes are considered different if there exists some integer **i****(****1****≤****i****≤****n****)** such that the indices of items taken away in the **i**-th move are different.

### Input

The first line contains an integer **n** (**1****≤****n****≤****1****0****6**).

The second line contains **n** integers **a****1********,****a****2********,****…****,****a****n****** (**1****≤****a****i********≤****n**).

### Output

Output the answer.

### Sample Input 1

```in
3
1 2 2
```

### Sample Output 1

```out
4
```

### Sample Input 2

```in
6
1 3 2 2 3 1
```

### Sample Output 2

```out
120
```

### Sample Input 3

```in
12
1 1 4 5 1 4 1 9 1 9 8 10
```

### Sample Output 3

```out
28800
```

### Explanations

In the first example, there are four possible processes:

* **[****1****,****2****,****3****]**.
* **[****1****,****3****,****2****]**.
* **[****2****,****3****,****1****]**.
* **[****3****,****2****,****1****]**.

Here **[****a****,****b****,****c****]** means that in the first move Ena takes away the **a**-th item, in the second move Mizuki takes away the **b**-th item, and in the final move Ena takes away the **c**-th item.

Note that **[****2****,****1****,****3****]** is not a possible process, since the second move is not optimal for Mizuki.

```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6+10;
const LL mod = 998244353;
LL f[N],fn[N];
int n;
int a[N];
LL mpow(LL x,LL n)
{
    x%=mod;
    //if(x==0) return 1;
    LL res=1;
    while(n)
    {
        if(n&1) res = (res * x)%mod;
        x = (x * x)%mod;
        n>>=1;
    }
    return res;
}
void init()
{
    f[0]=1;
    f[1]=1;
    for(int i=2;i<=1000005;i++)
    {
        f[i]=(f[i-1]*i)%mod;
    }
    fn[1000005]=mpow(f[1000005],mod-2);
    for(int i=1000004;i>=0;i--)
    {
        fn[i]=(fn[i+1]*(i+1))%mod;
    }

}
LL fun(LL res,LL p)
{
    return ( ( f[res+p]*fn[res] )% mod * fn[p] )%mod;
}
int main()
{
    init();
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    sort(a+1,a+n+1);
    LL res=n,cnt=0;
    LL ans = 1;
    int flg=a[n];
    a[0]=-1;
    for(int i=n;i>=0;i--)
    {
        if(a[i]==flg)
        {
            cnt++;
        }
        else
        {
            LL p = cnt/2;
            res = res - cnt;
            ans = ( ( ans * fun(res,p) )%mod * f[cnt] )%mod;
//            cout<<flg<<"  "<<cnt<<"  "<<res<<"  "<<fun(res,p)<<"  "<<ans<<endl;
            cnt=1;
            flg=a[i];
        }
    }
    printf("%lld\n",ans);
}

```

will us

C Optimal Strategy

评论已关闭

分类

标签

归档

其它