題目鏈接: https://atcoder.jp/contests/agc002/tasks/agc002_f

題解: 講一下官方題解的做法: 就是求那個圖(官方題解里的)的拓撲序個數，設\(dp[i][j]\)表示有\(i\)個0色和\(j\)個非0色的圖的拓撲序個數(\(i<j\))，則轉移一是加入一個0色球，二是加入一個非0色球(拓撲序以非0色球開始)，這種情況下我們固定了開頭所以還剩\(((K-1)j+i-1)\)個位置放入\((K-2)\)個球，\(dp[i][j]=dp[i-1][j]+dp[i][j-1]\times {\comb{(K-1)j+i-1}{K-2}}\).

另外有一種反著的做法(我代碼寫的就是這個)，但是并不懂(曾經懂過但是現在腦子又亂了)

啟示: 這種計數很多都是考慮第一個，千萬不要慣性思維無腦考慮最后一個！！！

代碼

#include<cstdio> #include<cstdlib> #include<cstring> #define llong long long using namespace std;const int N = 2000; const int P = 1e9+7; llong dp[N+3][N+3]; llong fact[5000003],finv[5000003]; int n,m;llong quickpow(llong x,llong y) {llong cur = x,ret = 1ll;for(int i=0; y; i++){if(y&(1ll<<i)) {y-=(1ll<<i); ret = ret*cur%P;}cur = cur*cur%P;}return ret; }llong comb(llong x,llong y) {return x<0 || y<0 || x<y ? 0ll : fact[x]*finv[y]%P*finv[x-y]%P;}int main() {fact[0] = 1ll; for(int i=1; i<=5000000; i++) fact[i] = fact[i-1]*i%P;finv[5000000] = quickpow(fact[5000000],P-2); for(int i=5000000-1; i>=0; i--) finv[i] = finv[i+1]*(i+1)%P;scanf("%d%d",&n,&m);if(m==1) {printf("1"); return 0;}dp[0][0] = 1ll;for(int i=1; i<=n; i++){dp[i][0] = 1ll;for(int j=1; j<=i; j++){dp[i][j] = dp[i-1][j];dp[i][j] += comb((n-i)+(n-(j-1))*(m-1)-1,m-2)*dp[i][j-1]%P;dp[i][j] %= P;}}llong ans = dp[n][n]*fact[n]%P;printf("%lld\n",ans);return 0; }

總結

以上是生活随笔為你收集整理的AtCoder AGC002F Leftmost Ball (DP、组合计数)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。