割と力技。
https://yukicoder.me/problems/no/2136
問題
6面に1~9のうち6つの数字が1つずつ書かれたサイコロが、計N種ある。
これらのサイコロを振って出た計N個の数字を、任意の順でつなげて生成できる整数は何通りか。
解法
f(n) := n個目までのサイコロで出た目の多重集合
とする。f(N)がわかれば、集合の各要素について、数字の並び方を数えるのは容易である。
多重集合を以下のように表現する。
2進数表記で1が8つ含まれる、n+8桁の2進数を考える。
1の間や両端にある0の個数を、それぞれ多重集合における1~9の数としてエンコードすると、32bit整数で表現でき、割と高速に処理できる。
int N; const ll mo=998244353; const int NUM_=400001; static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1]; vector<int> M[21]; int add(int mask,int v) { int i; FOR(i,31) if(mask&(1<<i)) { if(v==0) { int a=mask&((1<<i)-1); return ((mask^a)<<1)^a; } v--; } assert(0); } void solve() { int i,j,k,l,r,x,y; string s; inv[1]=fact[0]=factr[0]=1; for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo; for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo; cin>>N; M[0].push_back((1<<9)-1); FOR(i,N) { int C[6]; FOR(j,6) { cin>>C[j]; C[j]--; } FORR(a,M[i]) { FOR(j,6) M[i+1].push_back(add(a,C[j])); } sort(ALL(M[i+1])); M[i+1].erase(unique(ALL(M[i+1])),M[i+1].end()); } ll ret=0; FORR(m,M[N]) { ll v=fact[N]; int cur=0; FOR(i,31) { if(m&(1<<i)) { v=v*factr[cur]%mo; cur=0; } else { cur++; } } ret+=v; } cout<<ret%mo<<endl; }
まとめ
考察自体はシンプルなので、★3.5とかでも良いかも。