Loading... <div class='handsome_aplayer' data-preload="auto" data-autoplay="false" data-listMaxHeight="340px" data-order="list" data-media="netease" data-id="226989" data-type="song" data-size="large" data-auto="false"> <div class="handsome_aplayer_music" data-id="226989" data-server="netease" data-type="song" data-auth="auth"></div> </div> <div class='handsome_aplayer' data-preload="auto" data-autoplay="false" data-listMaxHeight="340px" data-order="list" data-media="netease" data-id="526093052" data-type="song" data-size="large" data-auto="false"> <div class="handsome_aplayer_music" data-id="526093052" data-server="netease" data-type="song" data-auth="auth"></div> </div> ## 讨论 求将一个$n\times m$的长方形,划分成$n×m$个$1×1$的正方形,任意选出一个由这些小正方形组成的矩形(包括正方形),求面积的期望值对$998244353$取模的值。$n,m\in \mathbb{N^*}\bigcap [1 ,10^{10^5}]$ ### 题解 注意到面积的期望值是面积的和与正方形总个数的比值,考虑对其分别计算。 设矩形个数为$c$,面积和为$s$。 $$ \begin{align} c&=\sum_{i=1}^nn+1-i\sum_{i=1}^m(m+1-i)\\&=\cfrac{n(n+1)}{2}\times\cfrac{m(m+1)}{2}\\&=\cfrac{mn(m+1)(n+1)}{4} \end{align} $$ $$ \begin{align} s&=\sum_{i=1}^ni\times(n+1-i)\sum_{i=1}^ii\times(m+1-i)\\&=\cfrac{n(n+1)(n+2)}{6}\times\cfrac{m(m+1)(m+2)}{6}\\&=\cfrac{mn(m+1)(n+1)(m+2)(n+2)}{36} \end{align} $$ 两式相除。 $$ \cfrac sc=\cfrac{(m+2)(n+2)}{9} $$ 由费马小定理得逆元为$443664157$。 ### 代码 ```python a, b = input().split() x = int(a) y = int(b) print((x+2) % 998244353*(y+2) % 998244353 * 443664157 % 998244353) ``` ## 战斗 ### 题目 ### 题解 $f_{i+1,j+h_i}$表示到第$i$个回合,给予伤害为$j$时,剩下的最大魔法值。 $f_{i+1,j+h_i}=\max \limits_{i=1}^4\left\{f_{i+1,j+h_i}, f_{i,j}-p_i\right\}$ 另外再将连招计为一种神奇的四回合招式即可。 ### 代码 ```cpp #include <bits/stdc++.h> using namespace std; int n, m; int h[7], p[7], dp[7][11000]; int main() { cin >> n >> m >> h[1] >> p[1]; for ( int i = 2; i <= 5; i++ ) { cin >> h[i] >> p[i]; h[6] += h[i]; p[6] += p[i]; } h[6] += 3 * h[5]; for ( int i = 0; i <= 4; i++ ) { for ( int j = 0; j <= m; j++ ) { dp[i][j] = -1e9; } } dp[0][0] = 0; for ( int i = 0; i <= n - 1; i++ ) { for ( int j = 0; j <= m; j++ ) { for ( int k = 1; k <= 5; k++ ) { if ( dp[0][j] - p[k] >= 0 ) { if ( j + h[k] > m ) { if ( dp[0][j] != -1e9 ) { cout << "yes"; return 0; } } else { dp[1][j + h[k]] = max( dp[1][j + h[k]], dp[0][j] - p[k] ); } } } if ( i + 4 <= n && dp[0][j] - p[6] >= 0 ) { if ( j + h[6] > m ) { if ( dp[0][j] != -1e9 ) { cout << "yes"; return 0; } } dp[4][j + h[6]] = max( dp[4][j + h[6]], dp[0][j] - p[6] ); } } for ( int k = 0; k <= 3; k++ ) { for ( int j = 0; j <= m; j++ ) { dp[k][j] = dp[k + 1][j]; } } } cout << "no"; return 0; } ``` ## 魔法 ### 题目 给出$n$个定义域和值域为$\mathbb{N^*}\bigcap [1 ,k]$的函数,选择一个函数$f(x)$,可以使你的数变成$f(x)$。试求开始数为$x\in\mathbb{N^*}\bigcap [1 ,k]$时最终值的最大值。 ### 题解 大力广搜即可。 ### 代码 ```cpp #include <bits/stdc++.h> using namespace std; int fuck[505][20005], linemax[505]; bool vis[505][20005]; struct status { int now, val; status() {} status( int a, int b ) { now = a; val = b; } bool operator<( const status& that ) const { return val == that.val ? now > that.now : val < that.val; } }; inline int read() { int s = 0, w = 1; char ch = getchar(); while ( ch < '0' || ch > '9' ) { if ( ch == '-' ) w = -1; ch = getchar(); } while ( ch >= '0' && ch <= '9' ) s = s * 10 + ch - '0', ch = getchar(); return s * w; } int main() { ios::sync_with_stdio( false ); cin.tie( 0 ); int n, x, k, ans = 0; n = read(); x = read(); k = read(); for ( int i = 1; i <= n; i++ ) { for ( int j = 1; j <= k; j++ ) { fuck[i][j] = read(); } } queue< status > q; q.push( status( 0, x ) ); while ( !q.empty() ) { status deal = q.front(); q.pop(); ans = max( ans, deal.val ); if ( ans == k ) { break; } for ( int i = deal.now + 1; i <= n; i++ ) { if ( !vis[i][deal.val] ) { q.push( status( i, fuck[i][deal.val] ) ); vis[i][deal.val] = true; } } } cout << ans << endl; return 0; } ``` <hr class="content-copyright" style="margin-top:50px" /><blockquote class="content-copyright" style="font-style:normal"><p class="content-copyright">版权属于:淡淡的路瑶</p><p class="content-copyright">本文链接:<a class="content-copyright" href="https://www.starroad.top/archives/793.html">https://www.starroad.top/archives/793.html</a></p><p class="content-copyright">如果文章出现任何问题,请下方评论,紧急情况请发邮件。谢谢支持!</p></blockquote> Last modification:October 23rd, 2020 at 07:14 pm © 允许规范转载 Support 如果您觉得我的文章有用,给颗糖糖吧~ ×Close Appreciate the author Sweeping payments Pay by AliPay Pay by WeChat