状态压缩DP

基本类型

参考题目

P1879 [USACO06NOV]Corn Fields G

https://www.luogu.com.cn/problem/P1879

题目描述

Farmer John has purchased a lush new rectangular pasture composed of M by N (1 ≤ M ≤ 12; 1 ≤ N ≤ 12) square parcels. He wants to grow some yummy corn for the cows on a number of squares. Regrettably, some of the squares are infertile and can't be planted. Canny FJ knows that the cows dislike eating close to each other, so when choosing which squares to plant, he avoids choosing squares that are adjacent; no two chosen squares share an edge. He has not yet made the final choice as to which squares to plant.

Being a very open-minded man, Farmer John wants to consider all possible options for how to choose the squares for planting. He is so open-minded that he considers choosing no squares as a valid option! Please help Farmer John determine the number of ways he can choose the squares to plant.

农场主John新买了一块长方形的新牧场，这块牧场被划分成M行N列(1 ≤ M ≤ 12; 1 ≤ N ≤ 12)，每一格都是一块正方形的土地。John打算在牧场上的某几格里种上美味的草，供他的奶牛们享用。

遗憾的是，有些土地相当贫瘠，不能用来种草。并且，奶牛们喜欢独占一块草地的感觉，于是John不会选择两块相邻的土地，也就是说，没有哪两块草地有公共边。

John想知道，如果不考虑草地的总块数，那么，一共有多少种种植方案可供他选择？（当然，把新牧场完全荒废也是一种方案）

输入格式

第一行：两个整数M和N，用空格隔开。

第2到第M+1行：每行包含N个用空格隔开的整数，描述了每块土地的状态。第i+1行描述了第i行的土地，所有整数均为0或1，是1的话，表示这块土地足够肥沃，0则表示这块土地不适合种草。

输出格式

一个整数，即牧场分配总方案数除以100,000,000的余数。

样例 #1

样例输入 #1

2 3
1 1 1
0 1 0

样例输出 #1

提示

参考代码

#include <bits/stdc++.h>
using namespace std;
const int mod = 100000000;
int n, m, x, ss;
int s[400], a[15];
int f[15][400];
int main()
{
	cin >> n >> m;
	for (int i = 0; i < 1 << m; i++)
	{
		if ((i & (i >> 1)) == 0)
		{
			s[ss++] = i;
		}
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			cin >> x;
			a[i] |= x << j;
		}
	}
	f[0][0] = 1;
	for (int i = 1; i <= n + 1; i++)
	{
		for (int j = 0; j < ss; j++)
		{
			if ((s[j] & a[i]) == s[j])
			{
				for (int k = 0; k < ss; k++)
				{
					if ((s[j] & s[k]) == 0)
					{
						f[i][j] = (f[i][j] + f[i-1][k]) % mod;
					}
				}
			}
		}
	}
	printf("%d\n", f[n + 1][0]);
	return 0;
}

题解

f[i][j]
for the first i rows, the i-th row is j

j is a set, we choose in the i-th row.

i = 000111
i>>1 = 00011
& = 00011

i = = 010101
i>>1 = 001010
& = 000000

a[i] = 10111 = {0, 1, 2, 4}
s[j] = 10101 = {0, 2, 4}

(s[j] & a[i]) == s[j]

1 1 1 111 = 7
0 1 0 010 = 2
0 0 1 100 = 4

1 0
1 1
1 0

f[i][j]
前i行，第i行选了j集合中的位置
0 <= i <= n
0 <= j < 2 ** m

m = 4

0000
0001
0010
0100
0101
1000
1001
1010

10 的二进制是 1010 = {1, 3}
15 的二进制是 1111 = {0, 1, 2, 3}

m=1, the number of ways=2
m=2, the number of ways=3
m=3, the number of ways=5
m=4, the number of ways=8
m=12, the number of ways=377

3 5
4 8
5 13
6 21
7 34
8 55
9 89
10 144
11 233
12 377

f[i][j]
前i行，第i行选了j集合中的位置
0 <= i <= n
0 <= j < 2 ** m

m = 4

0000
0001
0010
0100
0101
1000
1001
1010

10 的二进制是 1010 = {1, 3}
15 的二进制是 1111 = {0, 1, 2, 3}

if (j >> i & 1) 判断j的第i位是否是1

m 合法的状态数
3 5
4 8
5 13
6 21
7 34
8 55
9 89
10 144
11 233
12 377

f[i][j]
i：行数 0 <= i && i <= n + 1
j：列的子集 0 <= j && j < 1 << m
第i行，j集合这些列被选了
枚举第i+1行（或者是i-1行，谁转移到i）的状态k
(j & k) == 0

j的取值很小不是2**m

1: 2
2: 3
3: 5
4: 8
5: 13
6: 21
7: 34
8: 55
9: 89
10: 144
11: 233
12: 377

直接暴力枚举j和k的转移数是377*377
可以更快吗？是可以的，需要DFS

1L << 31

i >> j & 1

P3052 [USACO12MAR]Cows in a Skyscraper G

