I - 太阳轰炸(组合数学Cnk n固定)

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

3 2 4 1 1 1

636962896

Note

答案对质数 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(k+1)*(p1)^(k+1)*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依次类推

#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<vector>
#include<map>
#include<queue>
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(p&1)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){cout<<"0";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[i+1]*(i+1)%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