A.Character Encoding 简单计数
m个非负数和等于k的方案数为$\binom{m+k-1}{k}$, 但题目还要求每个数小于n, 容斥一下即可
即$ans = \sum\limits_{0\le i \le m}(-1)^i\binom{m}{i}\binom{m+k-1-ni}{k}$
B.Pizza Hub 计算几何
贪心可以知道最优情况三角形一定有一个顶点与矩形顶点重合, 暴力枚举判断一下即可
C. 不会
D.Parentheses Matrix 贪心
假设行列都为偶数, 因为奇数很容易特判. 再假设n>m, 我们假设初状态是每行全匹配, 再逐步调整到最优.
首先注意到第一列和最后一列显然不能动, 再考虑中间列的情况, 这里可以分两种情况讨论:
1, 保证每行都匹配
这样的话显然中间列匹配的上界为n+m/2-1, 手画一下很容易达到这个上界.
2, 不保证行匹配
这样的话, 手画一下可以发现, 通过破坏第一行和最后一行可以使得列全部匹配, 达到上界n+m-4.
最后取两种情况最大值即可.
但这题交了以后竟然WA了, 找了份题解拍了下所有小于200的n和m, 没发现是哪出锅了....
E. Magic Square 纯签到题
F. 不会
G.Make ZYB Happy 后缀自动机 (以后有时间补吧)
H. Taotao Picks Apples 讨论一下再二分
I.Pop the Balloons 状压
挺好的一个状压题, 三进制压一下, 第i位的0表示无气球, 1表示该位有气球, 2表示该位扎过一个气球
然后dp一次求出每种状态的方案数, 最后再统计答案即可.
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <queue>
#define pb push_back
#define REP(i,a,n) for(int i=a;i<=n;++i)
using namespace std;
typedef long long ll; const int N = 531450;
int n, m, k, t;
char a[22][22], b[22][22];
int g[N][22];
int fac[22], base[3][22];
ll dp[22][N], ans[22];
vector<int> f[22]; void work() {
scanf("%d%d%d", &n, &m, &k);
REP(i,1,n) scanf("%s", a[i]+1);
if (n<m) {
swap(n,m);
REP(i,1,n) REP(j,1,m) b[i][j]=a[j][i];
REP(i,1,n) REP(j,1,m) a[i][j]=b[i][j];
}
int mx = base[1][m]-1;
REP(i,1,n) f[i].clear();
REP(i,0,n) REP(j,0,mx) dp[i][j]=0;
REP(i,1,k) ans[i]=0;
REP(i,1,n) REP(j,1,m) if (a[i][j]=='Q') f[i].pb(j-1);
dp[0][0] = 1;
REP(i,1,n) REP(s,0,mx) if (dp[i-1][s]) {
int ss = s;
for (int j:f[i]) if (g[s][j]<2) {
dp[i][s-base[g[s][j]][j]+base[2][j]]+=dp[i-1][s];
if (!g[s][j]) ss += base[1][j];
}
dp[i][ss] += dp[i-1][s];
}
REP(s,0,mx) if (dp[n][s]) {
int f = 1, cnt = 0;
REP(j,0,m-1) {
if (g[s][j]==1) {f=0;break;}
if (g[s][j]==2) ++cnt;
}
if (f) ans[cnt] += dp[n][s];
}
ll mod = 1e12;
REP(i,1,k) {
__int128 t = (__int128)ans[i]*fac[i];
if (t>mod) printf("%lld%012lld\n",(ll)(t/mod),(ll)(t%mod));
else printf("%lld\n", (ll)t);
}
} int main() {
fac[0]=base[1][0]=1,base[2][0]=2;
REP(i,1,12) fac[i]=fac[i-1]*i;
REP(i,1,12) base[1][i]=base[1][i-1]*3;
REP(i,1,12) base[2][i]=base[2][i-1]*3;
REP(i,0,N-1) {
int t = i;
REP(j,0,12) g[i][j]=t%3, t/=3;
}
scanf("%d", &t);
REP(i,1,t) work();
}