https://www.luogu.com.cn/problem/P3052

题目描述

A little known fact about Bessie and friends is that they love stair climbing races. A better known fact is that cows really don't like going down stairs. So after the cows finish racing to the top of their favorite skyscraper, they had a problem. Refusing to climb back down using the stairs, the cows are forced to use the elevator in order to get back to the ground floor.

The elevator has a maximum weight capacity of W (1 <= W <= 100,000,000) pounds and cow i weighs C_i (1 <= C_i <= W) pounds. Please help Bessie figure out how to get all the N (1 <= N <= 18) of the cows to the ground floor using the least number of elevator rides. The sum of the weights of the cows on each elevator ride must be no larger than W.

给出n个物品，体积为w[i]，现把其分成若干组，要求每组总体积<=W，问最小分组。(n<=18)

输入格式

* Line 1: N and W separated by a space.

* Lines 2..1+N: Line i+1 contains the integer C_i, giving the weight of one of the cows.

输出格式

* A single integer, R, indicating the minimum number of elevator rides needed.

one of the R trips down the elevator.

样例 #1

样例输入 #1

样例输出 #1

提示

There are four cows weighing 5, 6, 3, and 7 pounds. The elevator has a maximum weight capacity of 10 pounds.

We can put the cow weighing 3 on the same elevator as any other cow but the other three cows are too heavy to be combined. For the solution above, elevator ride 1 involves cow #1 and #3, elevator ride 2 involves cow #2, and elevator ride 3 involves cow #4. Several other solutions are possible for this input.

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[18];
pair<int, int> f[262144];
int main()
{
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	memset(f, 0x3f, sizeof f);
	f[0] = make_pair(0, m);
	for (int i = 0; i < 1 << n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (~i >> j & 1)
			{
				if (f[i].second + a[j] > m)
				{
					f[i | 1 << j] = min(f[i | 1 << j], make_pair(f[i].first + 1, a[j]));
				}
				else
				{
					f[i | 1 << j] = min(f[i | 1 << j], make_pair(f[i].first, f[i].second + a[j]));
				}
			}
		}
	}
	cout << f[(1 << n) - 1].first << endl;
	return 0;
}

题解

f[i] is the best solution of subset i

for (try all set i)
{
for (try all i's subset j)
{
if (sum(j) <= w)
{
f[i] = min(f[i], f[i-j] + 1);
}
}
}

for a prefix of the permutation, we want to minimize

the number of sets.
the sum of the last sum.

f[i] 表示集合i的最优解
转移的话枚举i的一个子集
时间复杂度是3 ** n

https://www.luogu.com.cn/blog/feecle6418/solution-p3052

f[i] 表示i集合最少分成几组，
转移的话枚举 i 的一个子集
时间复杂度是3 ** n

j = (j - 1) & i
--j &= i;

for (int i = 0; i < 1 << n; i++)
{
for (int j = i; j > 0; j = (j - 1) & i)
{
（这里会运行 3 ** n 次）
枚举i的所有非空子集 j
if (j集合中的数字之和 <= w)
{
f[i] = min(f[i], f[i - j] + 1);
}
}
}

为什么是 3 的 n 次方？
因为对于每一位来说，只有 3 种可能，
i = 0, j = 0
i = 1, j = 0
i = 1, j = 1
一共有n位，

f[i] = pair
表示已经放了 i 集合这些物品，最少需要几组，在此基础之上最后一组之和最小。

P2915 [USACO08NOV]Mixed Up Cows G

https://www.luogu.com.cn/problem/P2915

题目描述

Each of Farmer John's N (4 <= N <= 16) cows has a unique serial number S_i (1 <= S_i <= 25,000). The cows are so proud of it that each one now wears her number in a gangsta manner engraved in large letters on a gold plate hung around her ample bovine neck.

Gangsta cows are rebellious and line up to be milked in an order called 'Mixed Up'. A cow order is 'Mixed Up' if the sequence of serial numbers formed by their milking line is such that the serial numbers of every pair of consecutive cows in line differs by more than K (1 <= K <= 3400). For example, if N = 6 and K = 1 then 1, 3, 5, 2, 6, 4 is a 'Mixed Up' lineup but 1, 3, 6, 5, 2, 4 is not (since the consecutive numbers 5 and 6 differ by 1).

How many different ways can N cows be Mixed Up?

For your first 10 submissions, you will be provided with the results of running your program on a part of the actual test data.

POINTS: 200

约翰家有N头奶牛，第i头奶牛的编号是Si，每头奶牛的编号都是唯一的。这些奶牛最近在闹脾气，为表达不满的情绪，她们在挤奶的时候一定要排成混乱的队伍。在一只混乱的队伍中，相邻奶牛的编号之差均超过K。比如当K = 1时，1, 3, 5, 2, 6, 4就是一支混乱的队伍，而1, 3, 6, 5, 2, 4不是，因为6和5只差1。请数一数，有多少种队形是混乱的呢？

输入格式

* Line 1: Two space-separated integers: N and K

* Lines 2..N+1: Line i+1 contains a single integer that is the serial number of cow i: S_i

输出格式

* Line 1: A single integer that is the number of ways that N cows can be 'Mixed Up'. The answer is guaranteed to fit in a 64 bit integer.

样例 #1

样例输入 #1

样例输出 #1

提示

The 2 possible Mixed Up arrangements are:

3 1 4 2

2 4 1 3

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[16];
long long f[65536][16], z;
int main()
{
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
		f[1 << i][i] = 1;
	}
	for (int i = 0; i < 1 << n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (i >> j & 1)
			{
				for (int k = 0; k < n; k++)
				{
					if (~i >> k & 1)
					{
						if (abs(a[j] - a[k]) > m)
						{
							f[i | 1 << k][k] += f[i][j];
						}
					}
				}
			}
			if (i == (1 << n) - 1)
			{
				z += f[i][j];
			}
		}
	}
	cout << z << endl;
	return 0;
}

