摘要
本文主要给出了2014-2015 ACM-ICPC, Asia Xian Regional Contest的部分题解，说明了每题的题意、解题思路和代码实现，意即熟悉区域赛比赛题型。
Built with Qinghuai and Ari Factor
题意
判断是否是Q数列，只要数列中每个数均能够被3整除就是Q数列。
解题思路
需要特判一下0的情况。
代码
#include <cstdio> int main()
{
int T;
int n;
int t = ;
scanf("%d", &T);
while(T--) {
scanf("%d", &n);
int f = ;
int x;
for(int i = ; i < n; i++) {
scanf("%d", &x);
if(x == || x % != )
f = ;
}
if(f)
printf("Case #%d: No\n",t++);
else
printf("Case #%d: Yes\n",t++);
}
return ;
}
题意
定义一个序列，前两项是a和b，第三项是前两项之差的绝对值，然后依次类推，问会出现多少个不同的数字。
解题思路
首先能够想到的是该数列最终会呈现...,x,0,x,0这样的序列，但是出现过多少个不同的数字呢，其实给出a和b后，不妨将a写成kb + tmp的形式，其中不同的数字个数就是k个，因为每次相减后出现一个（k - 1）* b + tmp，总共有k个，但这只是一组（相当于减到底），下一组就是b = a % b，a = b，直到b等于0的的时候，就可以结束了，最后再加上0这个数字的1个。
注意考虑特殊情况，当a == 0 且b != 0 或者 b == 0 且 a ！= 0时 sum = 2；
当a = b = 0时，sum = 1；
代码
#include <cstdio>
typedef long long ll; int main()
{
int T, t = ;
scanf("%d", &T);
ll a, b, tmp, sum;
while(T--) {
scanf("%lld %lld", &a, &b);
if(a == && b == )
sum = ;
else if((a == && b != ) || (a != && b == ))
sum = ;
else {
sum = ;
tmp = ;
while(tmp) {
sum += a / b;
tmp = a % b;
a = b;
b = tmp;
}
}
printf("Case #%d: %lld\n", t++, sum);
}
return ;
}
题意
给出n朵花，排成一行，问从m种颜色中挑出k种染色，使得这n朵花使用恰好k种颜色的同时两个相邻的话不同颜色，有多少种不同的方案。
解题思路
不难从m中颜色重挑出k中颜色，即C(m, k)。然后计算恰好使用k种颜色去染着n朵花，容易写出C(m, k) * k * (k - 1)^(n - 1)种方法，但是仔细想一下，这计算了最多使用k种颜色染的方案数，包含重复计数，这里就要考虑容斥了，假设最多使用 i 种颜色的方案数为F[i]，那么其中包括了最多使用 i-1 种的，最多使用 i-1 种的里面又包含了最多使用 i-2 种的，以此类推得到
ans = C(m, k) * (F[k] - (F[k - 1] - (F[k - 2] - (... - (F[3] - (F[2] - F[1])))))) = C(m, k) * (F[k] - F[k - 1] + F[k - 2] - ... + (-1)^(k - i)F[i] + (-1)^(k -2)F[2] + (-1)^(k - 1)F[1])，其中F[i]根据之前的计算方法等于(-1)^(k - i) * C(k, i) * (k - i)^(n - 1) 。
也可以看下表
如果减去f[i-1]的话，相当于减去整个表格里的内容：一个 i-1, 两个 i-2, 三个 i-3 .....所以因为减去了两个i-2，所以需要把i-2加回来一个，所以 + f[i-2] 就行了，其他同理 ，即可解释容斥原理。举个例子，如果选取的k个颜色是1,2,3,4，会有一种染色方案是1,2,1,2...，如果选取的k-1个颜色是1,2,3，仍然会包含一种染色方案1,2,1,2...所以上面的公式要再加上颜色数<=(k-2)的方案数，然后再减去颜色数<=(k-3)的方案数。
剩下的就是具体实现的细节了，首先怎么快速计算C(m, k)和C(k, i)?使用递推的方式，公式推导如下
然后其中使用到了乘法逆元。
最后就是了解一下输入输出外挂（不加也可以A）。
代码如下
#include <cctype>
#include <cstdio> typedef long long ll;
const int mod = 1e9 + ;
const int maxk = 1e6 + ; ll Sca() {
ll res = , f = ;
char x = getchar();
if(x == '-')
f = ;
if(x >= '' && x <= '')
res = x - '';
while((x = getchar()) >= '' && x <= '')
res = res * + (x - '');
return f ? -res : res;
}
void Out(ll x) {
if(x > )
Out(x / );
putchar(x % + '');
}
ll qpow(ll x, ll n) {
ll ans = ;
while(n) {
if(n & )
ans = ans * x % mod;
x = x * x % mod;
n >>= ;
}
return ans;
}
ll inv[maxk];
void get_inv() {
for(ll i = ; i < maxk; i++) {
inv[i] = qpow(i, mod - );
}
}
ll ck[maxk], cm[maxk];
void get_c(ll m, ll k) {
cm[] = ck[] = ;
for(ll i = ; i <= k; i++) {
cm[i] = (cm[i - ] * (m - i + ) % mod) * inv[i] % mod ;
ck[i] = (ck[i - ] * (k - i + ) % mod) * inv[i] % mod;
}
}
int main()
{
get_inv();
ll T;
T = Sca();
ll n, m, k;
for(ll ca = ; ca <= T; ca++) {
n = Sca();
m = Sca();
k = Sca(); get_c(m, k);
ll ans = ;
ll f = ;
for(ll i = k; i >= ; i--, f = -f) {
ans = (ans + (f * ck[i] * i % mod * qpow(i - , n - ) % mod) + mod) % mod;
}
ans = ans * cm[k] % mod;
printf("Case #%lld: %lld\n", ca, ans);
}
return ;
}