首页 > 代码库 > set与split
set与split
所以说不要以为前一天考了什么后一天就不会考这类的东西了
出题人总是能竭尽所能
打破你的下限qaq
naive
split 详解blog来自ljz大佬:http://blog.csdn.net/ljz_2016/article/details/54986358
然后set的话
我本来是以为昨天已经考过一道大家什么都没学的数学题
这事儿就这么完了
可惜没有qwq
解释一部分来自题解 一部分来自自己
写写划划试几个小的数据应该有助于理解
对 以后写题的时候也一定要记得 不管是什么样的题目 空想往往让人又迟钝又烦闷
不如来点实在的 对吧
1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cstring> 5 #include<algorithm> 6 #include<string> 7 #define ll long long 8 #define maxn 100100 9 using namespace std; 10 const int mod=(1000000000+7); 11 ll jc[maxn]; 12 ll qpow(ll x,ll y){ 13 ll ans=1; 14 for (;y;y>>=1,x*=x){x%=mod; if (y&1) ans*=x; ans%=mod;} 15 return ans; 16 } 17 ll inv(ll a){ 18 return qpow(a,mod-2); 19 } 20 int main(){ 21 //freopen ("set.in","r",stdin); 22 //freopen ("set1.out","w",stdout); 23 int n; 24 scanf ("%d",&n); 25 jc[0]=1; 26 /*设最后都收束为p,显然f(p)=p。 27 设有L个f(x)=p,除了p还要任选L-1个, 28 剩下n-L个都要在这L-1个位置中任取。枚举L, 29 复杂度O(n) f(n-L) -> L-1种值*/ 30 for (int i=1;i<=n;++i) jc[i]=(jc[i-1]*i)%mod; 31 ll ans=0; 32 for (int l=1;l<=n;++l){ 33 //n-1里选l-1个数u 34 ll as=jc[n-1]*inv(jc[l-1])%mod*inv(jc[n-l])%mod; 35 //把n-l个数放进l-1个位置里 36 ll am=qpow(l-1,n-l); 37 ans=(as*am%mod)+ans; 38 ans%=mod; 39 } 40 ans=ans*n%mod; 41 cout<<ans; 42 return 0; 43 }
然后这次求逆元用的是费马小定理 (其实上次也可以
快速幂打wa+mod 没打括号改了40分钟也是没谁了(仰胁息
考场想出了组合然而那时候也是不会逆元的
也不知道可以quickpow一下 不过现在感觉解释还是讲得满清楚的
一定记得有事没事就膜膜膜
(gouliguojia)
为出题人+1s
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<string>
#define N 100100
#define ll longlong
#define mod 1000000007
usingnamespace std;
ll ni[N],jie[N];
void ex(ll a,ll b,ll & x,ll & y,ll & r){
if(b==0) r=a,x=1,y=0;
else{
ex(b,a%b,y,x,r);
y-=x*(a/b);
}
}
ll nii(ll a,ll b){
ll r,x,y;
ex(a,b,x,y,r);
return r==1?(x+b)%b:-1;
}
int main(){
// freopen ("split.in","r",stdin);
// freopen ("split.out","w",stdout);
jie[0]=1;
for(int i=1;i<N;++i) jie[i]=(jie[i-1]*i)%mod;
ni[0]=ni[1]=1;
for(int i=2;i<N;++i) ni[i]=nii(i,mod)%mod;
for(int i=2;i<N;++i) ni[i]=(ni[i-1]*ni[i])%mod;
// for (int i=2;i<N;++i) cout<<ni[i]<<endl;
ll n,t,w;
ll anss=0;
scanf ("%lld%lld%lld",&n,&t,&w);
for(int i=1;i<=n;++i){
ll x,y;
scanf ("%lld%lld",&x,&y);
ll we=x-t;
if(w<we||w>we+2*t)continue;
if((w-we)%2)continue;
ll ans=((jie[t]%mod)*(ni[t-(w-we)/2]%mod))%mod;
ans*=(ni[(w-we)/2]%mod);
ans%=mod;
anss+=((ans*y)%mod);
}
printf ("%lld",anss%mod);
return0;
}
set与split
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。