吐槽诗（打油诗）

题面玄乎冗长，故事倒是挺好。 题解简单明了，尽显高深玄妙。 代码格式清晰，就是注释太少。 今天题目可订？你怕是在说笑！

yukikaze

#include<bits/stdc++.h> #define ll long long using namespace std; const int N = 5e5+5; char p[N]; int ans=0, lenp; inline char Cc(int a) {return char(a+'0');} inline int Ci(char a) {return a-'0';}//char和int的转换 int main() { scanf("%s", p+1); lenp = strlen(p+1); //输入 for(int i = 1; i <= lenp; i++) ans += Ci(p[i]); ans = 9-(ans%9); printf("%d\n", ans); //求删去的那个数 p[++lenp] = Cc(ans); ans = 0; for(int i = 1; i <= lenp; i++) { ans = ans*10+Ci(p[i]); p[i] = Cc(ans/9); ans %= 9; } //求x for(int i = 1; i <= lenp; i++) printf("%d", Ci(p[i])); puts("0"); //输出10x即s printf("0"); for(int i = 1; i <= lenp; i++) printf("%d", Ci(p[i])); //输出x即t return 0; }

tanikaze

shimakaze

#include <cstdio> #define ll long long; using namespace std; const ll mod = 1e9+7; const int N = 2e7+10; ll M(ll a){return a%mod;} int n, M; ll f[31][2], fac[N], inv[N], ans; ll pow(ll x,ll y){ ll c = 1; while(y){ if(y & 1) c = M( c*x ); b >>= 1; x = M( x*x ); } return c; } void prep() { fac[0] = 1; for(int i = 1; i <= n; i++) fac[i] = M( fac[i-1]*i ); inv[n] = pow(fac[n], mod-2); for(int i = n-1; i >= 1; i--) inv[i] = M( inv[i+1]*(i+1) ); }//处理阶乘及逆元 ll dfs(int left, int x, int y) { //left表示剩下的，还需要填多少数 ll tmpf[31][2]; for(int i = 0; i <= M; i++) for(int j = 0; j <= 1; j++) tmpf[i][j] = f[i][j]; ll tot = 0;//计算n中质因数数量至少x个的数 的数量 for(int i = x; i <= M; i++) for(int j = y; j <= 1; j++) tot += f[i][j], f[i][j] = 0; if (!x && !y){ for(int i = 0; i <= M; i++) for(int j = 0; j <= 1; j++) f[i][j] = tmpf[i][j]; return fac[tot]; }//边界 ll ans = 0; if (x) ans += dfs(left-tot, x-1, y);//gcd/2的情况 if (y) ans += dfs(left-tot, x, y-1);//gcd/3的情况 for(int i = 0; i <= M; i++) for(int j = 0; j <= 1; j++) f[i][j] = tmpf[i][j]; return M( M( fac[left-1]*inv[left-tot] ) * M( tot*ans ) ); //处理gcd不变的情况 //fac[left-1]*inv[left-tot] //等式转换一下，就是从left-tot+1乘到left-1,有tot个数填进去满足这个条件，就可以填1个，2个，3个…… } int main(){ scanf("%d", &n); prep(); f[0][0] = n; for(M = 1; f[M - 1][0]; M++) f[M][0] = f[M-1][0]>>1; M -= 2; //n可以分解出M+1个2 for(int i = 0; i <= M; i++) f[i][0] -= f[i+1][0];//减去重复，至少转换为恰好有 //（f[i][0]原先计算的是至少有i个2的数，减一减变成，恰好有i个2的数） f[0][1] = n / 3;//n中有0个2,1个3的数 for(int i = 1; i <= M-1; i++) f[i][1] = f[i-1][1]>>1; //n中有i个2,1个3的数，是n中有i-1个2,1个3的数除以2 for(int i = 0; i <= M-1; i++) f[i][1] -= f[i+1][1];//减去重复，至少转换为恰好有 for(int i = 0; i <= M; i++) f[i][0] -= f[i][1]; //n中有i个2,0个3的数 要减去 n中有i个2,1个3的数 ans = dfs(n, M, 0);//2^(M)的方案数 if (3*(1<<(M-1)) <= n) ans += dfs(n, M-1, 1); //如果2^(M)能够转换为另一种形式2^(M-1)*3，那么还要加上另外的方案数 printf("%lld\n", M(ans)); return 0; }

