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;
}
不过由于太暴力,只能计算前十个
打完之后观察,很容易推得满足题意的数组由两部分组成:n!个排列 + 不同排列各截取一部分,然后我们从打的表中把n!取出再看规律
#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;
}