A . 问一组数能否全部被3整除
K. S1 = A, S2 = B, Si = |Si-1 - Si-2|; 一直循环问， 出现了多少不同的数；
多模拟几组数， 可以发现和辗转相除法有很大关系
#include<bits/stdc++.h> using namespace std;
#define ll long long ll gcd(ll a, ll b)
{
ll cnt = ; // 一开始写的是 int wa 了很多次， 难受
if(b == )return ;
cnt += a/b;
cnt += gcd(b, a%b);
return cnt; } int main()
{
int T;
cin >> T;
int j = ;
while(j++ < T)
{
ll a,b;
cin >> a >> b;
ll ans ;
if(a==&&b==) {ans = ;printf("Case #%d: %lld\n",j,ans);continue;}
if((a==&&b!=)||(a!=&&b==)) {ans = ;printf("Case #%d: %lld\n",j,ans);continue;}
if(a < b) swap(a, b);
ans = gcd(a,b);
printf("Case #%d: %lld\n",j, ans);
}
}
F. 给你n朵花， m种颜色， 给花染色，要求正好用到K种颜色，并且相邻的花不能是相同的颜色
写的很详细 ： https://blog.csdn.net/qingshui23/article/details/51125323
首先从m种颜色种选取k种颜色的方案为C(m,k)，对于不超过的k种颜色的方案数很好求，为k*(k - 1)^(n - 1)，第一个物品有k种选择，之后的n－1个物品因为不能和前
面的相同，故都只有n－1种可能，但是题目要求的是恰好为k种的方案数，因此要容斥一下，容斥可以这样理解，假设不超过i种的方案数为F[i]，那么其中包括了不超
过i-1种的，不超过i-1种的里面又包含了不超过i-2种的，以此类推得到ans = F[k] - (F[k - 1] - (F[k - 2] - (... - (F[3] - F[2])))) = F[k] - F[k - 1] + F[k - 2] - ... + (-1)^(k - i)F[i]
因此最后答案为C(m,k)(Σ(-1)^(k - i)F[i])，其中F[i] = C(k,i)i*(i-1)^(n-1)
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
const int mod =;
using namespace std;
const int maxn=1e6+; int t;
ll n,m,k;
ll exgcd(ll a,ll b,ll &x,ll &y)
{
if(b==)
{
x=,y=;
return a;
}
else
{
ll q=exgcd(b,a%b,y,x);
y=y-x*(a/b);
return q;
}
}
ll niyuan(ll a,ll n)//逆元
{
ll x,y;
ll d=exgcd(a,n,x,y);
if(d==)
return (x%n+n)%n;
else
return -;
}
ll qmod(ll n,ll m,ll mod)//快速幂
{
ll ans=;
while(m)
{
if(m&)ans=(ans*n)%mod;
n=(n*n)%mod;
m>>=;
}
return ans%mod;
}
ll cm[maxn],ck[maxn],inv[maxn];
void get_inv()//打表
{
for(int i=;i<maxn;i++)
inv[i]=niyuan(i,mod);
}
void init()//打表
{
cm[]=,ck[]=;
for(int i=;i<=k;i++)
{
cm[i]=((cm[i-]%mod*(m-i+)%mod)*inv[i])%mod;
ck[i]=((ck[i-]%mod*(k-i+)%mod)*inv[i])%mod;
}
}
int main()
{ get_inv();
scanf("%d",&t);
int ca=;
while(t--)
{
scanf("%lld%lld%lld",&n,&m,&k);
init();
ll ret;
ll ans=;
for(ll i=k; i>=; i--)
{
if((k-i)%)
ret=-;
else
ret=;
ans=(ans+ret*i%mod*ck[i]%mod*qmod(i-,n-,mod)%mod+mod)%mod;
//二项式反演 }
ans=(ans*cm[k])%mod; printf("Case #%d: %lld\n",ca++,ans); }
}