吐槽诗（打油诗）
题面玄乎冗长，故事倒是挺好。
题解简单明了，尽显高深玄妙。
代码格式清晰，就是注释太少。
今天题目可订？你怕是在说笑！
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;}//求xfor(int i = 1; i <= lenp; i++)printf("%d", Ci(p[i]));puts("0");//输出10x即sprintf("0");for(int i = 1; i <= lenp; i++)printf("%d", Ci(p[i]));//输出x即treturn 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个2for(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;
}