发现了一道巨神无比的递推题

Posted on 2012-03-12 23:30 Mato_No1 阅读(486) 评论(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] = 0break;}
            } 
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] = 0break;}
            }
        }
        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;
}

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理