Posted on 2012-03-12 23:30
Mato_No1 阅读(487)
评论(0) 编辑 收藏 引用 所属分类:
递推
COCI 2011~2012 #2 funkcija其思想的巧妙程度以及各种细节的处理难度远超AHOI2009的cchess（以前本沙茶总以为这种才是最神的递推题囧……）
具体的题解以及方法归纳以后再写，先上代码：
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re1(i, n) for (int i=1; i<=n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
#define rre(i, n) for (int i=n-1; i>=0; i--)
#define rre1(i, n) for (int i=n; i>0; i--)
#define rre2(i, r, l) for (int i=r-1; i>=l; i--)
#define rre3(i, r, l) for (int i=r; i>=l; i--)
#define ll long long
const int MAXN = 27, MAXM = 100010, MOD = 1000000007, INF = ~0U >> 2;
struct edge {
int a, b, pre, next;
} E[(MAXN << 2) + 1];
int n, m, A[MAXN][2];
ll F[MAXN][MAXM], G[MAXN][MAXM], res;
void init_d()
{
re1(i, n) E[i].pre = E[i].next = i; m = n + 1;
}
void add_edge(int a, int b)
{
E[m].a = a; E[m].b = b; E[m].pre = E[a].pre; E[m].next = a; E[a].pre = m; E[E[m].pre].next = m++;
}
void init()
{
scanf("%d", &n);
char ss0[20], ss1[20];
re1(i, n) {
scanf("%s %s", ss0, ss1);
if (ss0[0] >= 48 && ss0[0] <= 57) A[i][0] = atoi(ss0); else A[i][0] = 96 - ss0[0];
if (ss1[0] >= 48 && ss1[0] <= 57) A[i][1] = atoi(ss1); else A[i][1] = 96 - ss1[0];
}
init_d();
re1(i, n) {
if (A[i][0] < 0) add_edge(-A[i][0], i);
if (A[i][1] < 0) add_edge(-A[i][1], i);
}
}
void solve()
{
int x, y, tmp;
rre1(i, n) re2(j, 1, MAXM) {
F[i][j] = 1;
for (int p=E[i].next; p != i; p=E[p].next) {
x = E[p].b;
if (A[x][0] < 0) {
if (A[x][1] >= j) {
tmp = G[x][A[x][1]] - G[x][j - 1]; if (tmp < 0) tmp += MOD;
F[i][j] = F[i][j] * tmp % MOD;
} else {F[i][j] = 0; break;}
} else {
if (A[x][0] <= j) {
tmp = G[x][j] - G[x][A[x][0] - 1]; if (tmp < 0) tmp += MOD;
F[i][j] = F[i][j] * tmp % MOD;
} else {F[i][j] = 0; break;}
}
}
G[i][j] = (G[i][j - 1] + F[i][j]) % MOD;
}
res = 1;
re1(i, n) if (A[i][0] > 0 && A[i][1] > 0) {
tmp = G[i][A[i][1]] - G[i][A[i][0] - 1]; if (tmp < 0) tmp += MOD;
res = res * tmp % MOD;
}
}
void pri()
{
cout << res << endl;
}
int main()
{
init();
solve();
pri();
return 0;
}