题解

f[i][j]
use the set i
the last cow is j
0 <= i < 2 ** n
0 <= j < n

from O(n!) to O(2 ** n * n ** 2)

f[集合][最后一个是什么]
处理排列相关的状态压缩动态规划

f[i]
i是一个集合，最小分成几组
枚举一个集合j，和i没有交集，集合j中所有牛的重量<=w

for (int i = 0; i < 1 << n; i++)
{
for (int j = 0; j < 1 << n; j++) // (想个办法枚举 n - 1 - i的子集)
{
if ((i & j) == 0)
{
cnt++;
直接做 O(4n);
优化做 O(3n);
if (s[j] <= K)
{
f[i+j] = min(f[i+j], f[i] + 1);
}
}
}
}
cnt == 3 ** n;
3种情况

i和j的第k位都是0
i的第k位是1，j的第k位是0
i的第k位是0，j的第k位是1

3**n 正确但可能超时的做法
https://www.luogu.com.cn/blog/feecle6418/solution-p3052
for(int i=1;i<(1<<n);i++){
for(int j=i;j;j=(j-1)&i){
if(s[j]>K)continue;
f[i]=min(f[i],f[i-j]+1);
}
}

2**n * n的做法
需要注意，我们决定的并不是如何分组，只需要决定加入顺序就可以了
另一个人看到这些牛的顺序，用贪心来决定如何分配子集
pair(到当前为止至少需要几组，在用最小组数的前提下，最后一个集合 sum最小是多少)

不可做题：给出n个数字ai
问能否把这n个数字分成两组，和相同。
ai <= 1e9
n = 100000
这没办法做

P3067 [USACO12OPEN]Balanced Cow Subsets G

https://www.luogu.com.cn/problem/P3067

题目描述

Farmer John's owns N cows (2 <= N <= 20), where cow i produces M(i) units of milk each day (1 <= M(i) <= 100,000,000). FJ wants to streamline the process of milking his cows every day, so he installs a brand new milking machine in his barn. Unfortunately, the machine turns out to be far too sensitive: it only works properly if the cows on the left side of the barn have the exact same total milk output as the cows on the right side of the barn!

Let us call a subset of cows "balanced" if it can be partitioned into two groups having equal milk output. Since only a balanced subset of cows can make the milking machine work, FJ wonders how many subsets of his N cows are balanced. Please help him compute this quantity.

给n个数，从中任意选出一些数，使这些数能分成和相等的两组。

求有多少种选数的方案。

输入格式

* Line 1: The integer N.

* Lines 2..1+N: Line i+1 contains M(i).

输出格式

* Line 1: The number of balanced subsets of cows.

样例 #1

样例输入 #1

样例输出 #1

提示

There are 4 cows, with milk outputs 1, 2, 3, and 4.

There are three balanced subsets: the subset {1,2,3}, which can be partitioned into {1,2} and {3}, the subset {1,3,4}, which can be partitioned into {1,3} and {4}, and the subset {1,2,3,4} which can be partitioned into {1,4} and {2,3}.

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, ss1, ss2;
int a[22];
pair<int, int> s1[60000];
pair<int, int> s2[60000];
bitset<1048576> v;
void gao(int *a, int n, pair<int, int> *s, int &ss)
{
	ss = 0;
	for (int i = 0; i < 1 << n; i++)
	{
		for (int j = i;; j = (j - 1) & i)
		{
			int u = 0;
			for (int k = 0; k < n; k++)
			{
				if (j >> k & 1)
				{
					u -= a[k];
				}
				else if (i >> k & 1)
				{
					u += a[k];
				}
			}
			s[ss++] = make_pair(u, i);
			if (j == 0)
			{
				break;
			}
		}
	}
	sort(s, s + ss);
	ss = unique(s, s + ss) - s;
}
int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	random_shuffle(a, a + n);
	gao(a, n / 2, s1, ss1);
	gao(a + n / 2, n - n / 2, s2, ss2);
	for (int i = 0, j = 0; i < ss1; i++)
	{
		while (j < ss2 && s1[i].first > s2[j].first)
		{
			j++;
		}
		for (int k = j; k < ss2 && s1[i].first == s2[k].first; k++)
		{
			v[s1[i].second | s2[k].second << (n / 2)] = 1;
		}
	}
	cout << v.count() - 1 << endl;
	return 0;
}

