欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

CodeForces - 1091D New Year and the Permutation Concatenation (打表)

程序员文章站 2022-06-05 13:48:15
...

????‍♂️ ????‍♂️ ????‍♂️
首先可以写出来这样的打表代码:

vi x,y;
inline void solve(int n)
{
    x.clear();y.clear();
    rpp(i,n) x.push_back(i);
    do
    {
        for(auto i:x) y.push_back(i);
    } while (next_permutation(all(x)));
    rep(i,sz(y)) if(i) y[i]+=y[i-1];
    int ans=1;
    for(int i=n;i<sz(y);++i) if(y[i]-y[i-n]==(n+1)*n/2) ++ans;
    cout<<"i:"<<n<<"    "<<"ans:"<<ans<<endl;
}
signed main()
{
    for(int i=1;i<=10;++i)
    {
        solve(i);
    }
    stop;
    return 0;
}

不过由于太暴力,只能计算前十个
CodeForces - 1091D New Year and the Permutation Concatenation (打表)打完之后观察,很容易推得满足题意的数组由两部分组成:n!个排列 + 不同排列各截取一部分,然后我们从打的表中把n!取出再看规律
CodeForces - 1091D New Year and the Permutation Concatenation (打表)

#define int ll
#define mod 998244353

int ans[MX];
signed main()
{
    ans[1]=1,ans[2]=2,ans[3]=9;
    int tag=6;
    for(int i=4;i<=1e6;++i) 
    {
        tag=tag*i%mod;
        ans[i]=(((ans[i-1]-1)%mod*i)%mod+tag)%mod;
    }
    int n;cin>>n;
    cout<<ans[n]<<endl;
    stop;
    return 0;
}