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)\)的方案数
\[ans=\sum_{i=1}^nF(len>=i)
\]
\[ans=\sum_{i=1}^n (m^n -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)\)
\[\sum_{i=0}^{n-1}\sum_{j=0}^{n}m\times (m-1)^{j-1}\sum_{k=0}^j(-1)^kC(j,k)C(n-ik-1,j-1)
\]
把\(k\)枚举提前
美化一下
\[m\times \sum_{i=0}^{n-1} \sum_{k=0}^n(-1)^k\frac{1}{n-ik} \sum_{j=k}^{n} (m-1)^{j-1}C(j,k)C(n-ik,j)j
\]
发现必须满足\(k+ik<=n\)所以枚举\(k\)是调和级数的复杂度
考虑后面部分的组合意义
从\(n-ik\)中选\(j\)个，再从\(j\)个中选\(k\)个，再从\(j\)个中选一个特殊的,再将剩下的\(j-1\)个染成\(m-1\)种颜色
分两种情况，
一种\(k\)中选一个特殊的,对于剩下的染色有\((m-1+不染)=m\)
一种在\(n-ik-k\)中选一个特殊的
\[\sum_{j=k}^{n} (m-1)^{j-1}C(j,k)C(n-ik,j)j=C(n-ik,k)((m-1)^k(n-ik-k)m^{n-ik-k-1}+k(m-1)^{k-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