题解

{1, 2, 3, 4, 5, 6, 7, 8}
{1, 4, 5, 8} {2, 3, 6, 7}
{1, 2, 7, 8} {3, 4, 5, 6}

3 ** (n/2)

worst case
C(n/2, n/4) ** 2

P3092 [USACO13NOV]No Change G

https://www.luogu.com.cn/problem/P3092

题目描述

Farmer John is at the market to purchase supplies for his farm. He has in his pocket K coins (1 <= K <= 16), each with value in the range 1..100,000,000. FJ would like to make a sequence of N purchases (1 <= N <= 100,000), where the ith purchase costs c(i) units of money (1 <= c(i) <= 10,000). As he makes this sequence of purchases, he can periodically stop and pay, with a single coin, for all the purchases made since his last payment (of course, the single coin he uses must be large enough to pay for all of these). Unfortunately, the vendors at the market are completely out of change, so whenever FJ uses a coin that is larger than the amount of money he owes, he sadly receives no changes in return!

Please compute the maximum amount of money FJ can end up with after making his N purchases in sequence. Output -1 if it is impossible for FJ to make all of his purchases.

约翰到商场购物，他的钱包里有K(1 <= K <= 16)个硬币，面值的范围是1..100,000,000。

约翰想按顺序买 N个物品(1 <= N <= 100,000)，第i个物品需要花费c(i)块钱，(1 <= c(i) <= 10,000)。

在依次进行的购买N个物品的过程中，约翰可以随时停下来付款，每次付款只用一个硬币，支付购买的内容是从上一次支付后开始到现在的这些所有物品（前提是该硬币足以支付这些物品的费用）。不幸的是，商场的收银机坏了，如果约翰支付的硬币面值大于所需的费用，他不会得到任何找零。

请计算出在购买完N个物品后，约翰最多剩下多少钱。如果无法完成购买，输出-1

输入格式

* Line 1: Two integers, K and N.

* Lines 2..1+K: Each line contains the amount of money of one of FJ's coins.

* Lines 2+K..1+N+K: These N lines contain the costs of FJ's intended purchases.

输出格式

* Line 1: The maximum amount of money FJ can end up with, or -1 if FJ cannot complete all of his purchases.

样例 #1

样例输入 #1

样例输出 #1

提示

FJ has 3 coins of values 12, 15, and 10. He must make purchases in sequence of value 6, 3, 3, 2, 3, and 7.

FJ spends his 10-unit coin on the first two purchases, then the 15-unit coin on the remaining purchases. This leaves him with the 12-unit coin.

参考代码

#include <bits/stdc++.h>
using namespace std;
int a[16];
int s[100001];
int f[65536];
int n, m, z = -1;
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &a[i]);
	}
	for (int i = 1; i <= m; i++)
	{
		scanf("%d", &s[i]);
		s[i] += s[i - 1];
	}
	for (int i = 0; i < 1 << n; i++)
	{
		int t = 0;
		for (int j = 0; j < n; j++)
		{
			if (~i >> j & 1)
			{
				int l = upper_bound(s, s + m + 1, s[f[i]] + a[j]) - s - 1;
				f[i | 1 << j] = max(f[i | 1 << j], l);
				t += a[j];
			}
		}
		if (f[i] == m)
		{
			z = max(z, t);
		}
	}
	printf("%d\n", z);
	return 0;
}

题解

f[i] the maximum number of purchases of coin set i

O(2 ** k * k * log n)

find the largest i, such that a[i] <= x = find the smallest i, such that a[i] > x -

upp

{} {1} {2} {1, 2}

lower_bound(a, a + n, x) - a; 的类型是什么（指针的差类型是什么）

f[i] 表示集合i的最优解

if ((i >> j & 1) == 0)
if (~ i >> j & 1)

P4877 [USACO14FEB]Cow Decathlon G

https://www.luogu.com.cn/problem/P4877

题目描述

Farmer John's $N$ cows $(1 <= N <= 20)$ , conveniently labeled $1...N$ as always, are preparing for a decathlon that has $N$ different events (so perhaps it would be better called an N-athlon instead of a decathlon, which traditionally has exactly 10 events).

Cow i has a skill level of $s_ij$ $(1 <= s_ij <= 1000)$ when competing in event j. Each cow must compete in one and only one event, and each event must have some cow competing in it.

The total score for all cows is the sum of their skill levels for the events in which they are competing. However, the event judges can also give out bonus points if they are particularly impressed. There are $B$ bonuses $(1 <= B <= 20)$ that the judges can give out. Bonus i has three parts: if the cows obtain at least $P_i$ points $(1 <= P_i <= 40,000)$ for the first $K_i$ events (including other bonuses involving just those events), they will get an additional $A_i$ points $(1 <= A_i <= 1000)$ .

