題目鏈接

https://atcoder.jp/contests/agc009/tasks/agc009_e

題解

又被勸退了。。。
第一步轉化非常顯然: 就等價于一開始有一個數\(1\), 有\(\frac{n+m-1}{k-1}\)次機會每次選擇一個數把它變成\(k\)個原來的\(\frac{1}{k}\), 最后從\(n+m\)個數中選出\(m\)個，問能選出多少不同的數。
然后考慮化成\(k\)進制小數，假設最后形成的數是\(d_1,d_2,...,d_{n+m}\), 則\(\sum^{n+m}_{i=1} d_i=1\).
一個\(d\)進制小數可以被表示成\(m\)個\(k\)的負整數次冪之和當且僅當其每一位數值之和不超過\(m\)且和\(m\)模\((k-1)\)同余。(顯然)
但同時還要保證\(1\)可以被表示成\((n+m)\)個\(k\)的負整數次冪之和，且包含這\(m\)個數。那么就可以轉化成\(1\)減這個小數可以被表示成\(n\)個\(k\)的負整數次冪之和。(行吧我就這一步沒想出來……自閉了啊……)
所以最后也就是要計算有多少個序列\(a_1,a_2,...,a_l\ (1\le l\le \frac{n+m-1}{k-1})\), 滿足\(0\le a_i\le k-1, a_l>0, \sum^l_{i=1}a_i\le m,\sum^l_{i=1}a_i\equiv m(\mod k-1), \sum^l_{i=1}k-1-a_i\le n-1, \sum^l_{i=1}k-1-a_i\equiv n-1(\mod k-1)\), 直接dp即可。時間復雜度\(O((n+m)k)\).

代碼

#include<cstdio> #include<cstdlib> #include<iostream> #include<cassert> #define llong long long using namespace std;const int N = 4e3; const int P = 1e9+7; llong dp[N+3][N+3],sdp[N+3][N+3]; int n1,n2,m,len; llong ans;int main() {scanf("%d%d%d",&n1,&n2,&m); len = (n1+n2-1)/(m-1);dp[0][0] = 1ll; for(int j=0; j<=n2; j++) sdp[0][j] = 1;for(int i=1; i<=len; i++){for(int j=0; j<=n2; j++){if(j>=m) {dp[i][j] = (sdp[i-1][j]-sdp[i-1][j-m]+P)%P;}else {dp[i][j] = sdp[i-1][j];}if((n2-j)%(m-1)==0 && i*(m-1)-j<=n1-1 && (n1-1-i*(m-1)+j)%(m-1)==0) {ans = (ans+dp[i][j]-dp[i-1][j]+P)%P;}}sdp[i][0] = dp[i][0]; for(int j=1; j<=n2; j++) sdp[i][j] = (sdp[i][j-1]+dp[i][j])%P;}printf("%lld\n",ans);return 0; }

總結

以上是生活随笔為你收集整理的AtCoder AGC009E Eternal Average (DP)的全部內容，希望文章能夠幫你解決所遇到的問題。

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