津原夜途
takanashi_mifuru · · 题解
考虑原问题是一个经典问题，我们使用 slope trick——从前往后枚举，把两个
考虑把这个式子化一下，最后的答案居然就是
要处理的信息太多了，考虑直接 01 化，于是我们就只关心
把这个东西直接拍到格路上，然后发现不会做！但是容易发现格路本身本质相同，不同的是往上/往下走的次数，然而变成这个形式还是不会做！因为一次运算就需要操纵
对系数打表吧！
#include<bits/stdc++.h>
using ll=long long;
using namespace std;
int testid,n,m,P;
int ans;
int power(int x,int y=P-2){
if(!y)return 1;
int tmp=power(x,y>>1);
if(y&1)return 1ll*tmp*tmp%P*x%P;
return 1ll*tmp*tmp%P;
}
int f[5005][5005];
int g[5005][5005];
void Add(int &x,int y){
if((x+=y)>=P)x-=P;
}
void Add(int &x,ll y){
x=(x+y)%P;
}
int dp[505][505][505];
void getf(int n){
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++)dp[n][i][0]=i;
for(int i=n-1;i>=0;i--){
for(int j=0;j<=i;j++){
for(int k=0;k<=n;k++){
Add(dp[i][j][k],dp[i+1][j+1][k]);
if(j&&k)Add(dp[i][j][k],dp[i+1][j-1][k-1]);
else if(k)Add(dp[i][j][k],dp[i+1][j][k-1]);
}
}
}
for(int i=0;i<=n;i++)f[n][i]=dp[0][0][i];
return;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)getf(i);
for(int i=1;i<=n;i++){
for(int j=0;j<=n;j++){
int tmp=f[i][j]-f[i-1][j];
if(j)tmp-=f[i-1][j-1];
printf("%6d ",tmp);
}
puts("");
}
return 0;
}//绝对更好的阅读体验
n=20
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 3 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 4 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 5 9 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 6 14 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 7 20 28 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 8 27 48 42 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 9 35 75 90 42 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 10 44 110 165 132 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 11 54 154 275 297 132 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 12 65 208 429 572 429 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 13 77 273 637 1001 1001 429 0 0 0 0 0 0 0 0 0 0 0 0 0
1 14 90 350 910 1638 2002 1430 0 0 0 0 0 0 0 0 0 0 0 0 0
1 15 104 440 1260 2548 3640 3432 1430 0 0 0 0 0 0 0 0 0 0 0 0
1 16 119 544 1700 3808 6188 7072 4862 0 0 0 0 0 0 0 0 0 0 0 0
1 17 135 663 2244 5508 9996 13260 11934 4862 0 0 0 0 0 0 0 0 0 0 0
1 18 152 798 2907 7752 15504 23256 25194 16796 0 0 0 0 0 0 0 0 0 0 0
设这个表格为
先做差，前两列的性质都还不错，第三列就爆了。
然后考虑递推，把每个点周围的数全部尝试一遍之后，我们发现
绝对更好的阅读体验
n=20
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 3 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 4 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 5 9 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 6 14 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 7 20 28 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 8 27 48 42 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 9 35 75 90 42 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 10 44 110 165 132 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 11 54 154 275 297 132 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 12 65 208 429 572 429 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 13 77 273 637 1001 1001 429 0 0 0 0 0 0 0 0 0 0 0 0 0
1 14 90 350 910 1638 2002 1430 0 0 0 0 0 0 0 0 0 0 0 0 0
1 15 104 440 1260 2548 3640 3432 1430 0 0 0 0 0 0 0 0 0 0 0 0
1 16 119 544 1700 3808 6188 7072 4862 0 0 0 0 0 0 0 0 0 0 0 0
1 17 135 663 2244 5508 9996 13260 11934 4862 0 0 0 0 0 0 0 0 0 0 0
1 18 152 798 2907 7752 15504 23256 25194 16796 0 0 0 0 0 0 0 0 0 0 0 设这个表格为
写出来拍一下发现居然是对的，后面就是随便做了，容易发现这是一个
#include<bits/stdc++.h>
using ll=long long;
using namespace std;
int testid,n,m,P;
int ans;
int power(int x,int y=P-2){
if(!y)return 1;
int tmp=power(x,y>>1);
if(y&1)return 1ll*tmp*tmp%P*x%P;
return 1ll*tmp*tmp%P;
}
int f[5005][5005];
int g[5005][5005];
void Add(int &x,int y){
if((x+=y)>=P)x-=P;
}
void Add(int &x,ll y){
x=(x+y)%P;
}
void getf(){
for(int i=1;i<=n;i++){
f[i][0]=i;
for(int j=1;j<i;j++){
if(j>=(i+1)/2)g[i][j]=0;
else{
if(j>1)g[i][j]=g[i-1][j]+g[i-1][j-1];
else g[i][j]=i-2;
}
if(g[i][j]>=P)g[i][j]-=P;
f[i][j]=g[i][j];
Add(f[i][j],f[i-1][j-1]);
Add(f[i][j],f[i-1][j]);
}
}
return;
}
int inv[10005];
int finv[10005];
int Y[5005];
int calc(int n,int X){
// printf("%d\n",Y[X]);
int sum=0;
for(int i=1;i<=n;i++){
int mul=Y[i];
for(int j=1;j<=n;j++){
if(i==j)continue;
if(i>j)mul=1ll*mul*(X-j+P)%P*inv[i-j]%P;
else mul=1ll*mul*(X-j+P)%P*finv[j-i]%P;
}
Add(sum,mul);
}
return sum;
}
int main(){
scanf("%d%d%d",&n,&m,&P);
for(int i=1;i<=2*n;i++)inv[i]=power(i),finv[i]=power(P-i);
ans=1ll*n*((1ll*(1+m)*m/2)%P)%P*power(m,n-1)%P;
getf();
for(int K=1;K<=n+2;K++){
int A=K-1,B=m-K+1;
int sum=0;
int mul=power(B,n);
B=power(B);
for(int j=0;j<=n;j++){
Add(sum,1ll*f[n][j]*mul);
mul=1ll*mul*A%P*B%P;
}
Y[K]=Y[K-1];
Add(Y[K],sum);
}
Add(ans,P-calc(n+2,m));
printf("%d\n",ans);
return 0;
}//