AtCoder Regular Contest 116（A-D）

A、Odd vs Even

editorial

已知对于给定数字(n)，他的因子可以表示成(prodlimits_{i=1}^{m}p_i^{cnt_i})，其中(p_i)是n的素因子，(cnt_i in [0,a_i]), (a_i)是满足([n mod p_i^{a_i} = 0])这个条件的最大值。

故知若(2^{a_i})中的(a_i)大于1时，偶因子多于奇因子个数；两者相等时，偶因子等于奇因子个数；否则，偶因子少于奇因子个数。

code

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        ll n;
        scanf("%lld", &n);
        if(n % 4 == 0)
            puts("Even");
        else if(n % 2 == 0 )
            puts("Same");
        else
            puts("Odd");
    }
    return 0;
}

B、Products of Min-Max

editorial

首先我们对该序列进行排序，发现就可以固定两端，中间是否选择，共有(2^{max(0,j-i+1)})中选择，故答案为

[sumlimits_{i=1}^nsumlimits_{j=i}^na_i*a_j*2^{max(0,j-i-1)}=sumlimits_{i=1}^na_i*sumlimits_{j=i}^na_j*2^{max(0,j-i-1)} =sumlimits_{i=1}^na_i*sumlimits_{j=i+1}^na_j*2^{j-i-1}+sumlimits_{i=1}^na_i^2 ]
观察式子发现

(sumlimits_{j=i}a_j*2^{j-i}=2*sumlimits_{j=i+1}a_j*2^{j-i}+a_i)

故我们从后往前计算。

code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int NMAX = 2e5 + 10;
const int MOD = 998244353;
 
int a[NMAX];
int main()
{
    int n;
    scanf("%d", &n);
    ll ans = 0, ant;
    for(int i = 1;i <= n;i++)   
    {
        scanf("%d", a + i);
        ans = (ans + 1ll*a[i]*a[i]%MOD)%MOD;
    }
    sort(a + 1, a + 1 + n);
    ant = a[n];
    for(int i = n-1;i >= 1;i--)
    {
        ans = (ans + ant*a[i]%MOD)%MOD;
        ant = (ant*2%MOD + a[i])%MOD;
    }
    printf("%lld
", ans);
    return 0;
}

C、Multiple Sequences

editorial

对于整数(m),连续的因子序列（因子序列中元素互不相等），最大长度为(lfloorlog_2m floor)，故进行dp，(dp[i][j])表示最后一位数字，当前序列长度为(i)的可能情况。

而对于原问题的序列我们可以通过我们的序列进行扩展，即将长度为(i)的序列扩展成长度为(n)，即可以想象把长度为(n)的序列划分为(i)段，用插空法求出有((n-1,i-1))种方式,故答案为(sumlimits_{i=1}^{20}(n-1,i-1)*(sumlimits_{j=1}^mdp[i][j]))

code

#include<bits/stdc++.h>
 
using namespace std;
const int NMAX = 2e5 + 10;
const int MOD = 998244353;
typedef long long ll;
 
ll dp[20][NMAX], sum[20];
ll f[NMAX],finv[NMAX];
ll fast_pow(ll a,ll n)
{
    ll ans = 1;
    while(n)
    {
        if(n&1) ans = (ans * a)%MOD;
        a = (a * a)%MOD;
        n >>= 1;
    }
    return ans;
}
ll C(ll n,ll m)
{
	return (n<0||m<0||n<m)?0:f[n]*(finv[m])%mod*finv[n-m]%mod;
}
void init()
{
    f[0]=1;
    for(int i=1;i< NMAX;i++)
        f[i]=f[i-1]*i%mod;
    finv[NMAX-1] = fast_pow(f[NMAX-1],mod-2);
    for (int i=NMAX-1; i > 0; i--)
        finv[i-1]=finv[i]*i%mod;
}	
int main()
{
    int n, m;
    init();
    scanf("%d%d", &n, &m);
    for(int i = 1;i <= m;i++)   dp[1][i] = 1;
    sum[1] = m%MOD;
    for(int j = 2;j < 20;j++)
    {
        for(int i = 1;i <= m;i++)
            for(int k = 2*i; k <= m;k += i)
                dp[j][k] = (dp[j][k] + dp[j-1][i])%MOD;
        for(int i = 1;i <= m;i++)
            sum[j] = (sum[j] + dp[j][i])%MOD;
    }
    
    ll ans = 0;        
    for(int i = 1;i < 20;i++)
        ans = (ans + C(n-1, i-1)*sum[i]%MOD)%MOD;  
    printf("%lld
", ans);
    return 0;
}

D、Wanna Win The Game

editorial
官方题解
(sum A_i)为偶数时，(Xor A_i)才可能存在情况数，对于所有的(A_i)二进制，固定位的(1)的个数必然为偶数。那我们从低位往高位开始，构造序列(A)。
定义(dp[i])为(m=i)的答案，首先构造最后一位，即对于偶数(m)，将(m)个(1)放到(n)个位置（保证一个位置至多只有一个一），共有((n, m))中方案。用之前的方案数来更新当前的情况，即在原来的序列每个元素左移一位，然后选择(2j)个(1),分别加到序列(A)中，故有转移方程如下：

[ dp[i*2+j] = 1ll*(dp[(i<<1)+j] + 1ll*dp[i]*C[n][j] mod MOD) mod MOD iff jequiv0pmod{2} ]

code

#include <bits/stdc++.h>
using namespace std;

const int MOD = 998244353;
const int NMAX = 5e3 + 5;

typedef long long ll;

int C[NMAX][NMAX];
int dp[NMAX];
void init()
{
    C[0][0] = 1;
    for(int i = 1;i < NMAX;i++)
    {
        C[i][0] = 1;
        for(int j = 1;j <= i;j++)
            C[i][j] = (C[i-1][j] + C[i-1][j-1])%MOD;
    }
}

int main()
{
    init();
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 2;i <= m;i += 2)
        dp[i] = C[n][i];
    for(int i = 1;i <= m;i++)
        for(int j = 0;(i<<1)+j <= m;j += 2)
            dp[i*2+j] = 1ll*(dp[(i<<1)+j] + 1ll*dp[i]*C[n][j]%MOD)%MOD;
    printf("%d
", dp[m]);
    return 0;
}