#include<bits/stdc++.h> using namespace std; typedef long long ll; #define fi first #define se second int n,m,k,y; ll mod; const int iu=1e6; ll f[iu+1],inf[iu+1]; ll pw(ll x,ll y){ if(y==0) return 1; if(y%2) return x*pw(x,y-1)%mod; ll res=pw(x,y/2); return res*res%mod; } ll C(ll x,ll y){ return f[x]*inf[y]%mod*inf[x-y]%mod; } int st[20]; int en[20]; int filled[1<<20]; ll dp[1<<20]; ll tab1(){ for(int i=0; i<n ;i++){ st[i]=i-k+1; en[i]=st[i]+m; st[i]=max(st[i],0); } for(int i=0; i<n ;i++) filled[1<<i]=en[i]-st[0]; for(int i=1; i<(1<<n) ;i++){ int id=__builtin_popcount(i); if(i!=(i&-i)) filled[i]=filled[i^(i&-i)]+filled[i&-i]+st[0]-st[id-1]; } /*for(int i=0; i<(1<<n) ;i++) cout << filled[i] << ' '; cout << endl;*/ dp[0]=1; for(int i=0; i<(1<<n)-1 ;i++){ int id=__builtin_popcount(i); int sgn=1; for(int j=n-1; j>=0 ;j--){ if((i>>j)&1){ sgn=-sgn; continue; } ll ways; if(st[id]==0){ ways=C(filled[i]+en[j]-1,en[j]-1); } else{ ways=C(filled[i]+en[j]-st[id],en[j]-st[id]); } //cout << "trans " << i << ' ' << (i|(1<<j)) << ' ' << sgn << ' ' << ways << endl; if(sgn==-1) ways=(mod-ways); dp[i|(1<<j)]=(dp[i|(1<<j)]+dp[i]*ways)%mod; } } return dp[(1<<n)-1]; } int g[25][50005],h[25][50005]; ll tab2(){ int tot=0; ll res=1; for(int i=n; i>=1 ;i--){ for(int j=m; j>=1 ;j--){ if(i+j+k-1<=n+m){ g[i][j]=g[i+1][j]+1; h[i][j]=h[i][j+1]+1; res=res*f[g[i][j]+h[i][j]-2]%mod*inf[g[i][j]+h[i][j]-1]%mod; ++tot; } } } res=res*f[tot]%mod; y=tot; //cout << res << endl; return res; } int main(){ ios::sync_with_stdio(false);cin.tie(0); cin >> n >> m >> k >> mod; k=n+m-k;//1<=k<=n f[0]=1; for(int i=1; i<=iu ;i++) f[i]=f[i-1]*i%mod; inf[iu]=pw(f[iu],mod-2); for(int i=iu; i>=1 ;i--) inf[i-1]=inf[i]*i%mod; ll v1=tab1(),v2=tab2(); cout << y << ' '; cout << v1*v2%mod << '\n'; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 | #include<bits/stdc++.h> using namespace std; typedef long long ll; #define fi first #define se second int n,m,k,y; ll mod; const int iu=1e6; ll f[iu+1],inf[iu+1]; ll pw(ll x,ll y){ if(y==0) return 1; if(y%2) return x*pw(x,y-1)%mod; ll res=pw(x,y/2); return res*res%mod; } ll C(ll x,ll y){ return f[x]*inf[y]%mod*inf[x-y]%mod; } int st[20]; int en[20]; int filled[1<<20]; ll dp[1<<20]; ll tab1(){ for(int i=0; i<n ;i++){ st[i]=i-k+1; en[i]=st[i]+m; st[i]=max(st[i],0); } for(int i=0; i<n ;i++) filled[1<<i]=en[i]-st[0]; for(int i=1; i<(1<<n) ;i++){ int id=__builtin_popcount(i); if(i!=(i&-i)) filled[i]=filled[i^(i&-i)]+filled[i&-i]+st[0]-st[id-1]; } /*for(int i=0; i<(1<<n) ;i++) cout << filled[i] << ' '; cout << endl;*/ dp[0]=1; for(int i=0; i<(1<<n)-1 ;i++){ int id=__builtin_popcount(i); int sgn=1; for(int j=n-1; j>=0 ;j--){ if((i>>j)&1){ sgn=-sgn; continue; } ll ways; if(st[id]==0){ ways=C(filled[i]+en[j]-1,en[j]-1); } else{ ways=C(filled[i]+en[j]-st[id],en[j]-st[id]); } //cout << "trans " << i << ' ' << (i|(1<<j)) << ' ' << sgn << ' ' << ways << endl; if(sgn==-1) ways=(mod-ways); dp[i|(1<<j)]=(dp[i|(1<<j)]+dp[i]*ways)%mod; } } return dp[(1<<n)-1]; } int g[25][50005],h[25][50005]; ll tab2(){ int tot=0; ll res=1; for(int i=n; i>=1 ;i--){ for(int j=m; j>=1 ;j--){ if(i+j+k-1<=n+m){ g[i][j]=g[i+1][j]+1; h[i][j]=h[i][j+1]+1; res=res*f[g[i][j]+h[i][j]-2]%mod*inf[g[i][j]+h[i][j]-1]%mod; ++tot; } } } res=res*f[tot]%mod; y=tot; //cout << res << endl; return res; } int main(){ ios::sync_with_stdio(false);cin.tie(0); cin >> n >> m >> k >> mod; k=n+m-k;//1<=k<=n f[0]=1; for(int i=1; i<=iu ;i++) f[i]=f[i-1]*i%mod; inf[iu]=pw(f[iu],mod-2); for(int i=iu; i>=1 ;i--) inf[i-1]=inf[i]*i%mod; ll v1=tab1(),v2=tab2(); cout << y << ' '; cout << v1*v2%mod << '\n'; } |