greate left size oss class cal different sin this
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1868 Accepted Submission(s): 522
代码:
- #include<bits/stdc++.h>
- //#include<regex>
- #define db double
- #include<vector>
- #define ll long long
- #define vec vector<ll>
- #define Mt vector<vec>
- #define ci(x) scanf("%d",&x)
- #define cd(x) scanf("%lf",&x)
- #define cl(x) scanf("%lld",&x)
- #define pi(x) printf("%d\n",x)
- #define pd(x) printf("%f\n",x)
- #define pl(x) printf("%lld\n",x)
- #define MP make_pair
- #define PB push_back
- #define inf 0x3f3f3f3f3f3f3f3f
- #define fr(i,a,b) for(int i=a;i<=b;i++)
- const int N=1e5+5;
- const int mod=1e9+7;
- const int MOD=mod-1;
- const db eps=1e-18;
- const db PI=acos(-1.0);
- using namespace std;
- ll x;
- ll F[N],inv[N],Finv[N];
- bool cal(ll n){
- if((n*n+n-2)/2<=x) return 1;
- return 0;
- }
- void init(){
- inv[1] = 1;
- for(int i = 2; i < 45000; i ++){
- inv[i] = (mod - mod / i) * 1ll * inv[mod % i] % mod;//单个逆元
- }
- F[1] = Finv[1] = 1;
- for(int i = 2; i < 45000; i ++){
- F[i] = F[i-1] * 1ll * i % mod;//阶乘
- Finv[i] = Finv[i-1] * 1ll* inv[i] % mod;//逆元阶乘
- }
- }
- int main(){
- //freopen("data.in","r",stdin);
- //freopen("data.out","w",stdout);
- int t;
- ci(t);
- init();
- while(t--)
- {
- cl(x);
- if(x<5) {pl(x);continue;}
- ll l=2,r=45000,sum;
- while(l<r){
- ll mid=l+(r-l+1)/2;
- if(cal(mid)) l=mid;
- else r=mid-1;
- }
- ll ans=x-(l*l+l-2)/2;
- if(ans==l) sum=F[l+2]*inv[2]%mod*inv[l+1]%mod;
- else sum=F[l+1]*Finv[l-ans+1]%mod*F[l-ans]%mod;
- pl(sum);
- }
- return 0;
- }
HDU 5976 数学
来源: http://www.bubuko.com/infodetail-2337051.html