一直不在状态……
想着各种事情……
A.
正常的方法是预处理k!和inv(k!)，然后每次询问O(1)。
然后某同学的方法是dp，O(n*m)也能过。
f(i,j,0)和f(i,j,1)吗？i<=n,j<=m,0和1分别代表是否已经选择F吗。
B.
对于a，是x的倍数，且不是y的倍数(其中p%x==0,y%x==0,p%y==0)
x乘上某个数，这个数除以z(z为不可以使用的约数的乘积，详见代码)为r（计算0~z-1）。
则对于b，是(p/x)的倍数
不好写。。。
时间复杂度：
预处理：k个质因数(<=6)，2^k * 对应的大小(<=p)
约数的个数*(k+k)
还有更快的方法
题解：数论方式分析。
a=px+y
y*b=p的倍数
则b是p/y的倍数。
然后枚举y。
写得很快。。。
看群里还有使用mobius的，比赛时想过，但没想到。
对于数字a,b
gcd(a,p)=d
然后b为p/d的倍数即可。
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cmath> 4 #include <cstring> 5 #include <string> 6 #include <algorithm> 7 #include <iostream> 8 using namespace std; 9 #define ll long long 10 11 const double eps=1e-8; 12 const ll inf=1e9; 13 const ll mod=1e9+7; 14 const int maxn=1e5+10; 15 16 ///2,3,5,7,11,13 17 18 struct node 19 { 20 ll g; 21 ///large to small 22 ll a[10],b[10]; 23 }f[maxn]; 24 25 ll zhi[maxn],zhi_cnt,maxv=1e5; 26 ll x[300],gx[300],y[130][maxn]; 27 bool vis[maxn],use[maxn]; 28 ll p; 29 30 ///10^5*64 31 void dfs(ll i,ll j,ll k) 32 { 33 if (k==f[p].g+1) 34 { 35 ll l,z; 36 y[j][0]=0; 37 x[j]=i; 38 z=f[p].g; 39 for (l=1;l<=i;l++) 40 { 41 for (k=1;k<=z;k++) 42 if (l%zhi[f[p].a[k]]==0 && use[k]) 43 break; 44 if (k==z+1) 45 y[j][l]=y[j][l-1]+1; 46 else 47 y[j][l]=y[j][l-1]; 48 } 49 gx[j]=y[j][i]; 50 return; 51 } 52 use[k]=0; 53 dfs(i,j*2,k+1); 54 use[k]=1; 55 dfs(i*zhi[f[p].a[k]],j*2+1,k+1); 56 } 57 58 ll work(ll u,ll v) 59 { 60 ll r=0,i,j; 61 v/=u; 62 63 i=1,j=1; 64 while (i<=f[u].g && j<=f[p].g) 65 { 66 if (f[u].a[i]==f[p].a[j]) 67 { 68 if (f[u].b[i]==f[p].b[j]) 69 r=r*2; 70 else 71 r=r*2+1; 72 i++; 73 j++; 74 } 75 else if (f[u].a[i]>f[p].a[j]) 76 i++; 77 else 78 { 79 j++; 80 r=r*2+1; 81 } 82 } 83 while (j<=f[p].g) 84 r=r*2+1,j++; 85 86 return v/x[r]*gx[r]+y[r][v%x[r]]; 87 } 88 89 int main() 90 { 91 ll t,i,j,k,maxv=1e5; 92 ll n,m,sum; 93 for (i=2;i<=maxv;i++) 94 { 95 if (!vis[i]) 96 { 97 zhi[++zhi_cnt]=i; 98 f[i].g=1; 99 f[i].a[1]=zhi_cnt; 100 f[i].b[1]=1; 101 } 102 for (j=1;j<=zhi_cnt;j++) 103 { 104 k=i*zhi[j]; 105 if (k>maxv) 106 break; 107 vis[k]=1; 108 f[k]=f[i]; 109 if (f[i].a[f[i].g]==j) 110 f[k].b[f[k].g]++; 111 else 112 { 113 f[k].g++; 114 f[k].a[f[k].g]=j; 115 f[k].b[f[k].g]=1; 116 } 117 if (i%zhi[j]==0) 118 break; 119 } 120 } 121 122 scanf("%lld",&t); 123 while (t--) 124 { 125 scanf("%lld%lld%lld",&n,&m,&p); 126 // if (p==1) 127 // { 128 // printf("%lld ",n*m); 129 // continue; 130 // } 131 dfs(1,0,1); 132 133 sum=0; 134 for (i=1;i<=p;i++) 135 if (p%i==0) 136 { 137 j=p/i; 138 139 sum+=work(i,n)*(m/j); 140 } 141 printf("%lld ",sum); 142 } 143 return 0; 144 } 145 /* 146 5 147 1000000000 1000000000 1 148 1000000000 1000000000 2 149 1000000000 1000000000 10 150 100000000 100000000 2 151 10 20 15 152 1000000000 1000000000 30030 153 100000000 100000000 30030 154 155 1 156 9 9 9 157 1 158 6 6 12 159 160 1 161 20 20 11 162 163 1 164 10 10 6 165 */
场上感觉，然后看了题解，以下想法基本是错的……
C.
a1,b1,c1
a2,b2,c2
要求
a1<b2<c1
a2<b1<c2
有可能要按照某种方式排序
两组条件，两者互相约束。
然后就不会做了……
题解：
取反求，变成i能赢j的条件，此时的条件可求。
然后就是偏序的子问题。
不同数组元素的比较，其实还是比较，二维偏序。
cj<bi bj<ai
改为
c,b；b,a数组 为 同一个数组(表示的符号相同)表示即可。
D.
一开始以为是图，觉得不可做，
后面发现是树。。。
点分治
结合题解想了一想，也许可以？？？
也许可以分为内部处理的 和 通过子根相连的
处理^k（k<=13）
各种多项式操作。 （题解：二项式定理）
看群里说对于k较小的情况，有更好的做法，cf的某些题？？？
题解：树形DP。
树本身的结构已经提供了层次感？？？
lca为当前根。
未证实正确的想法：
E.
末尾有0的操作。
只可能为
a->b->c->b->c
b->c->b->c
处理每个区间的最小/最大值
每次a->b时进行修改，
提前记录，也许要额外建一棵树，
数目不多。
题解的方法，特别是最后一部分没看懂。。。
F.
跟E一样，怎么都是各种修改。
没想法，估计较难。