题意:

给你n个数字,求某个多项式是否对于任何条件都是n的倍数..

非标准大乱搞解法:

随机10000个x..判定..

搞定..

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<fstream>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
int val[105];
char a[10005];
int rands()
{
    static int x=2011719;
    x=((x*19)+199903)%100000007;
    return x;
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int zu=0;
    for (;;)
    {
        memset(val,0,sizeof(val));
        scanf("%s",a);
        if (a[0]=='.') break;
        int i=1;
        int flag=1;
        if (a[i]=='-')
        {
            flag=-1;
            i++;
        }
        for (;;)
        {
            int x=1;
            sscanf(a+i,"%d",&x);
            x*=flag;
            for (;;)
            {
                if ((a[i]>'9')||(a[i]<'0')) break;
                i++;
            }
            int y=0;
            if (a[i]=='n')
            {
                y=1;
                i++;
                if (a[i]=='^')
                {
                    i++;
                    sscanf(a+i,"%d",&y);
                    for (;;)
                    {
                        if ((a[i]>'9')||(a[i]<'0')) break;
                        i++;
                    }
                }
            }
            val[y]+=x;
            if (a[i]==')')
            {
                i++;
                break;
            }
            else if (a[i]=='+')
            {
                flag=1;
                i++;
            }
            else
            {
                flag=-1;
                i++;
            }
        }
        int p;
        i++;
        sscanf(a+i,"%d",&p);
        printf("Case %d: ",zu+1);
        zu++;
        for (i=0;i<10000;i++)
        {
            int k=rands()%p;
            int j;
            int pows=1;
            int sum=0;
            for (j=0;j<=100;j++)
            {
                sum=(sum+(long long)pows*val[j])%p;
                pows=(long long)pows*k%p;
            }
            if (sum!=0)
            {
                printf("Not always an integer\n");
                break;
            }
        }
        if (i==10000)
        {
            printf("Always an integer\n");
        }
    }
    return 0;
}

(据说正解是差分一下..也就是说对于f(x+1)-f(x)判定是否是p的倍数,然后递归下去....)

正解-代码:

#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;
char a[10005];
int val[105];
int b[105];
int c[105][105];
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int zu=0;
    for (;;)
    {
        scanf("%s",a);
        if (a[0]=='.') return 0;
        int i=1;
        int flag=1;
        if (a[i]=='-')
        {
            flag=-1;
            i++;
        }
        memset(val,0,sizeof(val));
        for (;;)
        {
            int x=1;
            sscanf(a+i,"%d",&x);
            x*=flag;
            for (;;)
            {
                if (a[i]<'0') break;
                if (a[i]>'9') break;
                i++;
            }
            int y=0;
            if (a[i]=='n')
            {
                y=1;
                i++;
                if (a[i]=='^')
                {
                    i++;
                    sscanf(a+i,"%d",&y);
                    for (;;)
                    {
                        if (a[i]<'0') break;
                        if (a[i]>'9') break;
                        i++;
                    }
                }
            }
            val[y]+=x;
            if (a[i]=='+')
            {
                flag=1;
            }
            else if (a[i]=='-')
            {
                flag=-1;
            }
            else
            {
                break;
            }
            i++;
        }
        i++;
        i++;
        int p;
        sscanf(a+i,"%d",&p);
        zu++;
        printf("Case %d: ",zu);
        for (i=0;i<=100;i++)
        {
            int j;
            c[i][0]=1;
            for (j=1;j<=i;j++)
            {
                c[i][j]=((long long)c[i-1][j]+c[i-1][j-1])%p;
            }
        }
        for (i=0;i<=110;i++)
        {
            int j;
            if (val[0]%p!=0)
            {
                printf("Not always an integer\n");
                break;
            }
            memset(b,0,sizeof(b));
            for (j=0;j<=100;j++)
            {
                if (val[j]==0) continue;
                int k;
                for (k=0;k<j;k++)
                {
                    b[k]=(b[k]+(long long)val[j]*c[j][k])%p;
                }
            }
            memcpy(val,b,sizeof(val));
        }
        if (i>110)
        {
            printf("Always an integer\n");
        }
    }
    return 0;
}