关键词：
前言
CF原题，但是好题。
题解
略，见代码注释
具体就是前缀和上前缀和再前缀和。
然后架空原数组。
代码
#include <cstdio>
#define min(a, b) (a<b?a:b)
#define ll long long
#define MOD 1000000007
using namespace std;
ll ans, g[3005], fc[100005], inv[100005];
ll f[2][3005][3005], preg[100005], p[100005][2];
ll ksm(ll a, ll b)
ll ans = 1;
for ( ; b; b >>= 1, a = a * a % MOD)
if (b & 1) ans = ans * a % MOD;
return ans;
// 递推预处理阶乘和阶乘的逆元
inline void getFac(int k)
fc[0] = 1;
for (int i = 1; i <= k; ++i)
fc[i] = fc[i - 1] * i % MOD;
inv[k] = ksm(fc[k], MOD - 2);
for (int i = k - 1; ~i; --i)
inv[i] = inv[i + 1] * (i + 1) % MOD;
// 组合数计算，递推预处理优化至 O(1)
ll getC(ll x, ll y)
return (fc[x] * inv[y] % MOD) * inv[x - y] % MOD;
int main()
ll n, m, A, B, k;
scanf("%lld %lld %lld %lld %lld", &n, &m, &A, &B, &k);
getFac(k);
ll pAB = A * ksm(B, MOD - 2) % MOD; // 计算风每天摧毁房子的概率
for (int i = 0; i <= min(k, m); ++i)
// g[i] 表示某行破坏 i 列房子的概率
// k 天中选出 i 天的组合数 乘以 这 i 天每天都刚刚好正中 pAB 的概率被摧毁的概率
// 再乘以剩下的 (k - i) 天都不被摧毁的概率
g[i] = getC(k, i) * ksm(pAB, i) % MOD
* ksm((1 - pAB + MOD) % MOD, k - i) % MOD;
preg[0] = g[0]; // 生成 g 概率的前缀和
for (int i = 1; i <= m; ++i)
preg[i] = (preg[i - 1] + g[i]) % MOD;
f[0][0][0] = f[1][0][0] = 1;
for (int i = 1; i <= n; ++i) // 前 i 行
for (int l = 0; l < m; ++l) // 剩余区间为 (l, ...)
f[0][i][l] = -p[m - l - 1][0], f[1][i][l] = -p[m - l - 1][1]; // 由带系数的 sum_dp 前缀和转移而来
// 计算 dp_r 与 dp_l
f[0][i][l] = ( (f[0][i][l] +
(f[0][i - 1][0] - f[1][i - 1][m - l]) * preg[m - l - 1]) % MOD
+ MOD) % MOD;
f[1][i][l] = ( (f[1][i][l] +
(f[0][i - 1][0] - f[0][i - 1][m - l]) * preg[m - l - 1]) % MOD
+ MOD) % MOD;
f[0][i][l] = f[0][i][l] * g[l] % MOD;
f[1][i][l] = f[1][i][l] * g[l] % MOD;
for (int r = m - 1; ~r; --r)
// 维护 sum_f_l 与 sum_f_r 的前缀性
(f[0][i][r] += f[0][i][r + 1]) %= MOD;
(f[1][i][r] += f[1][i][r + 1]) %= MOD;
for (int r = 0; r <= m; ++r)
// 根据对称性计算乘上系数的概率
p[r][0] = g[r] * f[0][i][m - r] % MOD;
p[r][1] = g[r] * f[1][i][m - r] % MOD;
for (int r = 1; r <= m; ++r)
// 计算概率 p 的前缀和
(p[r][0] += p[r - 1][0]) %= MOD;
(p[r][1] += p[r - 1][1]) %= MOD;
// 答案显然已经计算完毕
printf("%lld", f[0][n][0]);
return 0;
思考总结
- 参数对称的式子可以裂开处理
- 当答案与前缀有关可以舍弃原数组
福州3中集训day5
数论，zld神犇认为我们都学过数论的，讲了一波高端（入门？）操作，从扩展欧几里得开始，同余方程诸如此类，早晚得重修。连课件都没，拿着画图讲了一上午sro_zld_orz具体内容都记在本上。还是说说下午考试题吧T1,简单来讲... 查看详情
面试官：redis中集合数据类型的内部实现方式是什么？(代码片段)
虽然已经是阳春三月，但骑着共享单车骑了这么远，还有有点冷的。我搓了搓的被冻的麻木的手，对着前台的小姐姐说：“您好，我是来面试的。”小姐姐问：“您好，您叫什么名字？”我回答：“我叫万猫学社。”小姐姐笑出... 查看详情
保研面试数据结构问题夏令营预推免(代码片段)
数据结构：O(n)的大O是什么意思？什么是时间复杂度?★★★线性存储结构和链式存储结构的优点★★★解释一下顺序存储与链式存储★★★头指针和头结点的区别？★★栈和队列的区别和内存结构★★★有一个循环队... 查看详情
道路重建(2018山东冬令营)(代码片段)
问题C:道路重建时间限制:1Sec 内存限制:128MB提交:67 解决:24[提交][状态][讨论版]题目描述小L的家乡最近遭遇了一场洪水，城市变得面目全非，道路也都被冲毁了。生活还要继续，于是市政府决定重建城市中的道路... 查看详情
数据类型之集合(代码片段)
在python中集合分两种:set:可变集合fronzenset:不可变集合集合的特点:无序不重复，常用于去重元素必须是可hash的，即不可变类型通过hashtable实现，查询速度极快，可以很高效地判断元素是否存在于某个集合集合很消耗内存创建一个... 查看详情
[暑假集训]开训复健练习赛：b-findaway——hdu-2612(代码片段)
#include<iostream>#include<cmath>#include<algorithm>#include<string>#include<cstring>#defineDEBUGif(1)//是否输出调试用信息usingnamespacestd;intW,H;inttime[2][205][205];intstack[20 查看详情
冬令营wintercamp数学专题(代码片段)
【冬令营WinterCamp】数学专题A-A^BModCB-逆元A-A^BModC思路：这个题目首先能想到暴力，但是数据太大，所以不现实，因此用快速幂来解决，具体看上述链接。#include<bits/stdc++.h>usingnamespacestd;typedeflonglongintl... 查看详情
springboot中集成lucence(代码片段)
Lucence和全文检索Lucene概念全文检索这里提到了全文检索的概念，我们先来分析一下什么是全文检索，理解了全文检索之后，再理解Lucene的原理就非常简单了。何为全文检索？举个例子，比如现在要在一个文件中查找某个字符串... 查看详情
jzoj5990.北大2019冬令营模拟2019.1.6bear（状压dp）(代码片段)
...[n+1][0])就是答案。这样的话能有(40)分（建议先看一下40分代码不然看不太懂AC代码的……）//minamoto#include<bits/stdc++.h>#defineRregister#definefp(i,a,b)for(Rinti=a,I=b+1;i<I;++i)#definefd(i,a,b)for(Rinti=a,I=b-1;i>I;--i)#definego(u)for(inti=head[u],v=e 查看详情
java面试常问知识总结(代码片段)
JAVA中的参数传递总结先看两道笔试题：1publicclassTest223publicstaticvoidmain(String[]args)4StringBuffera=newStringBuffer("A");5StringBufferb=newStringBuffer("B");6operate(a,b);7System.out.println(a+","+b);8910stati 查看详情
微信小程序|基于云数据库的许愿墙(代码片段)
CSDN话题挑战赛第2期参赛话题：学习笔记 本实训项目以云开发的云数据库为基础，制作一个简易的许愿墙。01、实训内容本实训项目以云开发的云数据库为基础，制作一个简易的许愿墙，顾名思义“云数据库”就... 查看详情
夏令时计算(代码片段)
1.首先确定要计算时间的时区，jdk8支持，根据时区ID来判断是否处于夏令时。2.根据要判断时区的id和对应的时间，即可判断出是否处于夏令时。publicstaticbooleancurrentTimeIsDaylightTime(longtime)Calendarcalendar=Calendar.getInstance();calendar.setTime(... 查看详情
json地理编码夏令营(代码片段)
jzoj5991.北大2019冬令营模拟2019.1.6juice(代码片段)
题面题解好迷……//minamoto#include<bits/stdc++.h>#defineRregister#definelllonglong#definefp(i,a,b)for(Rinti=a,I=b+1;i<I;++i)#definefd(i,a,b)for(Rinti=a,I=b-1;i>I;--i)#definego(u)for(inti=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)template<classT>inlineboolcmax(T&a,constT&... 查看详情
题解刻录光盘(代码片段)
题目描述 在FJOI2010夏令营快要结束的时候，很多营员提出来要把整个夏令营期间的资料刻录成一张光盘给大家，以便大家回去后继续学习。组委会觉得这个主意不错！可是组委会一时没有足够的空光盘，没法保证每个人都能... 查看详情
rabbitmq常见面试题(代码片段)
一.使用RabbitMQ的好处1.解耦，系统A在代码中直接调用系统B和系统C的代码，如果将来D系统接入，系统A还需要修改代码，过于麻烦！2.异步，将消息写入消息队列，非必要的业务逻辑以异步的方式运行，加快响应速度3.削峰，并发... 查看详情
2017计算机学科夏令营上机考试-b编码字符串
B:编码字符串总时间限制: 1000ms 内存限制: 65536kB描述在数据压缩中，一个常用的方法是行程长度编码压缩。对于一个待压缩的字符串，我们可以依次记录每个字符及重复的次数。例如，待压缩的字符串为"aaabbbbcbb"，压... 查看详情
常量引用(代码片段)
思考costint&a=bPKconstint&a=10;在C++中可以声明const引用constType&name=var；const引用让变量拥有只读属性 //常引用的知识架构intmain(void)//普通引用inta=10;int&b=a;printf("b:%d",b);//常引用intx=20;constint&y 查看详情