For example, let us consider $N = 3$ cows with the following skills:

      E V E N T
     | 1 | 2 | 3
   --+---+---+--
C  1 | 5 | 1 | 7
   --+---+---+--
O  2 | 2 | 2 | 4
   --+---+---+--
W  3 | 4 | 2 | 1

For example, cow 1 would earn the team 7 points if she participates in event 3.

Suppose the judges offer a bonus (B = 1), such that if the if the cows score at least 7 points in the first two events, they will get an additional 6 points. Here, the optimal assignment would be to assign cow 1 to event 1, cow 2 to event 3 and cow 3 to event 2. For the first two events, cow 1 will score 5 points and cow 3 will score 2 points giving them 7 points, which is enough to satisfy bonus 1. Therefore, the total points that they score will be 5+2+4+6=17.

Please help decide which events the cows should attempt to maximize their total score.

输入格式

Line 1: Two space-separated integers: $N, B$
Lines 2..B+1: Line i+1 will contain the information for bonus i which is three space- separated integers: $K_i, P_i, A_i$ .
Lines B+2..B+N+1: Line B+1+j will contain the information on how cow j will perform at each of her events. This will be given in $N$ space-separated integers: $s_j1...s_jN.$

输出格式

Line 1: The maximum amount of points that the cows can receive, including bonuses.

样例 #1

样例输入 #1

样例输出 #1

提示

Cow 1 will perform event 1, cow 3 will perform event 2, and cow 2 will perform event 3.

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m, x, y, z;
int a[21][21];
vector<pair<int, int> > b[21];
int f[1048577];
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; i++)
	{
		scanf("%d%d%d", &x, &y, &z);
		b[x].push_back(make_pair(y, z));
	}
	for (int i = 0; i < n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			scanf("%d", &a[i][j]);
		}
	}
	for (int i = 0; i <= n; i++)
	{
		sort(b[x].begin(), b[x].end());
	}
	for (int i = 0; i < 1 << n; i++)
	{
		int k = __builtin_popcount(i);
		for (int j = 0; j < n; j++)
		{
			if (i >> j & 1)
			{
				f[i] = max(f[i], f[i ^ 1 << j] + a[j][k]);
			}
		}
		for (pair<int, int> j: b[k])
		{
			if (f[i] >= j.first)
			{
				f[i] += j.second;
			}
		}
	}
	printf("%d\n", f[(1 << n) - 1]);
	return 0;
}

题解

P2167 [SDOI2009]Bill的挑战

https://www.luogu.com.cn/problem/P2167

题目描述

Sheng_bill 不仅有惊人的心算能力，还可以轻松地完成各种统计。在昨天的比赛中，你凭借优秀的程序与他打成了平局，这导致 Sheng_bill 极度的不满。于是他再次挑战你。这次你可不能输。

这次，比赛规则是这样的：

给出 $N$ 个长度相同的字符串（由小写英文字母和 ? 组成）， $S_1,S_2,\dots,S_N$ ，求与这 $N$ 个串中的刚好 $K$ 个串匹配的字符串 $T$ 的个数，答案对 $1000003$ 取模。

若字符串 $S_x(1\le x\le N)$ 和 $T$ 匹配，满足以下条件：

$|S_x|=|T|$ 。
对于任意的 $1\le i\le|S_x|$ ，满足 $S_x[i]= \texttt{?}$ 或者 $S_x[i]=T[i]$ 。

其中 $T$ 只包含小写英文字母。

输入格式

本题包含多组数据。

第一行一个整数 $T$ ，表示数据组数。

对于每组数据，第一行两个整数， $N$ 和 $K$ 。

接下来 $N$ 行，每行一个字符串 $S_i$ 。

输出格式

每组数据输出一行一个整数，表示答案。

样例 #1

样例输入 #1

5

3 3

???r???

???????

???????

3 4

???????

?????a?

???????

3 3

???????

?a??j??

????aa?

3 2

a??????

???????

???????

3 2

???????

???a???

????a??

样例输出 #1

提示

数据规模与约定

对于 $30\%$ 的数据， $N\le5$ ， $|S_i|\le20$ ；
对于 $70\%$ 的数据， $N\le13$ ， $|S_i|\le30$ ；
对于 $100\%$ 的数据， $1\le T\le 5$ ， $1\le N \le15$ ， $1\le|S_i|\le50$ 。

参考代码

