UOJ Logo Universal Online Judge

UOJ

#427. 【集训队作业2018】化学竞赛

统计

现有$n-1$种化学物质,他们全部溶于水。任取$n-1$种化学物质中的两种都可以在一定条件下发生化学反应(两种可以相同)。特别地,水和其他化学物质不会化学反应,但是我们为了统一考虑,我们认为水可以和任意一种化学物质$X$反应生成$X$。那么包含水我们一共有$n$种化学物质。

根据相关理论,由于产物不离开溶液反应体系,化学药品之间反应的产物与加入药品的顺序无关。另外,每种化学物质都有恰好一种对应的化学物质,它们两个反应生成水。

现在桌子上有一排药瓶,每一个药瓶中存放了一种化学物质,编号从左到右分别为$1,2,\cdots,m$。为了体现您的超强实验功底,您的第$i$次实验仅用编号在区间$[L_i,R_i]$中的药瓶。假设您能创造出任何可能的反应条件,请问第$i$次实验您总共能配出多少种不同的物质(包含一开始就有的物质)?

输入格式

第一行三个正整数$t,m,q$,分别表示第二行正整数个数、桌子上化学药品的数量、您做实验的次数;

第二行为用于描述这些化学药品性质的$t$个正整数;

接下来一行$m$个$[1,n]$内的正整数,第$i$个整数表示编号为$i$的药品是第几种化学物质;

接下来$q$行,每行两个正整数$L_i,R_i$,表示第$i$次实验中您能使用的药品编号区间。

输出格式

恰好$q$行,每行一个$[1,n]$内的正整数,表示第$i$次实验您在理论上能配出的不同的物质种类数。

样例一

input

1 5 3
4
1 3 2 2 4
2 4
1 2
1 1

output

4
2
1

辅助代码

推荐使用C++解决本题。

namespace LIB{
    const int N=30;
    int dim[N],dimcnt;
    template<class T>void dfs(int dep,T g,int x,int y,int z,int n){
        if(dep>dimcnt){
            g[x][y]=z;
            return;
        }
        int d=n/dim[dep];
        for(int i=0;i<n;i+=d){
            for(int j=0;j<n;j+=d){
                dfs(dep+1,g,x+i,y+j,z+(i+j)%n,d);
            }
        }
    }
    template<class T1,class T2>inline int put_reaction(int t,T1 a,T2 g){
        dimcnt=t;
        int n=1;
        for(int i=1;i<=t;i++){
            n*=dim[i]=a[i];
        }
        dfs(1,g,1,1,1,n);
        return n;
    }
}

将以上代码包含在您的源程序内之后,您可以调用这个时间复杂度为$\mathrm O(n^2)$的函数来处理输入数据的前两行:

int LIB::put_reaction(t,a,g);
  • 第一个参数是输入第一行的整数$t$;
  • 第二个参数是一个int数组,里面从下标$1$开始存放着输入数据第二行的$t$个数;
  • 第三个参数是一个int二维数组,函数执行完成之后,第i种物质和第j种物质反应的产物的是第g[i][j]种物质;
  • 该函数返回一个int,表示【题目描述】中的$n$。

程序能根据描述化学药品性质的$t$个正整数生成一个二维int数组g。根据【题目描述】,该数组满足:

  • 第i种化学物质和第j种化学物质反应生成第g[i][j]种化学物质;
  • 产物与加入顺序无关,故g[i][j]==g[j][i]g[g[i][j]][k]==g[i][g[j][k]]成立;
  • $n$种物质中恰有一种是水,保证其反应性质满足题目中的描述;
  • 二维数组g的每一行、每一列都恰有一个是水。

参考用法:

#include <cstdio>
namespace LIB{ /* ... */ }
const int N=3010;
int a[N],b[N][N];
int main(){
    int t,m,q;
    scanf("%d%d%d",&t,&m,&q);
    for(int i=1;i<=t;i++){
        scanf("%d",a+i);
    }
    int n=LIB::put_reaction(t,a,b);
    /* ... */
    return 0;
}

限制与约定

对于所有数据:

  • $n\leq3000,m,q\leq10^6$;
  • $\forall i,1\leq L_i\leq R_i\leq m$;
  • $\forall i,a_i\neq 1$。
测试点编号特殊约定
$1$$n,m,q\leq100$
$2,3$$m,q\leq4000$
$4,5$$\min(m,q)\leq4000$
$6$$n$为素数
$7$$n$为若干不同质数乘积
$8$$g[i][j]=((i-1) xor (j-1))+1$
$9,10,11,12,13,14,15,16,17,18,19,20$

时间限制:$\texttt{2s}$

空间限制:$\texttt{512MB}$

下载

样例数据下载