题目链接:http://poj.org/problem?id=2065
题目大意:
f(k)=∑0<=i<=n-1aiki
0 <= f (k) <= 26 ('*'=0,'a'=1,'b'=2...'z'=26) for 1 <= k <= n
给出f(1...n),求a[],(k从1~n循环使用).
题目思路:
代码:
#include <stdlib.h> #include <string.h> #include <stdio.h> #include <ctype.h> #include <math.h> #include <time.h> #include <stack> #include <queue> #include <map> #include <set> #include <vector> #include <string> #include <iostream> #include <algorithm> using namespace std; #define ull unsigned __int64 #define ll __int64 //#define ll long long #define ls rt<<1 #define rs ls|1 #define lson l,mid,ls #define rson mid+1,r,rs #define middle l+r>>1 #define INF 0x3F3F3F3F #define esp (1e-10) #define MOD 1000000007 #define type int typedef pair<int,int> pii; typedef multiset<int> mset; typedef multiset<int>::iterator mst_it; //const double pi=acos(-1.0); const int M=70 +5; #define clr(x,c) memset(x,c,sizeof(x)) type min(type x,type y){return x<y? x:y;} type max(type x,type y){return x>y? x:y;} void swap(type& x,type& y){type t=x;x=y;y=t;} int T,cas=0; int n,m,p; int a[M][M],x[M],free_x[M]; char str[M]; map<char,int>mp; int gcd(int a,int b){ if(a>b) swap(a,b); while(b){int t=b;b=a%b,a=t;} return a; } int lcm(int a,int b){ return a/gcd(a,b)*b; } int gauss(int equ,int var){ int i,j,k,col; clr(free_x,0); for(k=col=0;k<equ && col<var;k++,col++){ int max_r=k; for(i=k+1;i<equ;i++) if(abs(a[i][col])>abs(a[max_r][col])) max_r=i; if(max_r!=k) for(j=col;j<var+1;j++) swap(a[k][j],a[max_r][j]); if(!a[k][col]){k--;free_x[col]=1;continue;} for(i=k+1;i<equ;i++) if(a[i][col]){ int LCM=lcm(abs(a[i][col]),abs(a[k][col])); int ti=LCM/abs(a[i][col]); int tk=LCM/abs(a[k][col]); if(a[i][col]*a[k][col]<0) tk=-tk; for(j=col;j<var+1;j++) a[i][j]=((ti*a[i][j]-tk*a[k][j])%p+p)%p; } } for(i=k;i<equ;i++) if(a[i][var]) return -1; if(k<var) return var-k; for(i=k-1;i>=0;i--){ int tmp=a[i][var]; for(j=i+1;j<var;j++) if(a[i][j]){ tmp-=a[i][j]*x[j]; tmp=((tmp%p)+p)%p; } while(tmp%a[i][i]) tmp+=p; x[i]=(tmp/a[i][i])%p; } return 0; } void preSof(){ mp['*']=0; for(char c='a';c<='z';c++) mp[c]=c-'a'+1; return; } void run(){ int i,j,k,ki; clr(a,0); scanf("%d%s",&p,str); n=strlen(str); for(i=0,k=1;i<n;i++,k++){ a[i][n]=mp[str[i]]; for(j=0,ki=1;j<n;j++,ki=(ki*k)%p) a[i][j]=ki; } gauss(n,n); for(i=0;i<n;i++) printf("%d%c",x[i],i==n-1? '\n':' '); } int main(){ //freopen("1.in","r",stdin); //freopen("1.out","w",stdout); preSof(); //run(); //while(~scanf("%d%d",&n,&m) && (n||m)) run(); for(scanf("%d",&T),cas=1;cas<=T;cas++) run(); //system("pause"); return 0; }