256pt
bfs
576pt
有m块长度为L的木板，这些木板放置的位置只能是(i, i+L)这个区间，其中i必须是自然数。
在x = 0.5, 1.5, … (n-1).5都有对应的水滴下落频率。
每块木板放置的高度必须互不相同，如果两块模板同时占据了某个区间，那么只有高度比较高的那块木板能接到对应点的水。
每块木板接到的水的频率之和要在[A,B]这个区间内，问有多少不同的木板放置方案。
两个方案视作不相同当且仅当，有两个木板接到的水的区间范围不一样。
f[i][j][0] 表示第i个位置前没有木板，并已经放置了j块木板的方案数
f[i][j][1] 表示第i个位置前有一块木板的末尾，并已经放置了j块木板的方案数
f[i][j][2] 表示第i个位置前有一块木板，但那不是木板的结尾，需要放置一块木板在第(i, i+L)这个位置上以盖住这块木板的伸出部分。
转移一下即可。
#include <cstdio>
#include <cstring>
#include <cctype>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <iostream>
#include <map>
#include <set>
#include <list>
#include <sstream>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <bitset>
#include <algorithm>
using namespace std;
#define foreach(it, v) for (typeof((v).end()) it = (v).begin(); it != (v).end(); it++)
#define clr(a, x) memset(a, x, sizeof(a))
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define iter(v) typeof((v).end())
#define all(v) (v).begin(), (v).end()
#define DEBUG(a) cout << #a" = " << a << endl
#define DEBUGARR(a, n) rep(i, n) cout << #a"[" << i << "] = " << a[i] << endl
typedef long long ll;
const int N = 305;
const int Mod = 1000000009;
int n;
int a[N];
int sum[N];
int f[N][N][3];
void add(int &t, int x) {
t += x;
if (t >= Mod) t -= Mod;
}
class TheExperiment {
public:
int countPlacements(vector <string> intensity, int m, int L, int A, int B) {
n = sum[0] = 0;
rep (i, intensity.size()) {
rep (j, intensity[i].size()) {
a[n++] = intensity[i][j] - '0';
sum[n] = sum[n - 1] + a[n - 1];
}
}
clr(f, 0);
f[0][0][0] = 1;
rep (j, m + 1) {
rep (i, n + 1) {
int x = f[i][j][0];
int y = f[i][j][1];
int z = f[i][j][2];
add(f[i + 1][j][0], (x + y) % Mod);
int w = (x + z) % Mod;
if (i + L <= n) {
rep (k, L) {
int tmp = sum[i + k + 1] - sum[i];
if (A <= tmp && tmp <= B) {
add(f[i + k + 1][j + 1][k + 1 == L ? 1 : 2], w);
}
}
}
for (int k = 1; k <= L; k++){
if (i + k > n) continue;
if (i + k - L < 0) continue;
int tmp = sum[i + k] - sum[i];
if (A <= tmp && tmp <= B) {
add(f[i + k][j + 1][1], y);
}
}
}
}
return f[n + 1][m][0];
}
};
// Powered by FileEdit
// Powered by TZTester 1.01 [25-Feb-2003]
// Powered by CodeProcessor
900pt
一个大小为$$10^9 * W$$ 元素为$$a-z$$的字符矩阵，知道其中大小不超过$$10 * 10$$的子矩阵的元素，问生成这个矩阵的串s可能有多少种。
已知该矩阵的生成方式为：for (int cur = 0, i = 0; i < 10000000; i++) for (int j = 0; j < W; j++) { mat[i][j] = s[cur++]; cur %= s.size(); }
关键是弄清什么数目比较少，像这里是子矩阵比较小。
因为这个矩阵的生成方式是线性循环的，所以先把mat[i][j]化为mat[i * W + j]。
假设我们枚举了s的size，那么首先可以做的是判断这是不是一个可行的方案。
也就是判断是否存在mat[i % s.size()] != mat[j % s.size()] && i % s.size() == j % s.size()，这个直接两两枚举子矩阵元素判断即可。
在可行的前提下，只要再算算有多少个自由元，$$ans += 26^k$$即可，计算自由元的方法同样是两两枚举子矩阵。
但是这样肯定会TLE，所以看看哪些是可以直接一并处理的。
可以发现对于一个s的size，会造成i % s.size() == j % s.size()的情况是很少的。因为子矩阵元素总共才100个，也就是一共$$C(100, 2)$$对。而上面的等式成立的条件又是i - j == k * s.size()，所以可以找出每对i - j的约数，对它们进行上面提到的暴力处理。
而剩下的部分都是不存在i % s.size() == j % s.size()的，自由元的数目都是length - 子矩阵元素个数，所以方案都是$$26^{length - n}$$，这个随着length的增长形成等比数列，求和就很简单了。
总的来说，这个问题解决的方法来源于这样一种思路：解的大部分地方都是规则的，规则的地方直接用数学方法算出来。而对于少量不规则的部分再枚举出来单独处理。
在算法的设计中，正确衡量哪些东西比较少，哪些东西比较多是非常重要的。
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <bitset>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <cstring>
using namespace std;
#define clr(a,x) memset(a, x, sizeof(a))
#define foreach(it, v) for (iter(v) it = (v).begin(); it != (v).end(); it++)
#define pb push_back
#define mp make_pair
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define iter(v) __typeof((v).end())
typedef long long ll;
typedef pair <int,int> PII;
const int N = 100;
const int Mod = 1000000009;
int n, W;
ll c[N], w[N];
int power_mod(ll a, int b) {
if (b < 0) return 0;
ll res = 1;
while (b) {
if (b & 1) res = res * a % Mod;
a = a * a % Mod;
b >>= 1;
}
return res;
}
bool check(int len) {
rep (i, n)
for (int j = i + 1; j < n; j++)
if ((c[j] - c[i]) % len == 0 && w[i] != w[j])
return 0;
return 1;
}
int calc(int len) {
int cnt = 0;
rep (i, n) {
bool flag = 1;
rep (j, i) {
if ((c[i] - c[j]) % len == 0) {
flag = 0;
break;
}
}
cnt += flag;
}
return len - cnt;
}
void add(ll &res, ll x) {
res += x;
res %= Mod;
res += Mod;
res %= Mod;
}
int solve() {
set <ll> s;
rep (i, n) {
rep (j, n) {
if (i < j && !s.count(c[j] - c[i])) {
for (ll k = 1; k * k <= c[j] - c[i]; k++) {
if ((c[j] - c[i]) % k == 0) {
s.insert(k);
s.insert((c[j] - c[i]) / k);
}
}
}
}
}
ll ans = 0;
if (W >= n) {
ans = power_mod(26, W - n + 1);
add(ans, -1);
ans = ans * power_mod(25, Mod - 2) % Mod;
}
for (int i = 1; i < n && i <= W; i++) {
if (check(i)) {
add(ans, power_mod(26, calc(i)));
}
}
foreach (it, s) {
if (*it <= W && *it >= n) {
add(ans, -power_mod(26, *it - n));
if (check(*it)) {
add(ans, power_mod(26, calc(*it)));
}
}
}
return ans;
}
class CharacterBoard {
public:
int countGenerators(vector <string> fragment, int W, int i0, int j0) {
::W = W;
n = 0;
rep (i, fragment.size()) {
rep (j, fragment[i].size()) {
c[n] = (ll)(i0 + i) * W + (j0 + j);
w[n++] = fragment[i][j] - 'a';
}
}
return solve();
}
};
// Powered by FileEdit
// Powered by TZTester 1.01 [25-Feb-2003]
// Powered by CodeProcessor
// Powered by FileEdit
// Powered by TZTester 1.01 [25-Feb-2003]
// Powered by CodeProcessor