题目链接:http://codeforces.com/gym/100202/attachments/download/1698/20032004-winter-petrozavodsk-camp-andrew-stankevich-contest-6-en.pdf

题目大意:

给你一个数r

求在0~r-1中选一个子集,使得:

1,其中任何一个元素带入到多项式mod r的结果都在集合内

2,任何一个元素都是集合内某个元素带入多项式mod r的结果

现在这个子集要同时满足给定的两个多项式p和q

那么求有多少种选法

注意:空也是个选法

=============

样例解释:

有两个集合同时满足两个条件

一个是空

一个是{0,2,4}

0 * 2 + 0 = 0

2 * 2 + 0 = 4

4 * 2 + 0 = 2

第一个多项式满足

0 * 1 + 2 = 2

2 * 1 + 2 = 4

4 * 1 + 2 = 0

第二个多项式满足

PS:

{0,1,2,3,4,5}满足第二个多项式却不满足第一个

这一题我写了两个代码,一个是错的,一个是对的..

错误代码的思想在于,你选了某个数X,一定要选他的next[X],next[next[X]].....

所以把所有的团看成一组,如果有的团有后继那么这个团无效

答案是2^团的个数

可惜这个算法是错的,有反例如下:

4

1 0 1

1 1 1

按照规定,只有空集满足

但是按照算法,{0,1,2,3}也满足,因为next[0]= 1或1 next[1]= 1或2 next[2]=1或3 next[3]=1或0

这样看来都满足

错误代码如下:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#include<math.h>
#include<memory>
#include<vector>
#include<bitset>
#include<fstream>
#include<stdio.h>
#include<utility>
#include<sstream>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
bitset<128> need[105];
int a[105];
bool visit[105];
int sum=0;
int r;
void dfs(int x)
{
    if (visit[x]) return;
    visit[x]=true;
    int i;
    for (i=0;i<r;i++)
    {
        if (need[x][i])
        {
            if (need[x]!=need[i]) break;
        }
    }
    if (i==r)
    {
        sum++;
        for (i=0;i<r;i++)
        {
            if (need[x][i]) visit[i]=true;
        }
    } 
}
int c[1005];
int main()
{
    freopen("stable.in","r",stdin);
    freopen("stable.out","w",stdout);
    scanf("%d",&r);
    int i;
    int n;
    scanf("%d",&n);
    for (i=0;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    for (i=0;i<r;i++)
    {
        need[i][i]=true;
        int sum=0;
        int j;
        for (j=0;j<=n;j++)
        {
            sum*=i;
            sum+=a[j];
            sum%=r;
        }
        need[i][sum]=true;
    }
    scanf("%d",&n);
    for (i=0;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    for (i=0;i<r;i++)
    {
        int sum=0;
        int j;
        for (j=0;j<=n;j++)
        {
            sum*=i;
            sum+=a[j];
            sum%=r;
        }
        need[i][sum]=true;
    }
    int k;
    for (k=0;k<r;k++)
    {
        int j;
        for (i=0;i<r;i++)
        {
            for (j=0;j<r;j++)
            {
                if ((need[i][k])&&(need[k][j])) need[i][j]=true;
            }
        }
    }
    for (i=0;i<r;i++)
    {
        if (!visit[i]) dfs(i);
    }
    c[0]=1;
    for (i=0;i<sum;i++)
    {
        int j;
        for (j=0;j<1000;j++)
        {
            c[j]*=2;
        }
        for (j=0;j<1000;j++)
        {
            c[j+1]+=c[j]/10;
            c[j]%=10;
        }
    }
    for (i=999;i>0;i--)
    {
        if (c[i]!=0) break;
    }
    for (;i>=0;i--)
    {
        printf("%d",c[i]);
    }
    printf("\n");
    return 0;
}

正确的思路是这样的

找环,然后环内的并查集到一起

不合法的(永远走不到自己)并查集到一个"错误集合",统计答案的时候无视掉这个集合

求2^集合数量即可

代码如下:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#include<math.h>
#include<memory>
#include<vector>
#include<bitset>
#include<fstream>
#include<stdio.h>
#include<utility>
#include<sstream>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int a[105];
int next1[105],next2[105];
bool visit[105];
int sum=0;
int r;
int c[1005];
int father[105];
int size[105];
int findroot(int x)
{
    int root;
    for (root=x;father[root]!=-1;root=father[root]) ;
    int temp;
    for (;father[x]!=-1;)
    {
        temp=father[x];
        father[x]=root;
        x=temp;
    }
    return root;
}
void u(int x,int y)
{
    x=findroot(x);
    y=findroot(y);
    if (x==y) return;
    if (size[x]>size[y]) swap(x,y);
    father[x]=y;
    size[y]+=size[x];
}
int main()
{
    freopen("stable.in","r",stdin);
    freopen("stable.out","w",stdout);
    scanf("%d",&r);
    int i;
    int n;
    scanf("%d",&n);
    for (i=0;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    memset(visit,0,sizeof(visit));
    for (i=0;i<r;i++)
    {
        int sum=0;
        int j;
        for (j=0;j<=n;j++)
        {
            sum*=i;
            sum+=a[j];
            sum%=r;
        }
        next1[i]=sum;
    }
    father[r]=-1;
    size[r]=1000;
    scanf("%d",&n);
    for (i=0;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    for (i=0;i<r;i++)
    {
        int sum=0;
        int j;
        for (j=0;j<=n;j++)
        {
            sum*=i;
            sum+=a[j];
            sum%=r;
        }
        next2[i]=sum;
    }
    memset(father,-1,sizeof(father));
    for (i=0;i<r;i++)
    {
        size[i]=1;
    }
    for (i=0;i<r;i++)
    {
        int now=i;
        for (;;)
        {
            if (visit[now]) break;
            visit[now]=true;
            now=next1[now];
        }
        if (now!=i)
        {
            u(i,r);
            memset(visit,0,sizeof(visit));
            continue;
        }
        for (;;)
        {
            if (visit[now]==0) break;
            visit[now]=false;
            u(now,next1[now]);
            now=next1[now];
        }
    }
    for (i=0;i<r;i++)
    {
        int now=i;
        for (;;)
        {
            if (visit[now]) break;
            visit[now]=true;
            now=next2[now];
        }
        if (now!=i)
        {
            u(i,r);
            memset(visit,0,sizeof(visit));
            continue;
        }
        for (;;)
        {
            if (visit[now]==0) break;
            visit[now]=false;
            u(now,next2[now]);
            now=next2[now];
        }
    }
    for (i=0;i<r;i++)
    {
        if (father[i]==-1) sum++;
    }
    c[0]=1;
    for (i=0;i<sum;i++)
    {
        int j;
        for (j=0;j<1000;j++)
        {
            c[j]*=2;
        }
        for (j=0;j<1000;j++)
        {
            c[j+1]+=c[j]/10;
            c[j]%=10;
        }
    }
    for (i=999;i>0;i--)
    {
        if (c[i]!=0) break;
    }
    for (;i>=0;i--)
    {
        printf("%d",c[i]);
    }
    printf("\n");
    return 0;
}