加盟平台响应网站建设,营销型网站建设网络推广,网站建设 深路互动,国际新闻最新战争消息2023河南省赛组队训练赛#xff08;二#xff09; - Virtual Judge (vjudge.net)
背景#xff1a;阿塔尼斯#xff0c;达拉姆的大主教#xff0c;在艾尔又一次沦陷之后指挥着星灵的最后一艘方舟舰#xff1a;亚顿之矛。作为艾尔星灵数千年来的智慧结晶#xff0c;亚顿之…2023河南省赛组队训练赛二 - Virtual Judge (vjudge.net)
背景阿塔尼斯达拉姆的大主教在艾尔又一次沦陷之后指挥着星灵的最后一艘方舟舰亚顿之矛。作为艾尔星灵数千年来的智慧结晶亚顿之矛除了搭载了以太阳能碎片为核心的兵工厂之外还配备了诸如汇聚射线、太阳能射线枪等威力强大的支援武器。而在这些武器中最负盛名、也最让敌人胆寒的就是太阳轰炸。
太阳轰炸是一件威力巨大的对星球武器。在太阳轰炸开火时亚顿之矛将聚集太阳能核心中的太阳能量向目标坐标发射成百上千枚火焰飞弹。虽然这些火焰飞弹精准度较差但太阳轰炸的高攻击频率仍然可以让地面上的敌人无法躲避化为灰烬。
在这一次的行动中阿塔尼斯的目标是一枚臭名昭著的虚空碎片。在俯视视角下虚空碎片的投影是一个半径为 R1 的圆太阳轰炸的攻击散布范围是一个半径为 R2 的圆。这两个圆的圆心均为原点 (0, 0)。太阳轰炸将射出 n 枚火焰飞弹每一枚火焰飞弹等概率地落在攻击散布范围内每一个点上所有火焰飞弹的落点相互独立。火焰飞弹的伤害范围是以落点为圆心半径为 r 的圆。若火焰飞弹的伤害范围和虚空碎片的投影相交则该枚火焰飞弹命中虚空碎片造成 a 点伤害。若总伤害大于等于 h则虚空碎片会被摧毁。
摧毁这枚虚空碎片对阿塔尼斯的战略部署非常重要因此阿塔尼斯想要知道一次太阳轰炸能够摧毁这枚虚空碎片的概率。你需要输出答案对质数 109 7 取模的值。
Input
仅一行包含六个整数 n, R1, R2, r, a, h (1 ≤ n ≤ 5 × 106, 1 ≤ R1, R2, r ≤ 108, 1 ≤ a, h ≤ 108)含义见题目描述。
Output
一个整数表示答案。
Sample 1
InputcopyOutputcopy 3 2 4 1 1 1636962896Note
答案对质数 109 7 取模的定义设 M 109 7可以证明答案可表示为一个既约分数 其中 p, q 均为整数且 q 模 M 不余 0。输出满足 0 ≤ x M 且 x·q ≡ p ± od{M} 的整数 x。 上图对应了样例中 R1 2, R2 4, r 1 的情况。其中红色的圆是虚空碎片的投影蓝色的圆是太阳轰炸的攻击范围。A, B, C 是三个可能的落点其中 A, C 命中虚空碎片而 B 没有命中虚空碎片。
题解:
1.概率为0,炮弹伤害全部命中也无法摧毁碎片
2.概率为1,炮弹的落范围R2 R1 r
3.外面又一个环炮弹骗的范围
命中概率即为(R1 r)*(R1 r)/(R2 * R2) p1
未命中概率即为((R1*R2) - (R1 r)*(R1 r))/(R2 * R2) p2
根据组合数学命中总概率为
Cnk*(p1)^k*p2^(n-k) Cn(k1)*(p1)^(k1)*p2*(n-k-1) .......
Cnn*p1^n*p2^(n-n)
本题主要难点就是线性时间如何求出每一个Cnk
我们可以1*2*3..*n得到fa[n]
然后qpow(fa[n],mod-2)得到fa[n]的逆元g[n]
fa[n-1]的逆元就是g[n]*n依次类推 #includeiostream
#includealgorithm
#includestring
#includecstring
#includevector
#includemap
#includequeue
using namespace std;
#define int long long
const int N 6e6 10;
int mod 1e9 7;
#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
int fa[N];
int g[N];
int t[N];
int y[N];
int qpow(int x,int p)
{int a 1;while(p){if(p1)a a*x%mod;x x*x%mod;p / 2;}return a;
}
int C(int n,int m)
{return fa[n]*g[m]%mod*g[n-m]%mod;
}
void solve()
{int n,r1,r2,r,a,h;cin n r1 r2 r a h;int k ;if(h%a 0){k h/a;}else{k h/a 1;}if(k n){cout0;return ;}if(r2 (r1 r)){cout 1\n;return ;}fa[0] g[0] 1;int z (r1 r)*(r1 r)%mod;int x (r2*r2%mod - (r1 r)*(r1 r)%mod mod)%mod;int c r2*r2%mod; for(int i 1;i n;i){fa[i] fa[i-1]*i%mod;}g[n] qpow(fa[n],mod - 2);for(int i n -1;i 0;i--){g[i] g[i1]*(i1)%mod;}int zx 1;for(int i 1;i n;i){zx zx*c %mod;}t[0] 1,y[0] 1;for(int i 1;i n;i){t[i] t[i - 1]*z%mod;y[i] y[i-1]*x%mod; }int s 0;for(int i k;i n;i){s (s (C(n,i) * t[i]%mod*y[n - i]%mod) %mod)%mod;}cout s*qpow(zx,mod-2)%mod;}
signed main()
{
// ios;int t 1;
// cin t;while(t--){solve();}
}
//3 F
//5 B
//6 F
//9 F
//10 B
//12 F
//15 FB
//18 FB
