【题目链接】：click here~~
Uvalive 7040 组合+逆元+容斥原理
【题意】：
n个格子排成一行，有m种颜色，问用恰好k种颜色进行染色，使得相邻格子颜色不同的方案数。k≤106n,m≤109【思路】：组合+逆元+容斥首先，我们可以从m个颜色中取出k个，，即Ckm。接着容易想到 $k(k-1)^{n-1},这个是使用不超过k种颜色的所有方案。但我们要求的是恰好使用k种颜色。假设选出的k种颜色标号为1，2，3，…,k，那么记A_i$ 为不使用颜色i的方案数，求的就是 |S||A1A2An| 。也就是反过来考虑，我们不考虑用了哪些颜色，我们考虑哪些颜色没用！减去所有有没使用颜色的方案的并集，剩下的方案就是使用了所有k种颜色的方案。上式中的 |S| 即 $k(k-1)^{n-1}，后者就可以用容斥原理来求了。注意到我们只是给颜色标了个号，所以后面每一项的应为C^i_k(k-i)(k-i-1)^{n-1}$ 的形式，即选出i个不使用的颜色，用剩余颜色去涂的方案数。
代码：
/** Problem: Uvalive No.7040* Running time: 1.916MS* Complier: C++* Author: javaherongwei* Create Time: 20:10 2015/9/6 星期日**/#include <stdio.h>#include <string.h>#include <iostream>#include <algorithm>using namespace std;typedef long long LL;const LL MOD = 1e9+7;const LL N = 1e6+10;LL C[N],inv[N];LL n,m,k;LL pow_mod(LL a,LL b){LL res=a,ans=1;while(b){if(b&1) ans=ans*res%MOD;res=res*res%MOD;b>>=1;}return ans;}inline LL get_inverse(LL x){return pow_mod(x,MOD-2);}void init(){for(LL i=1; i<N; ++i)inv[i]=get_inverse(i);}void zuhe(LL n){C[0]=1;for(LL i=1; i<=k; ++i)C[i]=(C[i-1]*(n-i+1)%MOD)*inv[i]%MOD;}inline LL calc(LL x){return (C[x]*x%MOD)*(pow_mod(x-1,n-1)%MOD);}int main(){init();int t,tot=1;scanf("%d",&t);while(t–){scanf("%lld %lld %lld",&n,&m,&k);zuhe(m);LL ans_mk=C[k];zuhe(k);LL f1=0,f2=1;for(LL i=k; i>=1; –i){f1=(f1+f2*calc(i)+MOD)%MOD;f2=-f2;}ans_mk=ans_mk*f1%MOD;printf("Case #%d: ",tot++);printf("%lld\n",ans_mk);} return 0;}Uvalive 7035:
【题意】签到题，求一个序列里能被3整除的数的个数
代码：
/** Problem: Uvalive No.7035* Running time: 0.010MS* Complier: C++* Author: javaherongwei* Create Time: 20:20 2015/9/6 星期日*/#include <bits/stdc++.h>using namespace std;const int N=1e6+10;int arr[N];int main(){int t,tot=1;scanf("%d",&t);while(t–){int s=0,n;scanf("%d",&n);for(int i=0; i<n; ++i){scanf("%d",&arr[i]);if(arr[i]%3==0) s++;}printf("Case #%d: ",tot++);if(s==n) puts("Yes");else puts("No");}return 0;}Uvalive 7045: (gcd+模拟)
代码：
/** Problem: Uvalive No.7045* Running time: 0.010MS* Complier: C++* Author: javaherongwei* Create Time: 20:20 2015/9/6 星期日*/#include <bits/stdc++.h>using namespace std;typedef long long LL;LL n,m,k,a,b,c,ans;void get(LL a,LL b){if(b){ans+=a/b;get(b,a%b);}}int main(){ int t,tot=1;scanf("%d",&t); while(t–) {scanf("%lld %lld",&a,&b);printf("Case #%d: ",tot++);if(a==b&&b==0){puts("1");continue;}if(a!=b&&(a==0||b==0)){puts("2");continue;}if(max(a,b)-min(a,b)==min(a,b)){puts("3");continue;}ans=0;get(a,b);printf("%lld\n",ans+1); } return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
如若今生再相见，哪怕流离百世，迷途千年，也愿。
