【组合数学 && dp[i][j] = a*dp[i, j

在Photoshop中，Ctrl+J可以复制选区，Ctrl+Shift+J为剪切。 #生活常识# #电脑#

Step1 Problem:

已知 a , b , c a, b, c a,b,c 和 d p [ k ] [ 1 ] , d p [ 1 ] [ k ] dp[k][1], dp[1][k] dp[k][1],dp[1][k] 其中 k = 1 , 2 , 3 , . . . , n . k = 1, 2, 3, ..., n. k=1,2,3,...,n.
d p [ i ] [ j ] = a ∗ d p [ i ] [ j − 1 ] + b ∗ d p [ i − 1 ] [ j ] + c ; dp[i][j] = a*dp[i][j-1] + b*dp[i-1][j] + c; dp[i][j]=a∗dp[i][j−1]+b∗dp[i−1][j]+c;
求 d p [ n ] [ n ] dp[n][n] dp[n][n].
数据范围：
2 &lt; = n &lt; = 200000 , 0 &lt; = a , b , c &lt; = 1 e 6. 2 &lt;= n &lt;= 200000, 0 &lt;= a, b, c &lt;= 1e6. 2<=n<=200000,0<=a,b,c<=1e6.

Step2 Ideas:
(待填)

Step3 Code:

#include<bits/stdc++.h> using namespace std; #define ll long long const int N = 2e5+5; const int MOD = 1e6+3; int row[N], col[N]; ll ap[N], bp[N], A[2*N], inv[2*N]; ll Pow(ll x, int n) { ll ans = 1; while(n) { if(n&1) ans *= x, ans %= MOD; x = x*x, x %= MOD; n >>= 1; } return ans; } void init() { A[1] = inv[1] = 1; ll ans = 1; int n = 2*N; for(int i = 2; i < n; i++) { ans *= i, ans %= MOD; A[i] = ans; inv[i] = Pow(ans, MOD-2); } } ll C(int n, int m) { if(m == n || m == 0) return 1; return A[n]*inv[n-m]%MOD*inv[m]%MOD; } int main() { init(); int n, a, b, c; scanf("%d %d %d %d", &n, &a, &b, &c); ap[0] = bp[0] = 1; for(int i = 1; i <= n; i++) { ap[i] = ap[i-1]*a, ap[i] %= MOD; bp[i] = bp[i-1]*b, bp[i] %= MOD; } for(int i = 1; i <= n; i++) scanf("%d", row+i); for(int i = 1; i <= n; i++) scanf("%d", col+i); if(a == 0 && b == 0) { printf("%d\n", c); } else if(a == 0) { ll ans = col[n]; for(int i = 2; i <= n; i++) { ans = ans * b + c; ans %= MOD; } printf("%lld\n", ans); } else if(b == 0) { ll ans = row[n]; for(int i = 2; i <= n; i++) { ans = ans * a + c; ans %= MOD; } printf("%lld\n", ans); } else { // double k = 1.0*c/(a+b-1); // double ans = 0; ll ans = 0; ll tmp = Pow(a+b-1, MOD-2); for(int i = 2; i <= n; i++) { ans += (row[i]+c*tmp)%MOD*C(n-i+n-2, n-i)%MOD * ap[n-1]%MOD * bp[n-i]%MOD, ans %= MOD; } for(int i = 2; i <= n; i++) { ans += (col[i]+c*tmp)%MOD*C(n-i+n-2, n-i)%MOD * ap[n-i]%MOD * bp[n-1]%MOD, ans %= MOD; } printf("%lld\n", ((ans - c*tmp)%MOD + MOD)%MOD); } return 0; }

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182

网址：【组合数学 && dp[i][j] = a*dp[i, j https://www.yuejiaxmz.com/news/view/540157

相关内容

购物优惠策略DP算法
0、1背包问题（DP）
若有语句int a[4][3],*p= &a[0][0],i,j ; ,
若有以下程序段:inta[]={4,0,2,3,1},i,j,t;for(i=1
动态规划 多重01背包及空间开销优化
NOJ
a[i]
整数因子分解问题 SDUT
旅行商问题（动态规划方法，超级详细的）
下面程序段的时间复杂度是( )。 x=0; for(i=1; i for (j=

随便看看