需要一点数学思维的一套题，可惜我并没有，于是掉大分

看完题解之后觉得解法相当巧妙，决定写一写

A. Odd Set

题目地址

一句话题意

给定 $2n$ 个数，问是否存在一种将它们划分为 $n$ 个pair $(a,b)$ 的方法，使得每个pair的和为奇数

$n\le100$

解

显然一个pair的和为奇数当且仅当它由一个奇数和一个偶数组成

判断是否有奇数个数是否为 $n$ 即可

代码

略

B. Plus and Multiply

题目地址

一句话题意

给定一个集合 $S$ 满足

$1\in S$
如果 $x\in S$ ，那么 $ax\in S,x+b\in S$

给定T组 $n,a,b$ ，求 $n\in S?$

$T\le 10^5$

$1\le n,a,b\le 10^9$

解法

假设 $b\ne 1$

$n\in S$ 当且仅当存在 $m\in S$ 使得 $n\equiv m\pmod b$ 且 $m<n$

显然，要构造出一个新的 $m\space mod\space b$ ，只能采取 $\times a$ 操作，因此 $m$ 必然是 $a$ 的幂

判断是否存在 $a^k<n$ 满足 $n\equiv a^k\pmod b$ 即可

特判 $b=1$ 的情况，显然答案恒为Yes

复杂度 $O(\log n)$

代码

#include <iostream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long ll;

template<typename T>void read(T &t)
{
    t=0;int f=0;char c=getchar();
    while(!isdigit(c)){f|=(c=='-');c=getchar();}
    while(isdigit(c)){t=t*10+c-'0';c=getchar();}
    if(f)t=-t;
}

int T;
ll n,a,b;

void Work()
{
    read(n),read(a),read(b);
    if(b==1)
        printf("Yes\n");
    else if(a==1)
    {
        if(n%b==1)
            printf("Yes\n");
        else
            printf("No\n");
    }
    else
    {
        ll k=n%b;
        for(ll cur=1;cur<=n;cur*=a)
        {
            if(cur%b==k)
            {
                printf("Yes\n");
                return;
            }
        }
        printf("No\n");
    }
}

int main()
{
    read(T);
    while(T--)
    {
        Work();
    }
    return 0;
}

C. Strange Function

题目地址

一句话题意

$f(n)$ 表示最小的不是 $n$ 的因数的正整数

计算 $\sum_{i=1}^nf(i)\space mod\space (10^9+7)$

$t(t\le 10^4)$ 组数据

$n\le 10^{16}$

解法

