Codeforces

Luogu

分析

不难想到 DP。设 $dp_{i,a_1,a_2,\cdots}$ 表示前 $i$ 个字符，字符 $c_j$ 的出现次数模 $m_j$ 等于 $a_j$ 时的方案数。转移枚举在后面填的字符即可。

因为 $\prod m_i\leq 123$，所以后面的状态至多只有 $123$ 种，因此直接矩阵快速幂即可。

实现时需要把后面的状态压成一个数。我的做法是压成 $\Big(\big((a_1m_1)+a_2\big)m_2+a_3\Big)m_3$ 的样子。构造转移矩阵和算答案时可以直接把所有状态搜出来。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

char getc() {
    char c=getchar();
    while (c<'A'||c>'Z') c=getchar();
    return c;
}
ll read() {
    ll X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=123+10,M=1000+10;
const int mod=12345;

ll n; int m,r=1,vis[256];
struct node { char c; int k; } a[M];

struct Matrix {
    int s[N][N];
    Matrix() { memset(s,0,sizeof(s)); }
    int* operator [](int i) { return s[i]; }
} A,Q;
Matrix operator *(Matrix a,Matrix b) {
    Matrix c;
    for (int i=0;i<r;++i)
        for (int j=0;j<r;++j)
            for (int k=0;k<r;++k)
                c[i][j]=(c[i][j]+1ll*a[i][k]*b[k][j])%mod;
    return c;
}
Matrix qpow(Matrix a,ll b) {
    Matrix c=a; --b;
    for (;b;b>>=1,a=a*a) if (b&1) c=c*a;
    return c;
}

void dfs1(int p,char c,int u,int v) {
    if (p>m) { ++Q[u][v]; return; }
    for (int i=0;i<a[p].k;++i)
        dfs1(p+1,c,u*a[p].k+i,v*a[p].k+(i+(a[p].c==c))%a[p].k);
}
int ok[256],ans=0;
void dfs2(int p,int S) {
    if (p>m) {
        int flag=1;
        for (char i='A';i<='Z';++i)
            if (vis[i]&&!ok[i]) { flag=0; break; }
        if (flag) ans=(ans+A[0][S])%mod;
        return;
    }
    int o=ok[a[p].c];
    for (int i=1;i<a[p].k;++i) dfs2(p+1,S*a[p].k+i);
    ok[a[p].c]=1,dfs2(p+1,S*a[p].k);
    ok[a[p].c]=o;
}

int main() {
    n=read(),m=read();
    if (n==0) { puts("1"); return 0; }
    for (int i=1;i<=m;++i) vis[a[i].c=getc()]=1,r*=(a[i].k=read());
    for (char i='A';i<='Z';++i) if (vis[i]) dfs1(1,i,0,0);
    A[0][0]=1; A=A*qpow(Q,n);
    dfs2(1,0); printf("%d\n",ans);
    return 0;
}