分类存档：默认分类

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