首页 > 代码库 > 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