Submission #35779478

---

Source Code Expand

#include <bits/stdc++.h>
#include <atcoder/modint>
using mint = atcoder::modint998244353;
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)

ll read(){ll r;scanf("%lld",&r);return r;}

vector<string> ss;

char t[500010];

int main(){
  int n = read();
  int sz=0;
  rep(i,0,n){
    scanf("%s",t);
    sz=max(sz,(int)strlen(t));
    ss.push_back(t);
  }
  vector<mint>ans(n,1); // 1-index
  vector<vector<int>> g = {{}};
  rep(i,0,n)g[0].push_back(i);
  rep(j,0,sz){
    vector<vector<int>> nextg = {};
    for(auto &idx:g){ // idx 前j位一样, 从第j位开始比
      vector<vector<int> > ch2idx('z'-'a'+2); // 空, 'a', .. ,'z'
      for(auto i:idx){
        if((int)ss[i].size() == j) ch2idx[0].push_back(i);
        else ch2idx[ss[i][j]-'a'+1].push_back(i);
      }
      // 空 + (all-空-cur)/2 = (all+空-cur)/2
      for(auto i:idx)if((int)ss[i].size()!=j)ans[i] += mint(idx.size()+ch2idx[0].size()-ch2idx[ss[i][j]-'a'+1].size())/2;
      rep(i,0,'z'-'a'+2)if(ch2idx[i].size()>1)nextg.push_back(ch2idx[i]);
    }
    g=nextg;
  }
  for(auto v:ans)printf("%d\n",v.val());
  return 0;
}

// n个 小写字母 字符串
// 字典序得到学号
//
// 但是 是按照 a-z 的一个排列p 来决定 字典序大小, 而不是默认的
//
// 计算每个学生学号期望值
// 两两不同
// 
// 5e5
// 估计<= 141310 人
// 
// A < B , 前缀相同, 'ch0' < 'ch1', 或A更短
// A > B , 前缀相同, 'ch0' > 'ch1', 或B更短

Submission Info

Compile Error

./Main.cpp: In function ‘ll read()’:
./Main.cpp:10:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   10 | ll read(){ll r;scanf("%lld",&r);return r;}
      |                ~~~~~^~~~~~~~~~~
./Main.cpp: In function ‘int main()’:
./Main.cpp:20:10: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   20 |     scanf("%s",t);
      |     ~~~~~^~~~~~~~

Judge Result