未完待续
A.方格填数 2
这里提供一种可以用来蒙结论的方法：以大见小，由浅入深的暴力找规律。
之前模拟赛里出过本题的简易版，其中 m 固定为 3。那个题根据爆搜可以得到：当 n 为奇数时答案是 2 ^ n - 2，当 n 为偶数时答案是 2 ^ n + 2，特判 1。然后发现今天这个题和那天的挺像的，就是 m 不固定了，那为什么不蒙一下结论呢。
然后你尝试将式子表示为 $(m - 1) ^ n \pm (m - 1)$，并试了几组小数据，发现哇好像对了。
然后你也不想做这个题了，看上去并不可做，于是就用这个结论吧。
然后就过了。
虽然玄学，但也算学到如果遇到这么一道没什么头绪的结论题，以小见大，由浅入深，暴力找规律也是不错的选择。不保证对,但有一定可信度。
但是别忘了减法取模要加一遍模数！
痛失看似无意义的 20pts 但是需要撅一下警钟。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 1e9 + 7;
int n, m;
int bpow(int a, int b)
{
int tot = 1;
while(b)
{
if(b & 1) tot = (tot * a) % mod;
a = (a * a) % mod;
b >>= 1;
}
return tot % mod;
}
signed main()
{
while(~scanf("%lld%lld", &n, &m))
{
if(n == 1) printf("%lld\n", m % mod);
else if(n & 1) printf("%lld\n", (bpow((m - 1), n) % mod - m + 1 + mod) % mod);
else printf("%lld\n", (bpow((m - 1), n) % mod + (m - 1)) % mod);
}
return 0;
}
B.非严格上升子序列(syoj.1768)
首先感谢 @yb13558h 的思路，太强了，问了两遍终于懂了，感谢。
求长度为 1 ~ n 的序列，元素大小在 [A,B] 之间，非严格上升。
考虑按照大小放 A - B + 1 个盒子，一一对应 [A,B]。在这些盒子中把 n 个元素插进去。
但是为了保证这 A - B + 1 个盒子中，1~n 个元素个数都能取到，我们需要最后加一个盒子，放点多余的东西。
然后就转换成了盒球问题，球同盒不同，可以有空的。放球的方案就是符合要求的序列。答案为 $C_{B-A+1+n}^{B-A+1} - 1$。减一是去掉所有球都放到最后一个盒子里的方案。
因为我们的盒子都是按照大小排列的，所以最后出来的序列一定非严格上升。
求答案的时候用 Lucas 定理。这个之前讲过。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod = 1e6 + 3;
int T;
ll n, l, r;
ll jc[mod];
void init()
{
jc[0] = 1;
for(int i = 1; i < mod; i ++ ) jc[i] = jc[i - 1] * i % mod;
}
ll qpow(ll a, ll b)
{
ll tot = 1;
while(b)
{
if(b & 1) tot = (tot * a) % mod;
a = (a * a) % mod;
b >>= 1;
}
return tot;
}
ll C(ll x, ll y)
{
if(x < y) return 0;
return jc[x] * qpow(jc[y], mod - 2) % mod * qpow(jc[x - y], mod - 2) % mod;
}
ll lucas(ll n,ll m)
{
if(m > n) return 0;
if(! m) return 1;
return lucas(n / mod, m / mod) * C(n % mod, m % mod) % mod;
}
signed main()
{
init();
scanf("%d", &T);
while(T -- )
{
scanf("%lld%lld%lld", &n, &l, &r);
ll len = r - l + 1;
printf("%lld\n",(lucas(len + n, len) - 1 + mod) % mod);
}
return 0;
}
以及，求组合数的时候，记得要判一下两个数的大小。因为之前做的题都保证了大小，所以没有注意特判，这次因为要取模难免出现两个数大小不确定的时候。我就卡这里了。
C.积木大赛(syoj.1769)
根据题意，得知，让 1 ~ n 分别放置在 1 ~ n 处，要求让正好 m 个数仍在原位，其他数都不在原位的方案数。
这一看，不就是前两天上课讲的错排列吗？容易想到让 n - m 个数生成错排，在 n 中再选 m 个。即 $C_n^m \times f[n - m]$，f[i] 表示错排列方案数。
关于求错排列：设 f[i] 为 i 个数错排列的方案数，易得 f[1] = 0，f[2] = 1。那么第 i 位共有 i - 1 个位置可以放；
对于原本放在第一位上的数字 j，我们可以让它放在第 n 位，那么方案数只用考虑剩下的 i - 2 个数。
如果不让他放在第 n 位，那么方案数需要考虑 i - 1 个数。
综上：$$f[i] = (i - 1) \times (f[i - 1] + f[i - 2])$$
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod = 1e9 + 7;
const int N = 1e6 + 10;
int T;
int n, m;
ll f[N], jc[N];
ll ksm(ll a, ll b)
{
ll tot = 1;
while(b)
{
if(b & 1) tot = (tot * a) % mod;
a = (a * a) % mod;
b >>= 1;
}
return tot % mod;
}
ll C(ll x, ll y) {return jc[x] * ksm(jc[y], mod - 2) % mod * ksm(jc[x - y], mod - 2) % mod;}
void init()
{
jc[0] = 1;
f[0] = 1, f[1] = 0, f[2] = 1;
for(int i = 3; i <= N; i ++ ) f[i] = (i - 1) * (f[i - 1] + f[i - 2]) % mod;
for(int i = 1; i <= N; i ++ ) jc[i] = (jc[i - 1] * i) % mod;
}
int main()
{
init();
scanf("%d", &T);
while(T -- )
{
scanf("%d%d", &n, &m);
printf("%lld\n", C(n, m) * f[n - m] % mod);
}
return 0;
}