注意到 $f(n)=i$ 的含义是 $lcm(1,2,\dots,i-1)\le n$ ， $f(n)$ 的值很小(小于 $100$ ），因此可以枚举 $f(i)$ 。

满足 $f(k)=i$ 的 $k$ 的数量是 $\lfloor \frac{n}{lcm(1,2,\dots,i-1)}\rfloor-\lfloor \frac{n}{lcm(1,2,\dots,i)}\rfloor$ ，亦即 $k$ 可以被 $1,2,\dots,i-1$ 整除而不能被 $i$ 整除

于是答案即为 $\sum_{i>1}\lfloor \frac{n}{lcm(1,2,\dots,i-1)}\rfloor-\lfloor \frac{n}{lcm(1,2,\dots,i)}\rfloor$

上式还可以表示为 $\sum_{i\ge1}\lfloor \frac{n}{lcm(1,2,\dots,i)}\rfloor+n$

代码

#include <iostream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long ll;

template<typename T>void read(T &t)
{
    t=0;int f=0;char c=getchar();
    while(!isdigit(c)){f|=(c=='-');c=getchar();}
    while(isdigit(c)){t=t*10+c-'0';c=getchar();}
    if(f)t=-t;
}

const ll mod=1000000007;
int T;
ll n;

ll Gcd(ll a,ll b)
{
    return b?Gcd(b,a%b):a;
}

inline ll Lcm(ll a,ll b)
{
    return a/Gcd(a,b)*b;
}

void Work()
{
    read(n);
    ll lcm=1,ans=0;
    for(ll i=1;lcm<=n;++i)
    {
        lcm=Lcm(lcm,i);
        (ans+=n/lcm)%=mod;
    }
    printf("%lld\n",(ans+n)%mod);
}

int main()
{
    read(T);
    while(T--)
    {
        Work();
    }
    return 0;
}

Tips！

对于值较小的函数的和，可以枚举函数的值、计算值对应变量的个数来将复杂度转移到函数值上

D. Priority Queue

题目地址

一句话题意

对于一个对小根堆进行操作的序列 $S$ ，其中各元素的形式为+ x或-，分别表示入堆和出堆。设 $f(S)$ 表示依照序列 $S$ 对小根堆进行操作后，堆中所有元素的和

给定一个序列 $A$ ，求 $\sum f(B)\mod 998244353$ ，其中 $B$ 是 $A$ 的子序列

$n\le 500$

解法

我们可以计算堆中元素 $x$ 的贡献

假设我们已经在第 $I$ 个操作中加入了 $x$ ，设为 $X$ ，那么 $X$ 有贡献的子序列 $B$ 满足：

包含第 $I$ 个操作
设 $s$ 表示当前堆中小于等于 $x$ 的元素个数，不管在第 $I$ 个操作后遇到多少个-操作， $s$ 必须大于0（除了序列执行结束后）

可以得到以下DP：

设 $f(i,j)$ 表示满足完成操作后 $s=j$ 的 $A[1\dots i]$ 的子序列个数

转移：

$f(i-1,j)\rightarrow f(i,j)$ ，不包含第 $i$ 个操作， $i\neq I$
$f(i-1,j)\rightarrow f(i,max(j-1,0))$ ，包含第 $i$ 个操作， $i<I$ 且该操作为-
$f(i-1,j)\rightarrow f(i,j-1)$ ，包含第 $i$ 个操作， $i>I$ 且该操作为-，此时 $j$ 不可以为 $0$
$f(i-1,j)\rightarrow f(i,j)$ ，包含第 $i$ 个操作且该操作为+ x，其中 $x>X$
$f(i-1,j)\rightarrow f(i,j+1)$ ，包含第 $i$ 个操作且该操作为+ x，其中 $x<X$ ；或 $x=X$ 且 $i>I$

$X$ 对答案的贡献为 $X\times\sum_{i\ge 0}f(n,i)$

复杂度 $O(n^3)$

代码

#include <iostream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long ll;

template<typename T>void read(T &t)
{
    t=0;int f=0;char c=getchar();
    while(!isdigit(c)){f|=(c=='-');c=getchar();}
    while(isdigit(c)){t=t*10+c-'0';c=getchar();}
    if(f)t=-t;
}

const ll mod=998244353;
const int maxn=500+5;
int n;
int a[maxn];
ll dp[maxn][maxn];

int main()
{
    read(n);
    for(int i=1;i<=n;++i)
    {
        char s[10];
        gets(s);
        if(s[0]=='+')sscanf(s+1,"%d",&a[i]);
    }
    ll ans=0;
    for(int t=1;t<=n;++t)
    {
        if(a[t]==0)
            continue;
        memset(dp,0,sizeof(dp));
        dp[0][0]=1;
        for(int i=1;i<=n;++i)
            for(int j=0;j<=i;++j)
            {
                if(a[i]==0)
                {
                    if(i<=t || j>0)
                        (dp[i][max(j-1,0)]+=dp[i-1][j])%=mod;//case 2&3
                }
                else
                {
                    if(a[i]<a[t] || a[i]==a[t] && i<t)
                        (dp[i][j+1]+=dp[i-1][j])%=mod;//case 5
                    else
                        (dp[i][j]+=dp[i-1][j])%=mod;//case 4
                }
                if(i!=t)
                    (dp[i][j]+=dp[i-1][j])%=mod;//case 1
            }
        for(int i=0;i<=n;++i)
            (ans+=dp[n][i]*a[t]%mod)%=mod;
    }
    printf("%lld",ans);
    return 0;
}