2018ACM-ICPC徐州赛区网络赛: A. Hard to prepare【递推】+【dp】

题目链接：传送门

题意就不说了

思路：

一开始比赛的时候就是想   

k = 2^m

答案等于 k*（(k-1）^(m-1)） 发现多了情况 因为是个环

然后换成 k*（(k-2）^(m-1)）*（k-2） 发现漏算了第一个和倒数第二个相同的情况

看了网上的其他题解，包括比赛时打的表明白了这其中的规律

那么我们可以先算出第一个和倒数第二个不同的情况，而当他们相同的时候那么最后一个就有（k-1）种情况，那么就相当于整个长度被减去了2，得出的结果再加上去，可以由此进行dfs，因为给的n的值不大，时间复杂度是O（n），最后得出结果。

#include<bits/stdc++.h>
#define ll long long
#define MOD 1000000007
#define MAXN 1000005
using namespace std;
ll inv[MAXN];
ll k, n, m;
void init() {
	inv[1] = 2;
	for(int i = 2; i < MAXN; i++){
		inv[i] = inv[i-1] * 2LL % MOD;
	}
}
ll qpow(ll a, ll b){
	ll t = a, ans = 1;
	while(b) {
		if(b % 2){
			ans = ans * t % MOD;
		}
		t = t * t % MOD;
		b /= 2;
	}
	return ans;
}
ll cheak(ll len){
	if(len == 1){
		return k;
	}
	if(len == 2){
		return k * (k - 1) % MOD;
	}
	ll res = 0;
	res = k * qpow(k - 1, len - 2) % MOD * (k - 2) % MOD + cheak(len - 2) % MOD;
	return res;
}

int main() {
	int t;
	scanf("%d", &t);
	init();
	while(t--) {
		scanf("%lld%lld", &n, &m);
		k = inv[m] % MOD;
		printf("%lld\n", cheak(n) % MOD);
	}
	return 0;
} 

再搞上一波在别的博客学到的dp做法：

定义：

dp[i][0] 至第i个人分发面具的方案数，且 mask[i] = mask[1]

dp[i][1]至第i个人分发面具的方案数，且 mask[i] XNOR mask[1] = 0

dp[i][2]至第i个人分发面具的方案数，且 mask[i] ≠ mask[1]，mask[i] XNOR mask[1] ≠ 0

AC_code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN 1000005
#define MOD 1000000007
ll inv[MAXN];
ll dp[MAXN][3];
void init() {
	inv[0] = 1;
	for(int i = 1; i < MAXN; i++){
		inv[i] = inv[i-1] * 2LL % MOD;
	}
	return ;
}
ll DP(int n, int m) {
	dp[1][0] = 1;
	for(int i = 2; i <= n; i++){
		dp[i][0] = (dp[i - 1][0] + dp[i - 1][2]) % MOD;
		dp[i][1] = (dp[i - 1][1] + dp[i - 1][2]) % MOD;
		dp[i][2] = (dp[i - 1][0] + dp[i - 1][1]) * (inv[m] - 2 + MOD) % MOD + dp[i - 1][2] * (inv[m] - 3 + MOD) % MOD;
	}
	return (dp[n][0] + dp[n][2]) * inv[m] % MOD;
}
int main() {
	int n, m, t;
	scanf("%d", &t);
	init();
	while(t--) {
		scanf("%d%d", &n, &m);
		ll ans = DP(n, m);
		printf("%lld\n", ans);
	}
	return 0;
}