STD有误？？？

...................是我太弱了还是怎么样啊.........公式推对的自己写了怎么交都是百分之55，然后不得已看了std，刚开始对比我的代码没发现错误..然后我发现我把std代码加了有注释的两行就也是百分之55了....那么是不是std就假了啊......所以数据也假了啊.....整个人都是懵逼的啊...

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int P=1e9+7;
const int N=600000+10;
ll T,n,m,k,i,ans,f[N],inv[N];
ll ksm(ll a,ll n){
    ll res=1;
    a%=P;
    while (n){
        if (n&1) res=res*a%P;
        a=a*a%P;
        n>>=1;
    }
    return res;
}
ll C(ll n,ll m){
    if (n<m) return 0;
    ll res=1;
    for (int i=1;i<=m;i++){
        ll a=(n-m+i)%P;
        ll b=i%P;
        res=res*(a*ksm(b,P-2)%P)%P;
    }
    return res;
}
ll lucas(ll n,ll m){
    if (m==0) return 1;
    return C(n%P,m%P)*lucas(n/P,m/P)%P;
}
int main(){
    cin>>n>>m>>k;
    ll N0=lucas(m+n-1,n-1);
    ll nn=(n+m+1)/(k+1);
    for (i=1;i<=nn;++i){
       ans+=pow(-1,i+1)*lucas(n,i)*lucas((n+m-1)-(i*(k+1)),(n-1));
       ans%=P;
    }
    (N0-=ans)%=P;//修改的地方
    if (N0<0) N0+=P;//修改的地方
    printf("%lld\n",N0);
    return 0;
}

全部评论

推荐最新楼层

某不知名的蒟蒻

qwq神殿 C++

好像确实有这个问题。。。

点赞回复分享

发布于 2018-10-22 15:22

某不知名的蒟蒻

qwq神殿 C++

因为std先求出的是题目里给定问题的反问题，所以说容斥原理是有可能求得负的ans的。。

点赞回复分享

发布于 2018-10-22 15:23

PerfectPan

楼主

杭州电子科技大学前端工程师

因为我删掉以后才能过啊QAQ

点赞回复分享

发布于 2018-10-22 15:24

某不知名的蒟蒻

qwq神殿 C++

窝std好像给错了。。。

点赞回复分享

发布于 2018-10-22 15:30

某不知名的蒟蒻

qwq神殿 C++

#include<algorithm> #include<cstdio> #include<queue> #include<cmath> #include<cstring> #include<iostream> #include<ctime> #include<cstdlib> #define ll long long using namespace std; const int mod=1e9+7; const int maxn=10000005; ll n,m,k; ll ans; ll q_pow(ll n,ll mi){ ll res=1,temp=n%mod; while(mi){ if(mi&1) res=res*temp%mod; temp=temp*temp%mod; mi>>=1; } return res; } ll cal(ll n,ll m){ // Cm(n,m)=(n!/(n-m)!) * (m!)^(mod-2)) mod mod if(m>n) return 0; // important ll res=1; for(int i=1;i<=m;i++){ ll t1=(n-m+i)%mod,t2=i%mod; res=res*(t1*q_pow(t2,mod-2)%mod)%mod; } return res; } /*Lucas(n,m,mod)=Cm(n%mod,m%mod)* Lucas(n/mod,m/mod,mod) Lucas(x,0,mod)=1;*/ ll lucas(ll t1,ll t2){ if(t2==0) return 1; return cal(t1%mod,t2%mod)*lucas(t1/mod,t2/mod)%mod; } int main(){ // int t; // scanf("%d",&t); // while(t--){ // scanf("%lld",&n); // cout<<lucas(n-1,n/2)<<endl; // } // scanf("%lld%lld",&n,&m); cin>>n>>m>>k; ll N0=lucas(n+m-1,n-1); ll num=(n+m+1)/(k+1); for(int i=1;i<=num;i++){ ans+=pow(-1,i+1)*lucas(n,i)*lucas((n+m-1)-(i*(k+1)),(n-1)); ans%=mod; } printf("%lld\n",N0-ans);//取模正确吗？ // cout<<lucas(25,5)-(lucas(6,1)*lucas(16,5))+(lucas(6,2)*lucas(7,5)); // printf("Time used= %.2f\n",(double)clock()/CLOCKS_PER_SEC); // system("pause"); return 0; }

点赞回复分享

发布于 2018-10-22 15:30