相关链接
题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=4623
神犇题解:http://blog.csdn.net/keshuai19940722/article/details/49455357
解题报告
脑袋里一直想着去年$ZJOI$的小星星
然后就各种优化,最后还是$T$成狗 QwQ
然后正解就是把每个数按照因数种类不同分组
最后搞下来只有$14$种不同的,然后暴力状压$DP$就可以了
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 3000000; const int M = 16; int n,mx,MX,MOD,f[N][M],cnt[M],bit[M],cur[M],sym[M],suf[M],leg[M][M]; int ty[]={0,1,2,3,2,4,5,6,2,3,7,8,5,9,10,11,2,1,5,1,7,12,13,1,5,4,14,3,10}; inline int read() { char c=getchar(); int f=1,ret=0; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret * f; } int gcd(int a, int b) { return b? gcd(b, a%b): a; } inline void decode(int w, int *arr) { for (int i=mx;i;i--) { arr[i] = w % bit[i]; w /= bit[i]; } } inline int solve() { memset(cnt,0,sizeof(cnt)); mx = MX = 0; for (int i=1;i<=n;i++) { cnt[ty[i]]++; mx = max(mx, ty[i]); } for (int i=1;i<=mx;i++) { bit[i] = cnt[i] + 1; MX = MX * bit[i] + cnt[i]; } suf[mx] = 1; for (int i=mx-1;i;i--) { suf[i] = suf[i+1] * bit[i+1]; } memset(f,0,sizeof(f)); f[0][0] = 1; for (int i=0;i<MX;i++) { decode(i, cur); for (int j=0;j<=mx;j++) { if (!f[i][j]) continue; for (int k=1;k<=mx;k++) { if ((leg[k][j] || !j) && cur[k] < cnt[k]) { int to = i + suf[k]; f[to][k] = (f[to][k] + (LL)f[i][j] * (cnt[k] - cur[k])) % MOD; } } } } int ret = 0; for (int i=1;i<=mx;i++) { ret = (ret + f[MX][i]) % MOD; } return ret; } int main() { for (int i=1;i<=28;i++) { if (sym[ty[i]]) continue; sym[ty[i]] = i; } for (int i=1;i<=14;i++) { for (int j=1;j<=14;j++) { if (gcd(sym[i], sym[j]) == 1) { leg[i][j] = 1; } } } for (int T=read();T;T--) { n = read(); MOD = read(); printf("%d\n",solve()); } return 0; }
433313 3444[…]the time to read or visit the content material or sites we have linked to below the[…] 223239
499123 886493This is the sort of details Ive long been in search of. Thanks for posting this details. 54748
55632 937196Wow, incredible blog format! How lengthy have you been blogging for? you make running a blog glance simple. The full glance of your web site is great, as smartly the content material material! 323661
104955 22427My spouse and I stumbled more than here from a different website and thought I may as nicely check things out. I like what I see so now im following you. Appear forward to going over your internet page repeatedly. 977546
981232 632516I need to admit that that is one wonderful insight. It surely gives a company the opportunity to have in around the ground floor and genuinely take part in generating a thing particular and tailored to their needs. 823735
505108 139801Hey, you?re the goto expert. Thanks for haingng out here. 419460
214452 415211I love the appear of your internet site. I lately built mine and I was looking for some style ideas and you gave me several. May possibly I ask you whether you developed the internet site by youself? 172575
480327 356441forty men and women that function with all the services Oasis provides, and he is really a extremely busy man, he 180833
498063 36840Merely wanna input on few general items, The site style is perfect, the subject material is rattling superb : D. 466633
377590 144628You really need to experience a tournament for starters of the finest blogs online. Let me recommend this excellent website! 137499
568390 824021I truly treasure your piece of function, Excellent post. CHECK ME OUT BY CLICKING MY NAME!!! 920444
640562 715435This web internet site is truly a walk-through for all of the information you wanted about this and didnt know who to ask. Glimpse here, and you will definitely discover it. 331187
958967 917498Hi my loved 1! I wish to say that this post is wonderful, excellent written and come with almost all critical infos. I would like to see far more posts like this . 502348
Keep up the wonderful piece of work, I read few content on this website and I believe that your blog is very interesting and contains bands of good info .
I think that is one of the most significant information for me. And i’m satisfied reading your article. However want to commentary on some common issues, The website style is great, the articles is truly nice : D. Good process, cheers