E
题面
最暴力的做法，枚举连续段长度\(i\),然后暴力搜索,复杂度\(O(n^3)\)
点击查看代码
#include <bits/stdc++.h>
#define speed() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define ll long long
#define pb push_back
#define ull unsigned long long
#define pii pair<int,int>
#define lid (rt<<1)
#define rid (rt<<1|1)
#define file(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);
#define ts cout<<"************"<<endl;
using namespace std;
const int N = 5000+5,INF=1E9;
inline int read()
{
int x=0,f=1;char ch=getchar_unlocked();
for(;ch<'0'||ch>'9';ch=getchar_unlocked())if(ch=='-')f=-1;
for(;ch>='0'&&ch<='9';ch=getchar_unlocked())x=(x<<3)+(x<<1)+(ch^48);
return x*f;
}
inline void write(ll x)
{
if(x<0)x=-x,putchar_unlocked('-');
if(x>9)write(x/10);
putchar_unlocked((x%10)|48);
}
ll mod;
ll n,m;
ll dp[N][N];ll tot;
inline ll work(int len,int id,int mx)
{
if(dp[len][mx])return dp[len][mx];
if(id>mx&&len<id)return 0;
if(!len)return mx==id;
ll ans=0;
// cout<<(m-(len==n))<<endl;
for(int i=1;i<=min(len,id);i++)
{
ans=(ans+ work( len-i,id,max(mx,i) )*(m-(len!=n))%mod )%mod;
}
// cout<<id<<" "<<ans<<endl;
return dp[len][mx]=ans;
}
int main(int argc, char const *argv[])
{
file("a");
// freopen("sequence.in","r",stdin);freopen("sequence.out","w",stdout);
n=read();m=read();mod=read();
for(ll i=1;i<=n;i++)
{
// cout<<work(n,i,0)<<endl;
for(int j=0;j<=n;j++)
for(int k=0;k<=i;k++)dp[j][k]=0;
tot+=work(n,i,0)*i%mod;
// ts;
tot%=mod;
}
write(tot);
return 0;
}
//10 2 998244353
//100 23333333 998244353
考虑优化,
设$$ans=\sum_{i=1}^n方案数(len=i)$$
设\(F(len<i)\)的方案数
考虑计算
\[\sum_{i=0}^{n-1}F(len<=i) \]考虑枚举分成\(j\)段
如果没有\(<=i\)的限制，插空法可知为\(C(n-1,j-1)\)
但是有限制，考虑容斥，钦定有\(k\)个元素\(>i\),因为不能有空,则下界为\(i\),则有\(k\)个元素\(>i\),这时候再插空的话,为\(C(n-ik-1,j-1)\)
把\(k\)枚举提前
美化一下
发现必须满足\(k+ik<=n\)所以枚举\(k\)是调和级数的复杂度
考虑后面部分的组合意义
从\(n-ik\)中选\(j\)个，再从\(j\)个中选\(k\)个，再从\(j\)个中选一个特殊的,再将剩下的\(j-1\)个染成\(m-1\)种颜色
分两种情况，
一种\(k\)中选一个特殊的,对于剩下的染色有\((m-1+不染)=m\)
一种在\(n-ik-k\)中选一个特殊的
复杂度\(O(n\log n)\)
点击查看代码
#include <bits/stdc++.h>
#define speed() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define ll long long
#define pb push_back
#define ull unsigned long long
#define pii pair<int,int>
#define lid (rt<<1)
#define rid (rt<<1|1)
#define file(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);
#define ts cout<<"************"<<endl;
using namespace std;
const int N = 3e5+5,INF=1E9;
inline int read()
{
int x=0,f=1;char ch=getchar_unlocked();
for(;ch<'0'||ch>'9';ch=getchar_unlocked())if(ch=='-')f=-1;
for(;ch>='0'&&ch<='9';ch=getchar_unlocked())x=(x<<3)+(x<<1)+(ch^48);
return x*f;
}
inline void write(ll x)
{
if(x<0)x=-x,putchar_unlocked('-');
if(x>9)write(x/10);
putchar_unlocked((x%10)|48);
}
ll mod;
ll n,m;
ll tot;
inline ll qpow(ll a, ll b)
{
ll ans=1;
while(b)
{
if(b&1)ans=ans*a%mod;
a=a*a%mod;b>>=1;
}
return ans;
}
ll m1[N],mm[N],jie[N],inv[N];
inline ll C(int n,int m)
{
return jie[n]*inv[m]%mod*inv[n-m]%mod;
}
// #define int long long
ll iv[N];
signed main()
{
// file("a");
freopen("sequence.in","r",stdin);freopen("sequence.out","w",stdout);
n=read();m=read();mod=read();
ll ans=0;
m1[0]=mm[0]=1;
for(int i=1;i<=n;i++)m1[i]=m1[i-1]*(m-1)%mod,mm[i]=mm[i-1]*m%mod;
jie[0]=1;inv[0]=1;
for(int i=1;i<=n;i++)jie[i]=jie[i-1]*i%mod;
inv[n]=qpow(jie[n],mod-2);
for(int i=n-1;i>=1;i--)inv[i]=inv[i+1]*(i+1)%mod;
iv[1]=1;
for(int i=2;i<=n;i++)
{
iv[i]=(mod-mod/i)*iv[mod%i]%mod;
}
for(ll i=0;i<=n-1;i++)
{
ll cnt=1;ll val=0;
for(ll k=0;i*k+k<=n;k++)
{
// if(n-i*k-k-1<0)break;
val=(val+ cnt*iv[n-i*k]*( m1[k]%mod*(n-i*k-k)%mod*mm[max<int>(n-i*k-k-1,0)]%mod+k*m1[k-1]%mod*mm[n-i*k-k]%mod )%mod*C(n-i*k,k)%mod )%mod;
val=(val+mod)%mod;
// val=val*C(n-i*k,k)%mod;
cnt=-cnt;
}
ans=(ans+val)%mod;
}
ans=ans*m%mod;
ans=(n*mm[n]%mod-ans+mod)%mod;
write(ans);
return 0;
}
//10 2 998244353
//100 23333333 998244353