郑外—衡中欢乐赛之 一

胡扯

先水水感想。
大概就是 noip之前的攒人品系列 因为...又是一次正解+细节挂掉。
看来我代码实现确实可以去好好搞一下...
根据我的水平，我感觉基本上t1 t2苟出来基本就是正常水平了，t3乱搞了个状压骗了10分....
当然我只苟住了t1...

题解

T1

图片挂了（。）
果然还是要搭建博客的（。）

手推可以得到，对于每一次的操作 都可以简化成 $n*2$ 或者 $n-m=n-(sum-n)=n*2-sum$
所以总结一下就是

$$\begin{cases} n=n*2&(n<\frac{2}{n})\\ \\ n=n*2-sum&(n>\frac{2}{n}) \end{cases}$$

这不就是快速幂吗...
切之。

#include<cstdio>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
ll n,m,k,Q;
ll quick_pow(ll x,ll k)
{
    ll an=1;
    for(int i=k;i;i>>=1,x=x*x%Q)
        if(i&1) an=an*x%Q;
    return an;
}
int main()
{
    freopen("11.txt","r",stdin);
    freopen("1100.txt","w",stdout);
    cin>>n>>m>>k;
    Q=n+m;
    ll f=quick_pow(2,k);
    if(n>m) swap(n,m);
    n=n*f%Q;m=Q-n;
    if(n>m) swap(m,n);
    cout<<n;
    return 0;
}

T2

这就是gg了的题，没错

首先我们可以发现 每一个对子 $( a_x , a_y )$ 来说，我们可以将 $a_x$ 减去 $k$ ,这样我们就能保证在 $\sqrt{a_x}$ 的时间里面求出所有合法的 $a_y$ 了。（我们可以记录每一个数值的位置（注意这里是有重复的数字的，但是因为我们关心的是最近的在 $x$ 后面的，所以直接倒着扫就可以解决）
然后我们对于所有求出来的位置求一个后缀最小值（以防当前 $a_x$ 被后面某个 连累 。

强调！！！
当当前 $a_i == k$ 时，需要寻找其后面最近的大于 $k$ 的值。

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+5;
int a[N],end[N],pos[N],next[N],K,n;
int find(int x)
{
    int an=n+1;
    int k=a[x]-K;
    if(k==0)    return next[x];
    if(k<0) return n+1;
    for(int i=1;i*i<=k;++i)
    {
        if(k%i==0)
        {
            int t=k/i;
            if(pos[i]&&i>K) an=min(an,pos[i]);
            if(pos[t]&&t>K) an=min(an,pos[t]);
        }
    }
    return an;
}
void solve()
{
    long long ans=0;
    for(int i=n;i>=1;--i)
    {
        end[i]=find(i);
        pos[a[i]]=i;
    }
    long long minn=0x3f3f3f3f;
    for(int i=n;i>=1;--i)
    {
        minn=min((long long)end[i],minn);
        ans+=minn-i;
    }   
    cout<<ans;
}
inline int read()
{
    int x=0;char c=getchar();
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9')   x=x*10+c-'0',c=getchar();
    return x;
}
int main()
{
//  freopen("b.in","r",stdin);
//  freopen("110.txt","w",stdout);
    n=read(),K=read();
    for(int i=1;i<=n;++i)   a[i]=read();
    for(int i=n;i>=1;--i)
    {
        if(a[i]>K)
            next[i]=i;
        else
            next[i]=next[i+1];
    }
    solve();
    return 0;
}   

T3

先感谢一下噗噗的图片（。）

这道题很要命。

首先 我们可以知道 状压50是非常可做的。
但是明显过不了。

所以我们考虑，不记录具体的状态，改为记录相对不那么具体的，比如位置个数和颜色数。
对于这道题来说，在dp的时候是有两个限制条件的，我们考虑两个分开处理（当然在状压的时候就已经用到这种考虑了）
我们可以先求一下，对于每一个数量的格子，确定颜色数的颜色集合个数。
然后再可以根据这个，假装我们没有上下不同的限制，选择先算后减，减去重复的。
没什么太大的具体实现难度，主要是能不能想得到不记录状态，只记录格子数和颜色数。

#include<cstdio>
#include<algorithm>
#define ll long long 
using namespace std;
const int N=1e6+5;
const int M=5005;
ll A[M],a[N],fac[N],sum[2];
ll dp[2][N],f[M][M];//f[i][j]即为 第i行 染了j个的方案数
int n,m,Q,now=0,last=1;
void init()
{
    A[0]=1;
    for(int i=1;i<=m;++i)
        A[i]= A[i-1]*(m-i+1)%Q;
    fac[0]=1;
    for(int i=1;i<M;++i)
        fac[i]= fac[i-1]*i%Q;
    f[0][0]=1;
    for(int i=1;i<M;++i)
    {
        for(int j=1;j<=i;++j)
            f[i][j]=( f[i-1][j]*(j-1)%Q+f[i-1][j-1])%Q;
    }
}
void solve()
{
    dp[0][0]=1;sum[0]=1;
    for(int i=1;i<=n;++i)
    {   
        swap(now,last);
        sum[now]=0;
        for(int j=1;j<=a[i];++j)
        {
            dp[now][j]= A[j]*f[a[i]][j]%Q*sum[last]%Q;//假装不用管上下限制
            if(j<=a[i-1])
                dp[now][j]=(dp[now][j]- fac[j]*f[a[i]][j]%Q*dp[last][j]%Q+Q)%Q;
            //然后我们发现我们需要减去上下限制，这时候我们减去一个上一个重复的 fac代表排列 
            sum[now]=( sum[now]+dp[now][j])%Q;
        }
    }
    printf("%lld",sum[now]);
}
int main()
{
    scanf("%d%d%d",&n,&m,&Q);
    for(int i=1;i<=n;++i)   scanf("%d",&a[i]);
    init();
    solve();
    return 0;
}