#include<stdio.h>
#include<iostream>
#include<string.h>
#define C(x) __builtin_popcount(x)
using namespace std;
int g[60][26],f[60][32780];
char s[20][60];
int z[32780], t[20], c[20][20];
int tt,n,q,l,mo=1000003;
int dp(int b) {
	int z = 1;
	for (int i = 0; i < l; i++) {
		char c = '?';
		for (int j = 0; j < n; j++) {
			if ((b >> j & 1) && s[j][i] != '?') {
				if (c != '?' && c != s[j][i]) {
					return 0;
				}
				c = s[j][i];
			}
		}
		if (c == '?') {
			z = z * 26 % mo;
		}
	}
	return z;
}
int main()
{
	for (int i = 0; i < 20; i++) {
		c[i][0] = 1;
		for (int j = 1; j <= i; j++) {
			c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mo;
		}
	}
	for(scanf("%d",&tt);tt--;)
	{
		scanf("%d%d",&n,&q);
		for(int i=0;i<n;i++)
			scanf("%s",s[i]);
		l = strlen(s[0]);
		memset(t, 0, sizeof t);
		t[q] = 1;
		for (int i = q + 1; i <= n; i++) {
			for (int j = 0; j < i; j++) {
				t[i] -= (long long)t[j] * c[i][j] % mo;
				if (t[i] < 0) {
					t[i] += mo;
				}
			}
		}
		long long ans = 0;
		for (int i = 0; i < 1 << n; i++) {
			ans = (ans + (long long)t[C(i)] * dp(i)) % mo;
		}
		printf("%lld\n", ans);
	}
	return 0;   
}

题解

容斥原理
希望和ABCD中恰好2个匹配
[AB] 表示一定和AB匹配，和CD的关系任意

[AB] + [AC] + [AD] + [BC] + [BD] + [CD] - 3 * [ABC] - 3 * [ABD] - 3 * [ACD] - 3 * [BCD] + 6 * [ABCD]

C(-3, 0) = 1 = 1
C(-3, 1) = -2 / 1 = -3
C(-3, 2) = -3 * -4 / 2 = 6
C(-3, 3) = -3 * -4 * -5 / 6 = -10

C(n, m) = n * (n - 1) * .. * (n - m + 1) / m!

P1433,P1879,P1896,P2051,P2150,P2167,P2704,P3052,P3067,P3092,P3160,P3226,P3349,P3959,P5005

判断i的第j位是不是1
if (i >> j & 1)

（最低位是第0位）

判断i的第j位是不是0
if (~i >> j & 1)

输入一个图，求一条路径，访问每个点1次，问最短距离/问不经过重复的点是否可行，都NPC

f[i][j]
i是一个集合
0 <= i && i < (1 << n)
0 <= j < n
当前已经经过了i集合中的点，最后一个经过的点是j
显而易见(i >> j & 1) == 1

输入n个点，m条边的有向图
问有多少种方案从任意起点出发，遍历整个图，不经过重复点

double f[1];
memset(f, i, sizeof f);
printf("%d %g\n", i, f[0]);

double存储方式和int/long long不一样
结果不那么好预测
127 1.38242e+306 最大的
128 -2.93745e-306 最小的
254 -5.31401e+303

fill(f, f + n, 1e30);

f[i][j]
i是一个集合
0 <= i && i < (1 << n)
0 <= j < n
f[i][j] -> f[i | 1 << k][k]
2n * n2

直接暴力所有排列，时间复杂度
n! * n

状态压缩DP
2n * n2

P4544 [USACO10NOV]Buying Feed G

https://www.luogu.com.cn/problem/P4544

题目描述

约翰开车来到镇上，他要带 $K$ 吨饲料回家。运送饲料是需要花钱的，如果他的车上有 $X$ 吨饲料，每公里就要花费 $X^2$ 元，开车D公里就需要 $D\times X^2$ 元。约翰可以从 $N$ 家商店购买饲料，所有商店都在一个坐标轴上，第 $i$ 家店的位置是 $X_i$ ，饲料的售价为每吨 $C_i$ 元，库存为 $F_i$ 。

约翰从坐标 $X=0$ 开始沿坐标轴正方向前进，他家在坐标 $X=E$ 上。为了带 $K$ 吨饲料回家，约翰最少的花费是多少呢？假设所有商店的库存之和不会少于 $K$ 。

举个例子，假设有三家商店，情况如下所示：

坐标	$X=1$	$X=3$	$X=4$	$E=5$
库存	$1$	$1$	$1$
售价	$1$	$2$	$2$

如果 $K=2$ ，约翰的最优选择是在离家较近的两家商店购买饲料，则花在路上的钱是 $1+4=5$ ，花在商店的钱是 $2+2=4$ ，共需要 $9$ 元。

输入格式

第 $1$ 行:三个整数 $K,E,N$ 第 $2..N+1$ 行:第 $i+1$ 行的三个整数代表, $X_i,F_i,C_i$ .

输出格式

一个整数,代表最小花费

样例 #1

样例输入 #1

样例输出 #1

提示

$1 \leq K \leq 10000 , 1 \leq E \leq 500 , 1 \leq N \leq 500$

