淄博做网站哪家好,做网站 智域大连,怎么更改网站备案信息吗,建设银行信用卡网站【agc002f】Leftmost Ball#xff08;动态规划#xff09; 题面 atcoder洛谷 题解 我们从前往后依次把每个颜色按顺序来放#xff0c;那么如果当前放的是某种颜色的第一个球#xff0c;那么放的就会变成\(0\)号颜色#xff0c;所以无论何时#xff0c;\(0\)号颜色的数量不…【agc002f】Leftmost Ball动态规划 题面 atcoder洛谷 题解 我们从前往后依次把每个颜色按顺序来放那么如果当前放的是某种颜色的第一个球那么放的就会变成\(0\)号颜色所以无论何时\(0\)号颜色的数量不能少于其他颜色的数量。 可以设状态\(f[i][j]\)表示前面一共放了\(i\)个\(0\)号颜色的球而一共出现了\(j\)种其他颜色的球根据上面的东西可以知道\(i\ge j\)。每次转移我们分成两种考虑。第一种就直接在后面接一个\(0\)号颜色的球这个不需要考虑任何决策直接转移即可也就是\(f[i][j]f[i-1][j]\)。另外一种转移是选择一共新的颜色抛去前面已经放好的\(0\)号颜色的前抛去当前位置放下一个当前颜色的球那么还需要在后面选择\(k-2\)个位置来放这些球而后面剩下的空位个数显然是可以算的。首先还剩下\(n-i\)个\(0\)号颜色的球没有放所以提供\(n-i\)个空位前面一共只出现了\(j-1\)种颜色所以还有\((n-j1)*(k-1)\)个空位但是当前的位置被钦定放这种新的颜色所以还要减少一个位置。 也就是转移长成这个样子 \[f[i][j]f[i-1][j]C_{(n-i)(n-j1)*(k-1)-1}^{k-2}*f[i][j-1]*(n-j1)\] 时间复杂度\(O(nk)\) #includeiostream
#includecstdio
#includecstdlib
#includecstring
#includecmath
#includealgorithm
#includevector
using namespace std;
#define ll long long
#define MAX 2010
#define MOD 1000000007
void add(int x,int y){xy;if(xMOD)x-MOD;}
inline int read()
{int x0;bool tfalse;char chgetchar();while((ch0||ch9)ch!-)chgetchar();if(ch-)ttrue,chgetchar();while(ch9ch0)xx*10ch-48,chgetchar();return t?-x:x;
}
int n,k,mx,f[MAX][MAX];
int jc[MAX*MAX],jv[MAX*MAX],inv[MAX*MAX];
int C(int n,int m){return 1ll*jc[n]*jv[m]%MOD*jv[n-m]%MOD;}
int main()
{nread();kread();mxn*k;if(k1){puts(1);return 0;}jc[0]jv[0]inv[0]inv[1]1;for(int i1;imx;i)jc[i]1ll*jc[i-1]*i%MOD;for(int i2;imx;i)inv[i]1ll*inv[MOD%i]*(MOD-MOD/i)%MOD;for(int i1;imx;i)jv[i]1ll*jv[i-1]*inv[i]%MOD;f[0][0]1;for(int i1;in;i)for(int j0;ji;j){add(f[i][j],f[i-1][j]);if(j)add(f[i][j],1ll*f[i][j-1]*(n-j1)%MOD*C((n-i)(n-j1)*(k-1)-1,k-2)%MOD);}printf(%d\n,f[n][n]);return 0;
} 转载于:https://www.cnblogs.com/cjyyb/p/9705631.html