状压爆搜51分

#include<bits/stdc++.h> #define ll long long using namespace std; int T; ll n, k, ans; ll a[10000005]; const ll mod = 1e9+7; inline ll M(ll a){return a%mod;} inline ll add(ll a, ll b){return M(a+b);} inline ll sub(ll a, ll b){return M(a-b+mod);} inline ll mul(ll a, ll b){return M(a*b);} inline ll P(ll a,ll b){ll c=1;while(b){if(b&1)c=M(c*a);b>>=1;a=M(a*a);}return c;} inline void dfs(int num) { if(num == n+1) { int x1=(1<<k)-1, x2=0; for(int i = 1; i <= n; i++) { x1 = x1&a[i-1]; x2 = x2|a[i]; if(x2 == ((1<<k)-1)) return; } if(!x1 && x2!=((1<<k)-1)) ans++; return; } for(int j = 0; j <= (1<<k)-1; j++) {//货物 a[num] = j; dfs(num+1); } } int main() { scanf("%d", &T); while( T-- ) { scanf("%lld%lld", &n, &k); ans = 0; if(n>4 || k>4) puts("0"); else dfs(0), printf("%lld\n", M(ans)); } return 0; }

推公式正解AC

#include<bits/stdc++.h> #define ll long long using namespace std; int T; ll n, k, ans; const ll mod = 1e9+7; inline ll M(ll a){return a%mod;} inline ll sub(ll a, ll b){return M(a-b+mod);} inline ll mul(ll a, ll b){return M(a*b);} inline ll P(ll a,ll b){ll c=1;while(b){if(b&1)c=M(c*a);b>>=1;a=M(a*a);}return c;} int main() { scanf("%d", &T); while( T-- ) { scanf("%lld%lld", &n, &k); ans = mul( P(2,k), sub(P((P(2,n)-1), k),P((P(2,n)-2),k))); printf("%lld\n", ans); } return 0; }

dfs暴力枚举加特判55分

#include<bits/stdc++.h> #define ll long long using namespace std; const ll mod = 1e9+7; inline ll M(ll a){return a%mod;} inline ll add(ll a, ll b){return M(a+b);} inline ll sub(ll a, ll b){return M(a-b+mod);} inline ll mul(ll a, ll b){return M(a*b);} inline ll P(ll a,ll b){ll c=1;while(b){if(b&1)c=M(c*a);b>>=1;a=M(a*a);}return c;} const int N = 7e4; int a[N], b[N], n, m; bool bis[N], vis[N]; ll fac[N], inv[N], ans; void prep() { fac[0] = 1; for(int i = 1; i <= n; i++) fac[i] = mul(fac[i-1], i); }//处理阶乘 inline void dfs(int sum) { if(sum == n+1) { int mi = m; for(int i = 1; i <= n; i++) b[i] = a[i]; for(int i = 1, j; i <= n && mi; i<<=1){//跳的距离 j = 1; while(j < n && mi) { if(b[j] > b[j+i]) swap(b[j], b[j+i]); if(b[j]==1 && vis[b[j+i]]) return; if(vis[b[j+i]]) mi--; j += i<<1; } } ans++; } for(int i = 1; i <= n; i++) if(!bis[i]) a[sum]=i, bis[i]=1, dfs(sum+1), bis[i]=0; } inline ll work() { if(!m) return fac[n]; if(n-m <= 2) return 0; for(int i = 1, x; i <= m; ++i) { scanf("%d", &x); vis[x] = 1; } if(vis[2]) return 0; dfs(1); return M(ans); } int main() { scanf("%d%d", &n, &m); n = P(2, n); prep(); printf("%lld", work()); return 0; }