$0 < Xi < E, 1 \leq Fi \leq 10000, 1 \leq C_i \leq 10^7$

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m, l;
long long f[10020];
pair<int, pair<int, int> > a[520];
void gao(int x, long long y)
{
	for (int i = m; i >= x; i--)
	{
		f[i] = min(f[i], f[i - x] + y);
	}
}
int main()
{
	scanf("%d%d%d", &m, &l, &n);
	for (int i = 0; i < n; i++)
	{
		scanf("%d%d%d", &a[i].first, &a[i].second.first, &a[i].second.second);
	}
	sort(a, a + n);
	a[n].first = l;
	memset(f, 0x3f, sizeof f);
	f[0] = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 1; j <= a[i].second.first; j *= 2)
		{
			a[i].second.first -= j;
			gao(j, (long long)j * a[i].second.second);
		}
		gao(a[i].second.first, (long long)a[i].second.first * a[i].second.second);
		for (int j = 0; j <= m; j++)
		{
			f[j] += (long long)j * j * (a[i + 1].first - a[i].first);
		}
	}
	printf("%lld\n", f[m]);
	return 0;
}

题解

f[i][j] 到位置i 携带 j 的饲料，最小花费
如果i位置没有商店，那么直接f[i][j] = f[i-1][j] + j * j
如果i位置有商店，那么直接f[i][j] = min(f[i-1][j] + j * j, f[i][j - k] + k * 单价) 在i位置买k的饲料

上限 100 个， 100 个零一背包

100 = 1 + 2 + 4 + 8 + 16 + 32 + 37

5 * 1
5 * 2
5 * 4
5 * 8
5 * 16
5 * 32
5 * 37

f[i][j] min cost at position i, j units of feed.
if there is no shop at i,
f[i][j] = f[i-1][j] + j * j;

if there is a shop at i,
we should do knapsack on f[i]

monotonic queue

do weight times monotonic queue, each with length (size/weight)

weight = 2
value = v
limit = 3;

f[13] = max(f[13], f[11] + v, f[9] + v * 2, f[7] + v * 3)
f[11] = max(f[11], f[ 9] + v, f[7] + v * 2, f[5] + v * 3)
f[9]  = max(f[ 9], f[ 7] + v, f[5] + v * 2, f[3] + v * 3)
f[7]  = max(f[ 7], f[ 5] + v, f[3] + v * 2, f[1] + v * 3)

f[13] = max(f[13]-6*v, f[11]-5*v, f[9]-4*v, f[7]-3*v) + 6*v;
f[11] = max(f[11]-5*v, f[ 9]-4*v, f[7]-3*v, f[5]-2*v) + 5*v;
f[9]  = max(f[ 9]-4*v, f[ 7]-3*v, f[5]-2*v, f[3]-1*v) + 4*v;
f[7]  = max(f[ 7]-3*v, f[ 5]-2*v, f[3]-1*v, f[1]-0*v) + 3*v;

f[1]-0*v, f[3]-1*v, f[5]-2*v, f[7]-3*v, f[9]-4*v, f[11]-5*v, f[13]-6*v
f[0]-0*v, f[2]-1*v, f[4]-2*v, f[6]-3*v, f[8]-4*v, f[10]-5*v, f[12]-6*v

spoj REDRONESIA

https://atcoder.jp/contests/arc057/tasks/arc057_d
https://atcoder.jp/contests/arc057/submissions/2640690

P2915 [USACO08NOV]Mixed Up Cows G

P2051 [AHOI2009]中国象棋

一行一行来放
状态需要记录
f[放了几行][有多少列放了0个炮][有多少列放了1个炮][有多少列放了2个炮]
最后3维只需要记2维
状态数n * m * m
转移O(1)

放0个棋子

什么都不放
放1个棋子
0个炮->1个炮
1个炮->2个炮
放2个棋子
0个炮->1个炮 0个炮->1个炮
0个炮->1个炮 1个炮->2个炮
1个炮->2个炮 1个炮->2个炮
不建议记忆化搜索

n = 2
m = 2
f[1行][1列0个炮][1列1个炮] = 2
所有满足有 1列0个炮 1列1个炮方案之和所以等于2
任意一个满足有 1列0个炮 1列1个炮方案之和所以等于1
（显而易见，所有 1列0个炮 1列1个炮的方案数是相同的）

第一种理解 = 第二种理解 * 方案数

f[i][j][k] = f[i行][j个1][k个2]

include

define mod 9999973

define R register

using namespace std;
inline void in(int &x)
{
int f=1;x=0;char s=getchar();
while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}
while(isdigit(s)){x=x10+s-'0';s=getchar();}
x=f;
}
int n,m;
typedef long long ll;
ll ans;
ll f[108][108][108];
ll inv(ll x)
{
if (x == 1)
{
return 1;
}
return inv(mod % x) * (mod - mod / x) % mod;
}
inline ll C(ll x, ll y)
{
ll re = 1;
for (int i = 0; i < y; i++)
{
re = re * (x - i) % mod * inv(i + 1) % mod;
}
return re;
}
signed main()
{
in(n),in(m);
f[0][0][0]=1;
for(R int i=1;i<=n;i++)
{
for(R int j=0;j<=m;j++)
{
for(R int k=0;k<=m-j;k++)
{
f[i][j][k]=f[i-1][j][k];
if(k>=1)f[i][j][k]+=f[i-1][j+1][k-1]*k;
if(j>=1)f[i][j][k]+=f[i-1][j-1][k]*j;
if(k>=2)f[i][j][k]+=f[i-1][j+2][k-2]*C(k,2) % mod;
if(k>=1)f[i][j][k]+=f[i-1][j][k-1]kj % mod;
if(j>=2)f[i][j][k]+=f[i-1][j-2][k]*C(j,2) % mod;
f[i][j][k]%=mod;
}
}
}
for(R int i=0;i<=m;i++)
for(R int j=0;j<=m;j++)
{
ans += f[n][i][j] * C(m, i) % mod * C(m - i, j) % mod;
}
printf("%lld\n",(ans+mod)%mod);
}

