开始的时候被范围吓尿了,敲完之后嫌范围小。。。
#pragma comment(linker, "/STACK:102400000,102400000") #include<iostream> #include<vector> #include<algorithm> #include<cstdio> #include<queue> #include<stack> #include<string> #include<map> #include<set> #include<cmath> #include<cassert> #include<cstring> #include<iomanip> using namespace std; #ifdef _WIN32 #define i64 __int64 #define out64 "%I64d\n" #define in64 "%I64d" #else #define i64 long long #define out64 "%lld\n" #define in64 "%lld" #endif /************ for topcoder by zz1215 *******************/ #define FOR(i,a,b) for( int i = (a) ; i <= (b) ; i ++) #define FF(i,a) for( int i = 0 ; i < (a) ; i ++) #define FFD(i,a,b) for( int i = (a) ; i >= (b) ; i --) #define S64(a) scanf(in64,&a) #define SS(a) scanf("%d",&a) #define LL(a) ((a)<<1) #define RR(a) (((a)<<1)+1) #define pb push_back #define pf push_front #define X first #define Y second #define CL(Q) while(!Q.empty())Q.pop() #define MM(name,what) memset(name,what,sizeof(name)) #define MC(a,b) memcpy(a,b,sizeof(b)) #define MAX(a,b) ((a)>(b)?(a):(b)) #define MIN(a,b) ((a)<(b)?(a):(b)) #define read freopen("in.txt","r",stdin) #define write freopen("out.txt","w",stdout) const int inf = 0x3f3f3f3f; const i64 inf64 = 0x3f3f3f3f3f3f3f3fLL; const double oo = 10e9; const double eps = 10e-9; const double pi = acos(-1.0); const int maxc = 26; const int maxz = 125; const int mod = 12345; int use; struct Matrix { int a[maxz][maxz]; Matrix () { MM(a,0); } void operator *= (const Matrix &y) { Matrix x; for(int i=0;i<use;i++) { for(int j=0;j<use;j++) { for(int k=0;k<use;k++) { x.a[i][j]+=a[i][k]*y.a[k][j]; x.a[i][j]%=mod; } } } MC(a,x.a); return ; } Matrix pow(i64 n) { Matrix x,y; MC(y.a,a); for(int i=0;i<use;i++) x.a[i][i] = 1; while(n) { if(n%2==1) { x*=y; } y*=y; n/=2; } return x; } }; i64 n; int c; vector<int>v[maxc+1]; int dp[maxz][maxz]; int f[maxc+1]; int s[maxc+1]; bool hash[maxc+1]; bool can[maxc+1][maxz]; bool yes(int x) { for(int i=1;i<=maxc;i++) { if(hash[i]) { int now = x%f[i]; if(!can[i][now]) return false; x/=f[i]; } } return true; } int start() { Matrix ax,bx; MM(dp,0); int to,temp; for(int now=0;now<use;now++) { for(int i=1;i<=maxc;i++) { if(hash[i]) { temp = now / s[i-1]; temp %= f[i]; to = now - temp*s[i-1]; temp = (temp+1)%f[i]; to += temp*s[i-1]; dp[to][now]++; } } } MC(ax.a,dp); bx = ax.pow(n); int ans = 0; for(int i=0;i<use;i++) { if(yes(i)) { ans+=bx.a[i][0]; ans%=mod; } } return ans; } int main() { while(cin>>n>>c) { char ch; int temp; MM(hash,false); MM(can,false); for(int i=0;i<=maxc;i++) { v[i].clear(); f[i]=1; } for(int i=1;i<=c;i++) { cin>>ch>>temp; v[ch-'A'+1].pb(temp); f[ch-'A'+1]*=temp; int now = 0; while(now<maxz) { can[ch-'A'+1][now] = true; now+=temp; } } use=1; for(int i=1;i<=maxc;i++) { if(!v[i].empty()) { use*=f[i]; hash[i]=true; } } s[0]=f[0]; for(int i=1;i<=maxc;i++) { s[i]=s[i-1]*f[i]; } cout<<start()<<endl; } return 0; }