中位数

设是升序的，若，则，答案为。
否则，无论如何第小的数都不会是最后得到的数组中第小的数，此时只需把所有操作都加到第个。
时间复杂度。

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int N=2e5+5;
void ast(ll x,ll l,ll r){assert(x>=l&&x<=r);}
int n,k;
ll a[N];
int main()
{
    int t;scanf("%d",&t);
    ast(t,1,5);
    while(t--)
    {
        scanf("%d%d",&n,&k);
        ast(n,2,200000);
        for(int i=1;i<=n;i++) scanf("%lld",&a[i]),ast(a[i],1,200000);
        ast(k,1,n-1);
        sort(a+1,a+1+n);
        for(int i=n-k+1;i<=n;i++) a[n-k]+=a[i];
        n-=k;
        int m=(n+1)/2;
        printf("%lld\n",a[m]);
    }
}

k小数查询

由于是的排列，所以只出现一次。
设所在的位置为，令为中小于的数的个数，为中小于的个数。
答案为
用一个桶来计数，枚举即可。
时间复杂度。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
int n,x,k,a[N];
int sum[N],vis[N];
ll ans[N];
ll sol(int x,int k)
{
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++)
        sum[i]=sum[i-1]+(a[i]<x);
    ll ans=0;
    int flag=0;
    for(int i=1,l=0;i<=n;i++)
    {
        if(a[i]==x) flag=i;
        if(flag)
        {
            while(l<flag&&l<=i-k) vis[sum[l++]]++;
        }
        ans+=sum[i]-k+1>=0?vis[sum[i]-k+1]:0;
    }
    return ans;
}
int main()
{
    scanf("%d%d%d",&n,&x,&k);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    printf("%lld\n",sol(x,k));
}

牛老板

记忆化搜索，当较小时直接暴力。
当比较大时，设为恰好凑出元需要的纸币数量，此时优先用面值为的纸币，因为相对于用面值的纸币，我们省了张纸币，对同理。

upd

上面的方法被大佬了：
牛老板那题，所以答案至多是，标程输出了。
被后的再思考：对与这样的数，可能用了一个次方不会更优，从而需要多枚举一个。
对的数也同理，这时需要多枚举一个，但是多枚举的情况里包含了这种情况，不需要额外枚举。

对标程的错误向各位表示抱歉。万幸的是，数据都是正确的，对比赛没有造成重大影响。

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
unordered_map<ll,int>f;
vector<ll>v6,v9;
int F(ll n)
{
    if(n==0||f[n]) return f[n];
    f[n]=inf;
    int pos=upper_bound(v6.begin(),v6.end(),n)-v6.begin()-1;
    if(pos>=0)
        f[n]=min(f[n],F(n-v6[pos])+1);
    pos=upper_bound(v9.begin(),v9.end(),n)-v9.begin()-1;
    if(pos>=0)
        f[n]=min(f[n],F(n-v9[pos])+1);
    pos--;
    if(pos>=0)
        f[n]=min(f[n],F(n-v9[pos])+1);
    if(n<=5) f[n]=min(f[n],F(n-1)+1);
    return f[n];
}
int main()
{
    for(ll x=6;x<=1000000000000ll;x*=6) v6.push_back(x);
    for(ll x=9;x<=1000000000000ll;x*=9) v9.push_back(x);
    int t;scanf("%d",&t);
    while(t--)
    {
        ll n;scanf("%lld",&n);
        printf("%d\n",F(n));
    }
}

小G的排列-加强版

可以发现这个条件非常耀眼。
考虑用总排列数减去含有大于等于的连续段的排列的数量。
可以发现长度大于等于的连续段在序列中最多只会出现一次。
记为所有长度为的排列中长度为的连续段的出现的总次数，有。
考虑一个排列中有一个长度为的连续段，他恰好含有个长度为的连续段，含有个长度为的连续段（比长度为的连续段少一个），因此恰好为长度大于等于的连续段的个数。
因此答案为，预处理阶乘后，可以回答每个查询，时间复杂度。

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int N=10000005,mod=1e9+7;
ll f[N];
int n,m;
ll sol(int n,int m)
{
    if(m>n) return 0;
    return (n-m+1)*f[n-m+1]%mod*(m>1?2:1)%mod;
}
int main()
{
    f[0]=f[1]=1;
    for(int i=2;i<N;i++) f[i]=f[i-1]*i%mod;
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        ll ans=f[n]-sol(n,m+1)+sol(n,m+2);
        ans=(ans%mod+mod)%mod;
        printf("%lld\n",ans);
    }
}

