网站建设预算项目,wordpress更新缓存的插件,如何查网站是否备案,怎么用2013做网站摔电脑摔电脑#xff01;JZP业界毒瘤#xff01; 400题纪念~哇终于上400了的说#xff01;#xff01;#xff01;好不容易欸#xff01; 题解什么的还是Orz iwtwiioi 我求组合数的方法明明是O(n)的#xff0c;为什么这么慢#xff01;#xff01;#xff01;令人报警…摔电脑摔电脑JZP业界毒瘤 400题纪念~哇终于上400了的说好不容易欸 题解什么的还是Orz iwtwiioi 我求组合数的方法明明是O(n)的为什么这么慢令人报警 喂话说这题的重点不在求组合数上面吧。。。 1 /**************************************************************2 Problem: 34343 User: rausen4 Language: C5 Result: Accepted6 Time:6888 ms7 Memory:140824 kb8 ****************************************************************/9 10 #include cstdio11 #include cstring12 #include algorithm13 14 using namespace std;15 const int N 100005;16 const int mod 10007;17 const int Tt 1005;18 19 int g[21][N], f[21][15][N];20 int a[15], p[N], cnt, u[N], mx, mn;21 int n[Tt], c[Tt], m[Tt][15];22 int C[N][20];23 int ans;24 bool vis[N];25 26 inline int read() {27 int x 0, sgn 1;28 char ch getchar();29 while (ch 0 || 9 ch) {30 if (ch -) sgn -1;31 ch getchar();32 }33 while (0 ch ch 9) {34 x x * 10 ch - 0;35 ch getchar();36 }37 return sgn * x;38 }39 40 int pow(int x, int y) {41 int res 1;42 while (y) {43 if (y 1) (res * x) % mod;44 (x * x) % mod;45 y 1;46 }47 return res;48 }49 50 void get_f(int N) {51 int i, j, k, l;52 for (u[1] 1, i 2; i N; i) {53 if (!vis[i])54 p[cnt] i, u[i] -1;55 for (j 1; j cnt; j) {56 if ((k i * p[j]) N) break;57 vis[k] 1;58 if (i % p[j] 0) {59 u[k] 0;60 break;61 }62 u[k] -u[i];63 }64 }65 for (C[0][0] i 1; i N; i)66 for (C[i][0] j 1; j 19; j)67 C[i][j] (C[i - 1][j - 1] C[i - 1][j]) % mod;68 69 for (l 2; l 20; l)70 for (i 1; i N; i)71 for (j i, k 1; j N; j i, k)72 (g[l][j] C[i - 1][l - 2] * u[k]) % mod;73 for (i 1; i N; i)74 for (l 2; l 20; l) {75 k 1;76 for (j 1; j 12; j) {77 f[l][j][i] (f[l][j][i - 1] k * g[l][i]) % mod;78 (k * i) % mod;79 }80 }81 }82 83 void calc(int i, int x) {84 memset(a, 0, sizeof(a));85 a[1] 1;86 int d1, d2, t, j, k;87 for (k 1; k n[i]; k) {88 t m[i][k] / x;89 d1 (1ll * t * m[i][k]) % mod;90 d2 (1ll * t * (t 1) 1) % mod;91 for (j n[i] 1; j 1; --j)92 a[j] (a[j] * d1 - a[j - 1] * d2) % mod;93 (a[1] * d1) % mod;94 }95 }96 97 int main() {98 int i, j, k, l, T;99 T read();
100 for (i 1; i T; i) {
101 n[i] read(), c[i] read();
102 for (j 1; j n[i]; j)
103 m[i][j] read(), mx max(mx, m[i][j]);
104 }
105 get_f(mx);
106
107 for (i 1; i T; i) {
108 ans 0;
109 for (mn m[i][1], j 2; j n[i]; j)
110 mn min(mn, m[i][j]);
111 for (j 1; j mn; j k 1) {
112 k mn 1;
113 for (l 1; l n[i]; l)
114 k min(k, m[i][l] / (m[i][l] / j));
115 calc(i, j);
116 for (l 1; l n[i] 1; l)
117 (ans a[l] * (f[c[i]][l][k] - f[c[i]][l][j - 1])) % mod;
118 }
119 ans % mod;
120 printf(%d\n, (ans mod) % mod);
121 }
122 return 0;
123 } View Code(递推求组合数) 1 /**************************************************************2 Problem: 34343 User: rausen4 Language: C5 Result: Accepted6 Time:9596 ms7 Memory:134184 kb8 ****************************************************************/9 10 #include cstdio11 #include cstring12 #include algorithm13 14 using namespace std;15 const int N 100005;16 const int mod 10007;17 const int Tt 1005;18 19 int g[21][N], f[21][15][N];20 int a[15], p[N], cnt, u[N], mx, mn;21 int n[Tt], c[Tt], m[Tt][15];22 int fac[N], faci[N], sum[N];23 int ans;24 bool vis[N];25 26 inline int read() {27 int x 0, sgn 1;28 char ch getchar();29 while (ch 0 || 9 ch) {30 if (ch -) sgn -1;31 ch getchar();32 }33 while (0 ch ch 9) {34 x x * 10 ch - 0;35 ch getchar();36 }37 return sgn * x;38 }39 40 int pow(int x, int y) {41 int res 1;42 while (y) {43 if (y 1) (res * x) % mod;44 (x * x) % mod;45 y 1;46 }47 return res;48 }49 50 inline int C(int x, int y) {51 if (y 0) return 1;52 if (x y) return 0;53 if (sum[x] ! sum[y] sum[x - y]) return 0;54 return fac[x] * faci[y] % mod * faci[x - y] % mod;55 }56 57 void get_f(int N) {58 int i, j, k, l;59 for (u[1] 1, i 2; i N; i) {60 if (!vis[i])61 p[cnt] i, u[i] -1;62 for (j 1; j cnt; j) {63 if ((k i * p[j]) N) break;64 vis[k] 1;65 if (i % p[j] 0) {66 u[k] 0;67 break;68 }69 u[k] -u[i];70 }71 }72 fac[0] faci[0] 1;73 for (fac[1] 1, i 2; i N; i)74 if (i % mod 0) {75 sum[i] sum[i - 1] 1;76 fac[i] fac[i - 1] * (i / mod) % mod;77 } else {78 sum[i] sum[i - 1];79 fac[i] fac[i - 1] * i % mod;80 }81 for (faci[N] pow(fac[N], mod - 2),i N - 1; i; --i)82 if ((i 1) % mod 0)83 faci[i] faci[i 1] * ((i 1) / mod) % mod;84 else faci[i] faci[i 1] * (i 1) % mod;85 86 for (l 2; l 20; l)87 for (i 1; i N; i)88 for (j i, k 1; j N; j i, k)89 (g[l][j] C(i - 1, l - 2) * u[k]) % mod;90 for (i 1; i N; i)91 for (l 2; l 20; l) {92 k 1;93 for (j 1; j 12; j) {94 f[l][j][i] (f[l][j][i - 1] k * g[l][i]) % mod;95 (k * i) % mod;96 }97 }98 }99
100 void calc(int i, int x) {
101 memset(a, 0, sizeof(a));
102 a[1] 1;
103 int d1, d2, t, j, k;
104 for (k 1; k n[i]; k) {
105 t m[i][k] / x;
106 d1 (1ll * t * m[i][k]) % mod;
107 d2 (1ll * t * (t 1) 1) % mod;
108 for (j n[i] 1; j 1; --j)
109 a[j] (a[j] * d1 - a[j - 1] * d2) % mod;
110 (a[1] * d1) % mod;
111 }
112 }
113
114 int main() {
115 int i, j, k, l, T;
116 T read();
117 for (i 1; i T; i) {
118 n[i] read(), c[i] read();
119 for (j 1; j n[i]; j)
120 m[i][j] read(), mx max(mx, m[i][j]);
121 }
122 get_f(mx);
123
124 for (i 1; i T; i) {
125 ans 0;
126 for (mn m[i][1], j 2; j n[i]; j)
127 mn min(mn, m[i][j]);
128 for (j 1; j mn; j k 1) {
129 k mn 1;
130 for (l 1; l n[i]; l)
131 k min(k, m[i][l] / (m[i][l] / j));
132 calc(i, j);
133 for (l 1; l n[i] 1; l)
134 (ans a[l] * (f[c[i]][l][k] - f[c[i]][l][j - 1])) % mod;
135 }
136 ans % mod;
137 printf(%d\n, (ans mod) % mod);
138 }
139 return 0;
140 } View Code(奇怪的组合数求法) (p.s. 关于那种空间较小的求组合数的方法为什么慢了3秒我也是无言以对。。。)转载于:https://www.cnblogs.com/rausen/p/4294603.html
