P2220 [HAOI2012] 容易题 题解

· · 题解

P2220 [HAOI2012] 容易题 题解

题目大意

传送门。

解题思路

第一档部分分

对于 30\% 的数据，n \leq 4，m \leq 10，k \leq 10。

直接 O(m!n+m!k) 暴搜统计，拿下 30 分。

void dfs(int pos,long long tmp){
    //cout<<pos<<endl;
    if(pos==m){
        ans+=tmp;
        ans%=mod;
        return;
    }
    for(int i=1;i<=n;i++){
        bool flag=false;
        for(int j=1;j<=k;j++){
            if(lim[j].p==pos+1&&lim[j].v==i){
                flag=true;
                break;
            }
        }
        if(!flag) dfs(pos+1,(tmp*i)%mod);       
    }
}

特殊情况（第二档部分分）

对于另外 20\% 的数据，k = 0。

考虑推导没有限制的特殊情况（假定 n 不变）。

记 f_i（i 为正整数）为当 A 没有限制时，所有可能数列的积。

显然，当 i=1 时，只有 1,2,\dots,n 这几种可能。

那么，f_1=1+2+\dots+n=\frac{(n+1)n}{2}

对于每一个长度为 i 的 A，都可以从 长度为 i-1 的 A 后拼接 1,2,\dots,n 来得到，那么 f_{i} 的所有情况都可以用 f_{i-1} 拼接 1,2,\dots,n 去计算。

得到递推式：f_i=\frac{(n+1)n}{2}f_{i-1}。

通项，得 f_i=(\frac{(n+1)n}{2})^i。

此时，我们得到了 k=0 时的特殊做法：直接写快速幂算上面那个通项就行了。

时间复杂度为 O(\log{m})。

相信大家都会快速幂，就不放代码了吧。

第三档部分分

对于 70\% 的数据，n, m, k \leq 1000。

在 k=0 时，我们可以得到一个通项快速计算。但是存在限制时，只能一个一个递推，查找对应的限制，减去不能拼接的数，从 f_{i-1} 算出 f_i（f 的意义同上）。

时间复杂度为 O(mk)。

核心代码：

f[0]=1;
for(int i=1;i<=m;i++){
    f[i]=n*(n+1)/2*f[i-1];
    memset(vst,false,sizeof(vst));
    for(int j=1;j<=k;j++){
        if(lim[j].p==i&&!vst[lim[j].v]){
            f[i]-=lim[j].v*f[i-1];
            vst[lim[j].v]=true;
        }
    }
}
cout<<f[m];

正解

我们发现，第三档部分分做法的复杂度瓶颈在 m。

递推的时候，有很多没限制的地方可以直接计算，跳过去。

所以，只对存在限制的地方特别计算，剩下的直接用快速幂求即可。

时间复杂度为 O(k\log{m})。

参考代码

#include<algorithm>
#include<iostream>
using namespace std;
#define int long long
const int N=1e6+10;
const int mod=1e9+7;
struct ccf{
    int p,v;
    friend bool operator==(ccf a,ccf b){
        return a.p==b.p&&a.v==b.v;
    }
}lim[N];
bool cmp(ccf pre,ccf nxt){
    if(pre.p!=nxt.p) return pre.p<nxt.p;
    else return pre.v<nxt.v;
}
int qpow(int x,int mi){
    int ans=1;
    while(mi){
        if(mi&1){
            ans*=x;
            ans%=mod;
        }
        x*=x;
        x%=mod;
        mi>>=1;
    }
    return ans%mod;
}
int fft=1;
int n,m,k;
signed main(){
    ios::sync_with_stdio(false);
    cin>>n>>m>>k;
    if(k==0){
        cout<<qpow(((n+1)*n/2)%mod,m);
        return 0;
    }
    for(int i=1;i<=k;i++){
        cin>>lim[i].p>>lim[i].v;
    }
    lim[k+1]={m,0};
    sort(lim+1,lim+k+2,cmp);
    int k1=unique(lim+1,lim+k+2)-lim;
    int tmp=0,last=0; 
    for(int i=1;i<=k1;i++){
        tmp+=lim[i].v;
        if(lim[i].p!=lim[i+1].p){
            fft*=qpow((n*(n+1)/2)%mod,lim[i].p-last-1);
            fft%=mod;
            fft*=((n*(n+1)/2)%mod-tmp%mod+mod)%mod;
            fft%=mod;
            last=lim[i].p;
            tmp=0;
        }   
    }
    cout<<fft%mod;
    return 0;
}

赛时写得比较丑陋。

注意事项

写代码时要特别注意取模的细节，不然你的正解会被卡在 70pts~90pts 左右！

Written by toolong114514 on 2024/3/16.

没见过题目名字这么嚣张的。