P4783 【模板】矩阵求逆

http://acm.hdu.edu.cn/showproblem.php?pid=6410

const int mod = 1000000007
王逸松骆可强

int
加法减法越界相当于对232取模
unsigned 加减法越界，相当于对232取模
signed 加减法越界，是未定义行为
if (a < 0 && b < 0 && a + b > 0)
{
// 永远不会被运行到
}

乘法越界
unsigned 32位
unsigned * unsigned
计算机内部会得到64位的结果，但是只会返回低32位

加减法不区分有无符号
乘法区分有无符号的乘法

除法和余数

计算机真的算除法，没有被优化
(unsigned, unsigned) / unsigned = unsigned ...... unsigned

(long long, long long) / long long = long long ...... longlong

long long * long long % long long
可以内联汇编

https://www.cnblogs.com/bibibi/p/9613151.html

计算机没有算除法，优化成了乘法和右移
先计算商
如果需要余数
被减数 - 除数*商 = 余数

32位计算机的long long 比 64位计算机的long long慢非常多

P1879 [USACO06NOV]Corn Fields G

P2704 [NOI2001]炮兵阵地
f[i][j][k]
前i行
第i行是j
第i-1行是k

P5005 中国象棋 - 摆上马

https://www.luogu.com.cn/blog/user24518/solution-p5005

P2150 [NOI2015]寿司晚宴

2 3 5 7

第一个人取了 2 4 8 16
第二个人取了 3 9 27 81

{2} {3, 5, 7} + 1
{2, 5} {3, 7} + 1
{2, 7} {3, 5} + 1
{2, 5, 7} {3} + 1

{2} {3, 5} - 1
{2, 5} {3} - 1
{2} {3, 7} - 1
{2, 7} {3} - 1

{2} {3} + 1

能不能出到1000呢？

P2167 [SDOI2009]Bill的挑战

一共4个字符串，恰好匹配其中2个
ABCD

只能处理类似于求匹配AB（CD是否匹配不知道）的方案数

方法一：
求出每个子集的答案，做一遍子集和变换

方法二：
AB + AC + AD + BC + BD + CD - 3 * ABC - 3 * ABD - 3 * ACD - 3 * BCD + 6 * ABCD

include<stdio.h>

include

include<string.h>

define C(x) __builtin_popcount(x)

using namespace std;
char s[20][60];
int c[20][20];
int tt,n,q,l,mo=1000003;
int dp(int b) {
int z = 1;
for (int i = 0; i < l; i++) {
char c = '?';
for (int j = 0; j < n; j++) {
if ((b >> j & 1) && s[j][i] != '?') {
if (c != '?' && c != s[j][i]) {
return 0;
}
c = s[j][i];
}
}
if (c == '?') {
z = z * 26 % mo;
}
}
return z;
}
int main()
{
for (int i = 0; i < 20; i++) {
c[i][0] = 1;
for (int j = 1; j <= i; j++) {
c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mo;
}
}
for(scanf("%d",&tt);tt--😉
{
scanf("%d%d",&n,&q);
for(int i=0;i<n;i++)
scanf("%s",s[i]);
l = strlen(s[0]);
long long ans = 0;
for (int i = 0; i < 1 << n; i++) {
if (__builtin_parity(i ^ q))
ans = (ans - (long long)c[__builtin_popcount(i)][q] * dp(i)) % mo;
else
ans = (ans + (long long)c[__builtin_popcount(i)][q] * dp(i)) % mo;
}
printf("%lld\n", ans);
}
return 0;
}

折半搜索

P4799 [CEOI2015 Day2]世界冰球锦标赛

需要用2n的时间生成一个大小为n的集合的所有子集之和
注意是2n的时间，不是2**n * n
可以用数组和lowbit推，也可以dfs
a[0 .. n-1]
s[0 .. (1 << n) - 1]
for (int i = 0; i < n; i++)
{
s[1 << i] = a[i];
}
for (int i = 1; i < 1 << n; i++)
{
s[i] = s[i - (i & -i)] + s[i & -i];
}

map<int, vector >

P3349 [ZJOI2016]小星星

树 1 2 3 -> 图 1 2 3
树 1 2 3 -> 图 3 2 1

树 1 2 3 -> 图 1 2 1
树 1 2 3 -> 图 2 1 2

树 1 2 3 -> 图 3 2 3
树 1 2 3 -> 图 3 1 3

P3959 宝藏

https://www.luogu.com.cn/blog/dazade8/solution-p3959