贪吃蛇

设条蛇的长度为，不妨蛇。
我们看看在一瞬能发生什么： 条蛇被吃掉，剩下条蛇存活。
此时存活这条的蛇由于没蛇可吃，实际上也进入了冷却。
考虑如何吃蛇能让所有蛇变得尽可能的长。
第条吃掉第条，随后第条吃掉第条，...，最后第条吃掉第条。
这个时候第一条蛇变为最长，第二条第二长，...，第条第长。
模拟这个策略次即可得出答案。
但是这样复杂度太高，但这个过程可以通过构造一个矩阵来解决：

这个矩阵乘法得到的仍然升序。
构造出矩阵后进行矩阵快速幂即可。

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int N=55,mod=1e9+7,MS=55;
int n,x,M,L[N];
struct Mat
{
    ll a[MS][MS];
    int n,m;
    Mat(int n=0,int m=0):n(n),m(m) {memset(a,0,sizeof(a));}
    Mat operator*(const Mat&B)const
    {
        Mat C(n,B.m);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=B.m;j++)
                for(int k=1;k<=m;k++)
                C.a[i][j]=(C.a[i][j]+a[i][k]*B.a[k][j])%mod;
        return C;
    }
};
Mat qpow(Mat a,int n)
{
    Mat ans(a.n,a.n);
    for(int i=1;i<=a.n;i++) ans.a[i][i]=1;
    for(;n;n>>=1,a=a*a)
        if(n&1) ans=ans*a;
    return ans;
}
void ast(int x,int l,int r){assert(x>=l&&x<=r);}
int main()
{
    int t;scanf("%d",&t);
    ast(t,1,50);
    while(t--)
    {
        scanf("%d%d%d",&n,&x,&M);
        ast(n,1,50);
        ast(x,1,1000000);
        ast(M,1,1000000);
        for(int i=1;i<=n;i++) scanf("%d",&L[i]),ast(L[i],1,1000000);
        sort(L+1,L+1+n);
        reverse(L+1,L+1+n);
        M=M/x+1;
        Mat A(n,n);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n-i+1;j++)
            A.a[i][j]=1;
        A=qpow(A,M);
        ll ans=0;
        for(int i=1;i<=n;i++) ans=(ans+1ll*A.a[i][1]*L[i]%mod)%mod;
        printf("%lld\n",ans%mod);
    }
}

简洁的题面

对于一个固定的，考虑这个式子的组合意义：有个木板和种颜色，每个木板可以从种颜色里选一种颜色进行染色，或者不染色，有多少种方案使得每种颜色的出现次数都是的倍数。 和都比较小，于是可以用一个进制来表示染色状态，在各种状态之间建立转移边，再用矩阵快速幂加速计算。
具体的，设为已经对第块木板染色，第种颜色出现的数量，可以转移到




把压缩成进制状态，在转移之间建立有向边，问题等价于求图中状态到状态长度为的路径的数量。

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
int n,k,mod,g;
struct node
{
    ll a[27][27];
    int n;
    node(int n):n(n){memset(a,0,sizeof(a));}
    node operator*(const node&o)const
    {
        node ans(n);
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
            for(int k=0;k<n;k++)
            ans.a[i][j]=(ans.a[i][j]+a[i][k]*o.a[k][j])%mod;
        return ans;
    }
};
ll qpow(ll a,ll n)
{
    ll ans=1;
    for(;n;n>>=1,a=a*a%mod)
        if(n&1) ans=ans*a%mod;
    return ans;
}
node mqpow(node a,int n)
{
    node ans(a.n);
    for(int i=0;i<a.n;i++) ans.a[i][i]=1;
    for(;n;n>>=1,a=a*a)
        if(n&1) ans=ans*a;
    return ans;
}
int main()
{
    int t;scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d%d",&n,&k,&mod,&g);
        ll ans=0;
        for(int d=1;d<=g;d++)
        {
            if(d==1) ans=(ans+qpow(k+1,n))%mod;
            else
            {
                int st=1;
                for(int i=1;i<=k;i++) st*=d;
                node A(st);
                for(int i=0;i<st;i++)
                {
                    A.a[i][i]=1;
                    for(int j=0,h=1;j<k;j++,h*=d)
                    {
                        int s=i/h%d;
                        int sst=i-s*h;
                        s=(s+1)%d;
                        sst+=s*h;
                        A.a[i][sst]=1;
                    }
                }
                A=mqpow(A,n);
                ans=(ans+A.a[0][0])%mod;
            }
        }
        printf("%lld\n",ans);
    }
}